HackWithInfy Round 2 - The Number Game

1

I recently attended HackWithInfy Round 2 and this was one of the questions they asked.
Two numbers will be given A and B. Constraints: 1<=A,B<=10^18.

Four operations are allowed:

  1. If a number is odd, you can subtract 1 from it
  2. If a number is even, you can add 1 to it
  3. If a number is even or odd, you can multiply 2 to it
  4. If a number is even, you can divide it by 2

What is the minimum number of operations to reach B from A. If not possible, just print 1.

I tried this with recursion and it gave TLE for large numbers. I couldn’t do using memorization also. If anyone came up with a better approach, please share it here.

My approach:
The Number Game

2

You could use bfs which would have time complexity O(n)

3

@shravan660 Please Sir,can you explain how should I approach this problem??

4

Sir,@coderag, did you find any impossible test cases???

5

No, I didn’t find any.

6

If possible, can you implement and share?

7

see this solution

2 Likes
8

Observation
Can be done in O(log(n)) using bit manipulation. Look at the binary form of the two numbers.
It doesn’t matter whether you go from A to B or B to A. The process is reversible. So, I am gonna focus on going from the smaller number to the bigger number.
The operations on the binary numbers can be looked as follows-

  1. If the number has a 1 bit at the end, you can make it 0
  2. If a number has a 0 bit at the end, you can make it 1
  3. You can add a 0 at the end of the number whenever you want
  4. If there is a zero at the end, you can remove it

Notice, we can build any number we want with the given type of operations.

Solution
Let A < B

  1. Look at how much of the prefix of A and B is same.
  2. Then perform the operations to reduce A to just the common prefix.
  3. Then perform the operations to build A same as B.
5 Likes
9

@harisisbatman @nehra_1997 Thanks for the approach. I really didn’t think of bit manipulation during the contest.

10

Yeap… Happens.

11

I would like to share my approach.What I did was try to bring A and B to some common term.The common term that we can bring A and B to provided A and B are both>=2 is 2 with the help of given operations.So
1)list all the numbers obtained in the process of converting B to 2.
2)this conversion is carried out in the following way
1->if B is odd, decrease it.
2->ifB is even divide by 2.This iteration here i think will also be taking log(B) at most.
3)try to convert A to 2 in the same way.If in the process ,if we encounter some number that is common with the numbers in the process of converting B to 2, we stop the iteration.
4)ans will be sum of (steps taken to convert A to that common number)+(steps taken to convert B to that common number).

Although Sample test cases passed, I cannot prove optimality.@harisisbatman, would you like to comment about this solution?

Thanks for your solution also…

1 Like
12

@sayan_1999
Yes, the time complexity is O(log(n)) and you are doing exactly the same thing I described with a little different way of thinking. According to my understanding, your solution is correct and efficient. I hope you did not forget to take care of cases where A or B is 1. I think you should have just gone to the number 1 rather than 2 and it would have automatically taken care of it.

13

damn, how much is this question worth in terms of points?

14

@harisisbatman thanks so much for taking time to go through my solution and comment.
You really have been a tremendous help to beginners like us.
However what I really miss is how are you going to prove that your solution or mine will give the minimum number of steps?

15

It was 75 points.But i think you will be angry to know that the question included a statement of impossibility even though that impossible case shall never come. I never seen such type of misguiding statements ever in my life in CP. These people take CP contests but violate certain basic courtsies.

1 Like
16

We can’t use bfs?

17

I don’t know whether people who did this question noticed or not. I was checking my solution for some custom test cases during the contest. For many outputs, which can be obtained only by multiplying it by 2, the expected output was 1 less than the actual answer.
For example:
1
2 8
For this example, the output was 1, but we can never reach 8 by making only one operation. It should be two. Similarly I checked for all cases in which result can be obtained only by multiplying the number by 2 ‘n’ times. The output was always ‘n-1’. Anyway I submitted.

18

These people…I don’t know…why do they host contest if they can’t follow some basic norms of CP?

19

Yeah I faced the same problem. I ignored the checker. Most likely it was designed to confuse us. Though I hate the fact that there were no pretests and the solution was just saved. It’s not like you can run a stress test on an online compiler.

1 Like
20

Sir,if they did so, believe me it’s cheating.Total misguidance.