# The Problem
This particular LeetCode [problem](https://leetcode.com/problems/find-unique-binary-string) of the day was exceptionally fun.
It felt familiar, though I hadn't solved it before. I could immediately see a Trie implementation, but given that my developmental aims included learning to use bitwise operations more intuitively, and that I misliked writing out a whole Trie class, I decided to forego that approach. I thought about ```reduce()``` with xor, looking for the first index where all the strings had the same parity, and a few other things on paper before I realized this was going nowhere. And then, all of a sudden, I realized what this problem had reminded me of...
# Cantor's Diagonal Proof
Cantor's diagonal proof is the idea that if you serry an _infinite_ number of _infinitely long_, **unique** binary sequences in an infinity by infinity grid, you can _always_ still generate yet another **unique, _infinitely long_** binary sequence that is not housed in that matrix. How? By ensuring that the solution sequence mismatches _every single row_, step by step.
In the first row, you take the opposite of the first digit. On the second row, you take the opposite of the second digit. On the third, you take the opposite of the third digit...and so on and so forth.
Visually, it would like something like:
$
\begin{pmatrix}
s_1 = & a_{11} & a_{12} & a_{13} & \cdots \\
s_2 = & a_{21} & a_{22} & a_{23} & \cdots \\
s_3 = & a_{31} & a_{32} & a_{33} & \cdots \\
\vdots & \vdots & \vdots & \vdots & \ddots
\end{pmatrix}
$
where:
$
d = (a_{11},\ a_{22},\ a_{33},\ \ldots,\ a_{nn},\ \ldots)
$
is the main diagonal, and:
$
b_n = \begin{cases} 0 & \text{if } a_{nn} \neq 0 \\ 1 & \text{if } a_{nn} = 0 \end{cases}
$
is the function we have to implement over the integers $[0,n−1]$ where $n$ is the length of the strings we're given.
You don't have to use bitwise operators for this (you really shouldn't if you're trying to write anything readable), but I did use them so I'll briefly explain.
I'm converting the ASCII code to a 0 or 1 with `ord(i)`AND 1, (which you could replace with a simple `int(i)`) and then I'm getting the complement with XOR (which you could replace with an if else statement). Then convert back to a string with `str()` and join it all together. Super simple and sweet. And fast. And redolent of my math classes.
# Complexity
- Time complexity: O(n)
- Space complexity: O(n)
# Code
```python
class Solution:
def findDifferentBinaryString(self, nums: List[str]) -> str:
return "".join(str(ord(x[i])&1^1) for i,x in enumerate(nums))
```