# SPOJ WA, LOCKER - Magic of the locker

LOCKER - Magic of the locker

My Solution: 25439050 (ID)

Hi, I have already been through the discussions on this question on SPOJ…can’t reach an AC tho!!
My approach:

1. for 0 ans is 1
2. for 1 ans is 1.
3. any other number n … count the no. of 3s by d = (n/3) and remainder rem = (n%3) then if rem is 1 then increase rem by 3 , decrease d by 1 …for final answer… raised 3^d and multiply with rem.

Code:
import java.io.*;

`````` class Main {

static long c = (long)(Math.pow(10,9)+7);

public static void main(String[] args) throws IOException {

while (l-- > 0) {
long res = 1;

if(n==1){System.out.println(1);continue;}
long d = ((n%c)/3)%c;
long rem = (n%3);

if(rem == 1){d--;rem+=3;}
else if(rem == 0){rem++;}  // keeps final ansr non-zero

long a = 3;
while (d > 0) {
if ((d & 1) == 1) {
res = (res*a)%c;
}
a = (a*a)%c;
d >>= 1;
}
res = (rem*res);
System.out.println(res);
}
}
}
``````

PS: This is my first time asking a doubt … Any test case where my code fails will also help. Thank you.

Can u please explain where my approach is wrong . I was doing this is n is even I was calculating 2^(n/2) && if n is odd then 3*2^((n/2)-1) but it gave WA. @mitsuki

2 Likes

Hey @kanisht09 first of all thanks , u r the first one ever on this platform to ask me a doubt

I would like to suggest u:

1. Take more examples and dry run your code on them
Take n = 6
n/2 = 3; 2^3 = 8 (solution returned by your code )
whereas if a 6mtrs long rope to be cut into 3 + 3
answer would have been 3*3 = 9 ( >8 ).

2. Try to learn Binary Exponentiation
this approach is better and efficient for large numbers (Use This)

PS:Sorry for late reply since i’m not active on this account this days

1 Like

yep thanks a lot bro for helping me.