×

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

This question is marked "community wiki".

616913
accept rate: 0%

(11 Nov '13, 15:52)

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

(11 Nov '13, 16:18) 1★

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

(11 Nov '13, 16:32)

@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?

(11 Nov '13, 16:42) 1★

(11 Nov '13, 22:21)

Why no correct submission in python ?

(12 Nov '13, 12:03) 2★

@anil09

u can see my version of solution... hope u get wat i mean in the code.. :)

http://www.codechef.com/viewplaintext/2919571

(12 Nov '13, 21:03)
showing 5 of 7 show all

 6 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 answered 11 Nov '13, 16:54 180●1●2●9 accept rate: 0% this is what i did...it is definitely the most simple and fast way. http://www.codechef.com/viewsolution/2923042 (11 Nov '13, 17:19) defacto3★ same here..http://www.codechef.com/viewsolution/2980062 simple and efficient (12 Nov '13, 01:07)
 5 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. answered 11 Nov '13, 16:09 364●15●18●27 accept rate: 0% this is only possible when MOD is prime. (11 Nov '13, 17:06) Yeah but then again, most likely the MOD is selected to be a prime number to get the most out of it !! (11 Nov '13, 17:21)
 2 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 #include #include #define REP(i,a,b) for(i=a;i
 0 Yeah. . My solution exploited Fermat's little theorem too :) answered 11 Nov '13, 17:07 5★bodmas 161●2●7 accept rate: 0%
 0 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 answered 12 Nov '13, 10:13 4★abhinav1 31●3 accept rate: 0%
 0 Can anyone tell me why this gave me WA? http://www.codechef.com/viewsolution/2968557 answered 12 Nov '13, 20:20 252●6 accept rate: 0% I guess directly using ULL won´t work and you have to do it incremetally... Check @mugurelionut's solution for further reference (12 Nov '13, 21:10) kuruma3★ Your solution is giving WA because you are passing 2nbin to your function. 600000 in binary is close to 1.1E19 and range of ULL is 1.8E19. So 2nbin will go out of range. What you can do is make two calls to the modular exponent function, first to calculate 2^nbin and then (result of first call)^2. (13 Nov '13, 05:17)
 0 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);} // your code goes here } } answered 04 Mar '15, 02:47 9 accept rate: 0% It is showing time limit exceeded what should I do to optimize the program? (04 Mar '15, 02:48)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,852
×3,820
×15
×1

question asked: 11 Nov '13, 15:04

question was seen: 5,904 times

last updated: 04 Mar '15, 02:48