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