can anyone please help me with this question : Devotee of god . I looked in the submission and found that just (2^n %mod ) & (2^n-1)%mod is answer. But i’m not getting the reason behind it.
use (2^n)%mod and ((2^n)%mod)-1
Initially, say it is x , then it becomes 2x after crossing the river, then it gives y to temple . So, it becomes 2x-y , in second step, it doubles again, so 4x-2y it becomes. It will give y to temple again, so the final value will be 4x-3y . What is the smallest possible value of x and y which satisfies the above equation ? 
After 2-steps :- 4x-3y
After 3-steps:- 8x-7y
After 4-steps:- 16x-5y
Now, you can see the pattern
1 Like