In a recent hiring challenge, a question was asked to find the no. of arrays of size N, whose xor of all the elements is 0 and the array should only contain 0,1,2,3,4,5 as its element. Return ans%(1e9+7). 1<=N<=1e5
Here are the test cases for the first 60 elements.
How should I approach this problem?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | dXqwq | 3436 |
| 8 | Radewoosh | 3415 |
| 9 | Otomachi_Una | 3413 |
| 10 | Um_nik | 3376 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | adamant | 152 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 144 |
| 5 | errorgorn | 141 |
| 6 | cry | 139 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 9 | TheScrasse | 134 |
What is N in this case? The size of the arrays?
yes, N is the input size of the array.
Auto comment: topic has been updated by ajayNegi (previous revision, new revision, compare).
Recall that a ^ a = 0, where ^ denotes the xor operation.
yeah, I know that. but my thoughts are quite brute force. I thought of iterating over the no. of 0s and for each iteration go over the no. of 1s and go on until 5 but this too bad. but, then 1^2^3 give 0 and 1^4^5 give 0 so I've to keep this in mind too.
Then I thought of finding the combination of single occurrences of 0s + no. of pairs of (1,1), (2,2), (3,3), (4,4), (5,5) and + no. of triplets like (1,2,3), (1,4,5). But this again pushes me to iterate over the no. of occurrences of 0s and no. of pairs(which is 0(n^2).. bad) plus I've to keep in mind about the permutations(of 0s, 1s, 2s,..) too. So, it boiled down to find the no. of 0s, 1s, 2s, 3s, 4s, 5s and this is what I described in para 1.
Use dp: notice that the xor sum will always be at most $$$7$$$ so we can calculate $$$dp[i][mask]$$$ which represents the number of arrays of length $$$i$$$ with xor sum of $$$mask$$$.
https://ideone.com/GeAdMM
you can solve it using dynamic programming where dp[i][j] = number of ways to form a sequence of length i whose xor is j. At each position you have only 6 choices so u can try all of them, let suppose at position i u choose k and you want your prefix xor to be j so u can calculate as : dp[i][j] += dp[i-1][k^j].
your final answer will be dp[n][0].
Some extensions:
I am pretty sure $$$ N \leq 10 ^ 5$$$ and numbers $$$0,1 ... K$$$ where $$$K \leq 10 ^ 9$$$ can also be solved. And it also seems to be possible to solve $$$ N \leq 10 ^ 9$$$ but it's quite a bit more complicated.
I think that since the bitwise-xor is at most 7, you can use the same DP as mraron said, but with matrix power.
Won't the same methodology work O(7*7*1e9)? or will it exceed the time limits?
Ofcourse, anything above $$$10^9$$$ ( I think even $$$10^8$$$ is too close ) exceeds time limit of $$$1$$$ second.
so, how to solve those extensions within the time limit?
Oh, I understand now. I was going to reply to mraron's comment, by saying why can't we just choose any values for first $$$N-1$$$ elements, and last will be fixed. Then, I reread the problem and your comment made it more clear. The second extension seems interesting to think about.
Wait, even for the second one the subtraction is simple? I thought it will be complicated at first glance, and possibly involve inclusion-exclusion.
For the first one,the answer is simply 8n-1 .
then that should hold for n<=1e5, or did i miss something?
No it would even work for N ≤1018
Read about it here.
you said that the answer is 8^n. I said then the answer for my posted question should be 8^n too(then why are we doing it using dp if it's simply 8^n). or seems like i missed your statement.
Well, the numbers allowed are only $$$0,1,2,3,4,5$$$. The formula $$$8^{N-1}$$$ works if numbers allowed are $$$0,1,2,3,4,5,6,7$$$.
The idea is that, after choosing $$$N-1$$$ numbers to be anything, you can always choose the last one as the xor of the other $$$N-1$$$ elements, and because $$$a \oplus a = 0$$$, we get the whole xor of the array as $$$0$$$.
The problem with doing the same thing for numbers $$$0,1,2,3,4,5$$$ is that, they can have xor $$$6$$$ or $$$7$$$ as well, in which case you couldn't nullify them by a single number. But, something can be done, along similiar lines, using some math.
cool, this is because maximum xor is 7. How about the 2nd extension?
Well, I don't want to give away the whole solution. So, I'll briefly give the idea.
First of all, total number of ways to choose $$$N-1$$$ elements is $$$6^{N-1}$$$. But there are cases, where the xor of these will be $$$6/7$$$. So, final answer is
$$$ ways(N,0) = 6^{N-1} - ways(N-1,6) - ways(N-1,7) $$$
$$$ways(N,X)$$$ represents number of ways to select $$$N$$$ numbers to make xor sum $$$X$$$, given you can only choose numbers from $$$ \{ 0, 1, 2, 3, 4, 5 \} $$$.
I leave it to you to think about $$$ways(N-1,6)$$$ and $$$ways(N-1,7)$$$.
ways(n,6) = 6^(n-1) — ways(n-1,0) — ways(n-1,1)
same for ways(n,7).
is that correct?
Well, for one, you'll keep recursing this way.
Also, I don't understand why you are subtracting $$$ways(N-1,0)$$$ and $$$ways(N-1,1)$$$. You should explain your reasoning, briefly.
Update: Okay, I understood what you have done. Now, you need to solve and get a closed form perhaps, instead of a recursive solution ( because that would be linear in $$$N$$$ ).
total number of ways to choose n-1 elements is 6^(n-1). But there are cases, where the xor of these will be 0/1 (for which i don't have any numbers to write at nth position(only 0 to 5 allowed)).
Edit: how to reach that "closed-form" that you're talking about?
Well, you basically have
$$$ways(N,0) = 6^{N-1} - 2*( 6^{N-2} - ways(N-2,0) - ways(N-2,1) )$$$.
Similiar to the reasoning for $$$ways(N,6) = ways(N,7)$$$, we also have $$$ways(N,0) = ways(N,1)$$$. So,
$$$ways(N,0) = 6^{N-1} - 2*6^{N-2} + 4*ways(N-2,0)$$$
$$$F(N) - 4*F(N-2) = 6^{N-1} - 2*6^{N-2}$$$
the last equation(bringing 4*f(n-2) on right side) f(n) depends on f(n-2), ain't that still linear?
Well, one way to do it is matrix exponentiation ( you might like to view other resources too ). It is a simple linear recurrence.
Another is, you can actually solve this equation completely, write $$$F(N)$$$, then $$$4*F(N-2)$$$, then $$$16*F(N-4)$$$ ..., and the middle terms cancel out, since it telescopes.
In general, I think you get
$$$F(N)-2^{2k}F(N-2k) = 6^{N-1}-2*6^{N-2}+4*6^{N-3}-8*6^{N-4}+...-2^{2k-1}*6^{N-2k}$$$
Depending on whether $$$N$$$ is even or odd, you can make use of base cases $$$N=0$$$ or $$$N=1$$$, and choose $$$K$$$ appropriately. Right hand side, is just a geometric progression ( with first term = $$$6^{N-1}$$$ and common ratio = $$$\dfrac{-2}{6}$$$ ).
I already mentioned that this is the solution to the first extension question of saketh.
For your question, I could not think of any other solution than this.
Isn't it $$$8^{n-1}$$$?
Yes, EDITED :)
Did it : https://ideone.com/g3EqYy
Will there be queries or only single test case? If there is no queries there is a sure dp solution.
Why not a DP solution in case of multiple queries ?
obviously it can. but if there is queries then i need to consider time complexity as i need to otpimize it.