650iq's blog

Can someone pls help with this problem
By 650iq, history, 2 years ago, In English

You are given an integer x which is initially 1. In one move You can perform either of the 2 operations — make x = x-1 or x=2*x. You need to perform exactly K such operations. Find if it is possible to make number N from X. Note N and K is very high upto 10^18.

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
2 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

The question can be rephrased as transforming x to 1 with operations x/=2 and x++
For this we will choose first operation if x is even, second otherwise and we will reach 1 in atmost 128 operations
This looks correct but i can't prove whether this requires the min operations or not

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

    He is not looking for min operations, it's "exactly K such operations". Very strange since usually this type of problem is asked about "min operations"

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

I think this problem is in the problem set.

We can approach it in reverse -> try to make 1 from x. This is valid since if we can make x from 1 then reverse should be possible.

so in reverse following two operations are possible: 1) divide x by 2 (if even) 2) increment x by 1

so keep on dividing x by 2 until it is divisible by 2. else if it becomes odd then increment. keep on counting the operations.

--> NOTE: this gives you minimum number of operations (say N). if we can reach in N oper. then we can reach in any operations >= N. in start we can simply waste excess operations by 1*2 = 2 , then 2-1 = 1.

then at last compare the no. of operations taken with k and print the answer.

→ Reply