It is 2nd Question from Yesterday's PayU Hiring Challenge on Hackerearth PROBLEM Given an array with size n and maximum value l compute $(\sum_{i=0}^{l} t_i * 31^l)$ % mod where mod=10e9+7 $t_i$=size of maximum subset whose xor is i If there is no subset whose xor is i then $t_i$=0 Constraints $n<=10^4$ $a[i]<=10^3$ Sample Example 4 1 2 3 4 Output 3755653 Explanation l=4 For i=0 $31^0 * 3$ Subset is (1,2,3) For i=1 $31^1 * 2$ Subset is (2,3) For i=2 $31^2 * 2$ Subset is (1,3) For i=3 $31^3 * 2$ Subset is (1,2) For i=4 $31^4 * 4$ Subset is (1,2,3,4) I used DP to solve this problem but got WA Here is link to my Solution It would be grateful if someone can point out my mistake :) asked 07 Aug '17, 12:20

why range here is 1001 and not 1024 because xor can vary till 1024. Although a[i] <=1000 but a[i]^j can be above 1000 till 1024.. no?? and this will affect when you are calculating max using dp.. because you have not updated cells of j>1000.. answered 07 Aug '17, 13:56

Do you remember problem name?? I can look up in my submissions and check.. I solved that question successfully and remember that there was some edge condition in dp.. I can help easily then.. :)