 # SPOTWO - Editorial

EASY

### PREREQUISITES:

High school maths

### PROBLEM:

Calculate (2N__bin)2 % 1000000007 for given N, where N__bin stands for the decimal number encoded by the representation in base 2 of the number N

### QUICK EXPLANATION:

Store the binary representation of N as decimal number in appropriate data type(as per language). Use fast exponentiation technique to calculate the result within time limit.

### EXPLANATION:

First task is to get binary representation of N as decimal number. The largest value of N is 600000 whose binary representation is 10010010011111000000 which is less than 2^64 but greater than 2^63. For C programmers, unsigned long long is suitable to store this value.

Next task is to calculate (2N_bin)2 % 1000000007 within time limit. This can be achieved using Right-to-left binary method for modular exponentiation.
See mugurelionut’s solution for simple implementation in C/C++

Another simple way of calculating 2n in log n time is by using exponentiation by squaring. See setter’s solution for a simple function using this technique.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here
Tester’s solution can be found here and here

4 Likes

if power is greater than MOD value… you could use this to simplify the result calculation,

(x^(N%(MOD-1)))%MOD,

Eg, Binary Representation of 600000 in decimal is 10010010011111000000,
now 10010010011111000000 % ((1e9+7)-1) = 50940294

You can now see that (2^50940294)%(1e9+7) = (2^10010010011111000000)%(1e9+7) = 140171955.
Simple DP should take care about the rest of the optimizations.

4 Likes

Hello @all,

Besides the presented solutions (the tester one and mine) there is a much more clever solution of which I was not aware of.

Sadly, my solution was too complicated, possibly because I wanted to make something look harder than what it actually was.

I thought that for a specific value of N (around 527.000) its binary representation would exceed the capacity of an unsigned long long and as such I used simple fast exponentiation below that “threshold” value and devised a simple grade-school arithmetic scheme to “get around” the “supposed” ULL overflow.

You can read it when the links are live The testers’ solution uses @mugurelionut scheme where the fact of not occuring any overflow just makes the task trivial with simple fast exponentiation (I really must have overlooked this fact while searching for C++ type limits).

Finally, the more theoretical solution which possibly lots of contestants used is based on a variation of Fermat’s Little Theorem that exploits the fact that:

2M-1 mod M = 1, where M = 109+7.

Therefore, we just output 2(2*N_bin % (M-1)) mod M

and we have correct answer!! As you can see, this trick would allow for a much higher constraint on the value of N assuming you would process it properly. Sadly, when I was told about this trick, I didn’t fully understood it (it was few months ago) and I ended up writing the most naive solution possible.

Hiroto Sekkido told me that even if M is changed, the sequence {20 mod M, 22 mod M, 22 mod M,…, 2k mod M, …} must be periodic (ignoring the first a few
terms), so such kind of cheat could be applicable.

I can leave here his solution using this approach as reference:

``````#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define M 1000000007
#define ll long long

ll pw(ll a,ll b, ll md){
ll r;
if(!b) return 1;
r = pw(a,b/2,md);
r = (r*r)%md;
if(b%2) r = (r*a)%md;
return r;
}

int main(){
int T, N;
int B;

scanf("%d",&T);
while(T--){
scanf("%d",&N);
B = 0;
p = 0; add = 1;
while(N){
N /= 2;
}
p = (p*2)%(M-1);
printf("%d
``````

",(int)pw(2,p,M));
}

``````  return 0;
}
``````

This was the reason why the problem was set as EASY instead of MEDIUM.

Nontheless, I hope you have enjoyed it Best,

Bruno

2 Likes

This is what I did
600000’s binary is 10010010011111000000. So I computed an array of following values offline using a C program of modular exponentiation.

• (2^10)%M
• (2^100)%M
• (2^1000)%M
• (2^10000)%M
• .
• .
• .
• (2^10000000000000000000)%M

Now,600000’s binary (2^10010010011111000000)%M
can be written as *((2^10000000000000000000)%M)*(2^(10000000000000000)%M)… (2^1000000)%M)%M

5 Likes

Yeah. . My solution exploited Fermat’s little theorem too I implemented a Dynamic Programming approach. Each problem can be divided into 2 sub-problems (except powers of 2 like 4, 8, 16, 32, … which can be trivially solved). See below:

Base cases:

• 2^1 = 2^1 = 2;
• 2^2 = 2^10 = 1024;

• 2^3 = 2^11 = 2^10 * 2^1;
• 2^4 = 2^100 = (2^10)^10;
• 2^5 = 2^101 = 2^100 * 2^1;
• 2^6 = 2^110 = 2^100 * 2^10;
• 2^168 = 2^10101000 = 2^10100000 * 2^1000
• and so on

Execution time - 0.23 Seconds

http://www.codechef.com/viewsolution/2913164

Can anyone tell me why this gave me WA?
http://www.codechef.com/viewsolution/2968557

class Codechef
{

public static void main (String[] args) throws java.lang.Exception
{
Scanner sc=new Scanner(System.in);

int t=sc.nextInt();

while(t–>0)
{
int n=sc.nextInt();

``````String s=Integer.toString(n,2);
``````

int val=Integer.parseInt(s);

``````  BigInteger bi=new BigInteger("2");

BigInteger ans=bi.pow(val*2);
``````

System.out.println(ans);}
}
}

how can we solve the same problem if N > 600000 i.e, if binary representation has more than 64 bits?

@anil09, use big integer in the case of java, or use strings to manipulate bigger digits…

@mecodesta: suppose i am using only C. and i have 100bit value stored in string.That 100bit value treated as integer(N_bin) according to problem. How can we do left/right shift operations on that string?

this is only possible when MOD is prime.

this is what i did…it is definitely the most simple and fast way.
http://www.codechef.com/viewsolution/2923042

Yeah but then again, most likely the MOD is selected to be a prime number to get the most out of it !!

hope u get wat i mean in the code… 