prathams's blog

Find p such that 2^p starts with n
By prathams, history, 9 years ago, In English

Given value of n, how can we find the power(p) of 2 such that the result 2^p starts with n.

For ex —

n = 12 then answer is 7 i.e., 2^7 = 128.

n = 82 then answer is 209 i.e., 2^209 = 822752278660603021.........

If no such power exist then p should be -1.

I have coded it, but giving WA and TLE on some test cases. Here is the link to my code : link

How can we find power efficiently ? I got this problem on link

UPD : Thank you all, Tima's approach helps me to get AC. In case anyone interested, here is the link to my code : link

  • Vote: I like it
  • +11
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Let's assume the correct answer is k so 2k begins with n.

N consists of ⌈ log(n)⌉ digits and 2k consists of ⌈ k log(2)⌉ digits, so

by taking log to the base 2 for both sides of the equation

so we have to find minimum k which satisfies the equation without having to compute large exponential numbers.

I'm not sure though if the answer will be in a range that allows linear search.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Even i did the same thing, i.e., finding the first log10(n) digits of 2^k for each k between 0 to some random max value and checking it with n. But the search for k is not within some range. I wonder if their is any formula or trick to find it.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      you can use binary search to find k... can't you?

      → Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

You want to find k such that n00..00 ≤ 2k ≤ n99..99, where we have L zeroes/nines. This is equivalent to n10L ≤ 2k < (n + 1)10L; taking logarithms we have . It seems that linear iteration through L with doubles in this form is enough to get accepted.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I don't remember exact constraints, but that problem was given on a Petr Mitrichev contest. Constraints definitely didn't allow simple computations on logarithms, however there was an information that input is randomized. FYI, it got 0 ACs :P.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Let x is integer, such that 10x ≤ n < 10x + 1, and y = 10x. 

double d = 1.0;
for(int i=1;i<=100000000;i++){
  d = d * 2.0;
  while(d >= y) d /= 10;
  if(int(d) == n){
    cout << i;
    return 0;
  }
}
→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you tell me why this works?
    Thanks first.

    → Reply