Please read the new rule regarding the restriction on the use of AI tools. ×

Lakshay149's blog

https://www.hackerrank.com/challenges/prime-xor/problem.Can anybody tell how to approach this problem.

By Lakshay149, history, 5 years ago, In English

I dont know how to approach this problem can someone help me with the dp and recursive relation.This is a hackerrank problem. Intuition behind it.https://www.hackerrank.com/challenges/prime-xor/problem

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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

There will be atmost $$${1000}$$$ distinct values. The xor of all these values will be atmost $$${2^{13} -1}$$$. So you can have a state $$${(x,y)}$$$ where x is the value you currently are and y is the xor accumulated by taking some instances of previous elements. You can take even instances of this element x with no effect on xor or odd instances of this element with xor changing to $$${y}$$$ xor $$${x}$$$. You can map values from $$${3500-4500}$$$ to $$${1-1000}$$$. Store frequency for each element. You will have to precompute factorials and inverse factorials upto $$${100000}$$$. Total states will be atmost $$${1000 * 8191 }$$$

→ Reply