HackWithInfy Round 2 - The Number Game

@shravan660 No, there will be 10^18 states.

2 Likes

If you think it in the binary as I told before, Suppose
A = 10101101
B = 10111110
And we are changing A to B, For A to become exactly equal to B, all bits of A must be same as that of B. If we look at the fourth bit from the left, the only way to change that bit is to first decrease A so much that the fourth bit from the left becomes the rightmost because only then we can add 1 to it which will change the bit.
After we change the leftmost unmatched bit, thereā€™s really only one straightforward way to build the remaining number the same as B and thatā€™s what we are following. I canā€™t prove it formally but I think it should make enough sense up to your satisfaction.

BFS will definitely give the correct answer but its going to be too slow. Hereā€™s why,
From every number, you have 2 or 3 options to explore. Letā€™s suppose it to be only 2 for all numbers. So if you make the BFS tree, youā€™ll see that the number of nodes are doubling every next level and there are going to be O(log(n)) levels because you will find your answer in a path of length O(log(n)) at max. So the total complexity is equal to the number of nodes in the BFS tree which is
2^(levels) = 2^(log(n)) = n
And n can be up to 10^18.

I solved 2 problems. Any guesses if I would be called for interview? If yes, then tentatively when will be the interview?

I am having a little trouble understanding your solution. Maybe if you can explain the idea of your approach.

Result declaration is far away considering cyclone affected candidates did not take Sunday exam and will be rescheduled to give exam at a later date.

@shravan660 how do you propose to use bfs in this problem?

1 Like

It ll give tle however. Chill

aare plzzz Share Sirā€¦I want to know

1 Like

Sir xD bro even I am 1999

So, I would first put the number (likely A here) in a queue. In a while loop, initial we remove A . Now we do all process A-1 if odd, A+1 if even,A*2,A/2 if even. We put these values in the queue. And we remove and do the same step untill B is achieved

Ok okā€¦can we communicate through social media or mail just for interaction?

instagram @shravalogy_

I am not in insta Sir. You did all the questions in hackwithinfy?

2 only. then i got server error and come out :frowning:


This is my solution

1 Like