ajayNegi's blog

No. of arrays with xor sum equal to 0
By ajayNegi, history, 4 years ago, In English

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?

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it -10 Vote: I do not like it

What is N in this case? The size of the arrays?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ajayNegi (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it -23 Vote: I do not like it
Hint
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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$$$.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

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].

→ Reply
»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Some extensions:

  • Solve for $$$N \leq 10^9$$$ if elements are in $$${0,1,2,3,4,5,6,7}$$$.
  • Solve for $$$N \leq 10^9$$$ with original values $$${0,1,2,3,4,5}$$$.
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it +16 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think that since the bitwise-xor is at most 7, you can use the same DP as mraron said, but with matrix power.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    Won't the same methodology work O(7*7*1e9)? or will it exceed the time limits?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ofcourse, anything above $$$10^9$$$ ( I think even $$$10^8$$$ is too close ) exceeds time limit of $$$1$$$ second.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        so, how to solve those extensions within the time limit?

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wait, even for the second one the subtraction is simple? I thought it will be complicated at first glance, and possibly involve inclusion-exclusion.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    For the first one,the answer is simply 8n-1 .

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      then that should hold for n<=1e5, or did i miss something?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        No it would even work for N ≤1018

        Read about it here.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              cool, this is because maximum xor is 7. How about the 2nd extension?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                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)$$$.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  ways(n,6) = 6^(n-1) — ways(n-1,0) — ways(n-1,1)

                  same for ways(n,7).

                  is that correct?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                  ← Rev. 3   Vote: I like it 0 Vote: I do not like it

                  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$$$ ).

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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}$$$

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  the last equation(bringing 4*f(n-2) on right side) f(n) depends on f(n-2), ain't that still linear?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                  ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                  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}$$$ ).

                  → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Isn't it $$$8^{n-1}$$$?

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did it : https://ideone.com/g3EqYy

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be queries or only single test case? If there is no queries there is a sure dp solution.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why not a DP solution in case of multiple queries ?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      obviously it can. but if there is queries then i need to consider time complexity as i need to otpimize it.

      → Reply