SPOJ WA, LOCKER - Magic of the locker

general
,
1

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!!:confused:
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 {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int l = Integer.parseInt(br.readLine());
        while (l-- > 0) {
            long n = Long.parseLong(br.readLine());
            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.:grinning:

1 Like
2

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
3

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

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 :wink:

1 Like
5

yep thanks a lot bro for helping me.

6

I had the same doubt
.

7

Hi, bro I just see your rating graph. I am amazed :smiley: :heart_eyes: :star_struck:, I think in just 3 months you improve a lot in Competitive Programming. Any tips regarding improving in Competitive Programming are welcomed.

1 Like
8

Codeforces only and select by tags and do . My rating is not good because I avoid short contests sometimes. You should be amazed by someone who participates in all contests and still 4* or above

1 Like