650iq's blog

Can someone pls help with this problem
By 650iq, history, 8 months 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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you share the problem link?

→ Reply
»
8 months ago, # |
  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
  • »
    »
    8 months ago, # ^ |
      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
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes we need to perform exactly K operations

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

    If I understand correctly, your solution solves the problem. If K >= min operations, then the answer is “Yes”. We can simply do 2 using x *= 2 and do 1 using x -= 1 and then use minimal operations to get N. It seems something like this

    → Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the cases can be, first of all we multiply x with 2 till it exceeds or just become N, then we will count the difference of new x from the N, so the total operations will be (No. of times we need to multiply x with 2 to make it greater than or equal to N + (Difference of new x with N)), but as you can see this is the most optimal solution, however multiple such solutions can exist and what we need to do for other solutions is that, we will again multiple the new updated x with 2, this will increment the first operation by one also also increment the second operation by a lot of times, we will do this continuously till x reaches out of bound and we can check for each total operations whether they match the k or not, if at the end of all cases no such condition is found where operations == k, then we can simply say that it is impossible otherwise it is possible, this is just my thinking, it may be correct or not.

→ Reply
»
8 months ago, # |
← 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