A complex polynomial is determined by its zeros and ones. Let $P$ and $Q$ be two non-constant complex polynomials (in one variable).
Assume that
$$
\{z:\ P(z)=0\} = \{z:\ Q(z)=0\} \text{ and } \{z:\ P(z)=1\} = \{z:\ Q(z)=1\}
$$

Then show that $P=Q$.

I tried this: Define a polynomial $R=P-Q$. Now the roots of $R$ include the zeros as well as the ones of $P$ (and Q). If I could show that the set of zeros and ones of $P$ together form a set of degree greater than $P$ then we will be done since then $R$ would be the zero polynomial. But I am not even sure if that is true.
 A: The fact that the zeros of $P$ and $Q$ are the same means that $P$ and $Q$ are both of the form $(x-z_1)^{p_1}\cdot\ldots\cdot(x-z_n)^{p_n}$, where $p_i$'s for $P$ can be different from the $p_i$'s for $Q$.  
The proof that the powers must be equal is done by induction.  The result is clearly true when the number of factors is $1$.  So fix $P(z)$, let $n$ be the smallest possible number of factors in any polynomial sharing its roots and 1's with $P(z)$, and let $Q(z)$ be a polynomial with that number of factors.  If $P(z)\neq Q(z)$, then we can multiply and divide $P(z)$ and $Q(z)$ in a way that would result in a polynomial with a smaller number of factors, which would be a contradiction.
To answer your comment, an example for the number of factors being $2$ is:
If $P(x)=(x-z_1)^{p_1}(x-z_2)^{p_2}$ and $Q(x)=(x-z_1)^{q_1}(x-z_2)^{q_2}$, then WLOG assume $p_1\neq q_1$.  Then $P(x)^{q_1}\neq Q(x)^{p_1}$.  And dividing them, we see that $R(x)$ := $P(x)^{q_1}/Q(x)^{p_1}$ has the same set of $1$'s as $P(x)$ and $Q(x)$.  On the other hand, $R(x)=(x-z_2)^{q_1p_2-p_1q_2}$ (or 1/R(x) if that exponent is negative) is a polynomial consisting of just $1$ factor, contradicting the assumption that $Q(x)$ was the polynomial with the smallest number of factors that had the same roots as $P(x)$.
A: Your original idea works.
I will prove the following

Lemma: Let $P$ be a non-constant complex polynomial of degree $d$. Let $n$ and $m$ be the number of different zeros of $P$ and $P-1$, respectively. Then we have $n+m\geq d+1$.

The original question follows from the lemma by considering $P-Q$.
Proof of Lemma: Write $P=c\prod_{i=1}^n(x-z_i)^{r_i}$ and $P-1=c\prod_{j=1}^m(x-w_j)^{s_j}$. We have $$\frac{P'}P=\sum_{i=1}^n\frac{r_i}{x-z_i}$$ and similarly $$\frac{P'}{P-1}=\frac{(P-1)'}{P-1}=\sum_{j=1}^m\frac{s_j}{x-w_j}.$$
Taking the difference, we get:
$$\frac{P'}{P(P-1)}=\sum_{j=1}^m\frac{s_j}{x-w_j}-\sum_{i=1}^n\frac{r_i}{x-z_i}.$$
Multiplying both sides by $F=\left(\prod_{i=1}^n(x-z_i)\right)\left(\prod_{j=1}^m(x-w_j)\right)$, we see that the right hand side becomes a polynomial $G$. Therefore we have $FP'= P(P-1)G$, which has degree at least $2d$. Since $P'$ has degree $d-1$, it follows that $n+m=\deg F\geq d+1$.
