Блог пользователя prathams

Find p such that 2^p starts with n
Автор prathams, история, 9 лет назад, По-английски

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

  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
9 лет назад, # |
← Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

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;
  }
}
→ Ответить