In this if a number is odd then only one operation is allowed multiplying by 2 and if number is even then we can divide the number until that number is odd. i stored all these numbers in a vector and created a hash map.
Then I traversed on vector and found minimum difference.
This solution passed in contest on hackerearth. But I have a test for which it fails.
Test Case : 2 5
for this answer should be 3 but my logic is giving 1 is it correct or not ?
Can you post your code?
@rude009 this question is from a hiring contest I have submitted the solution their and i don’t have the copy of it as we can’t copy and paste the solution their. I have done it the same way i have explained. It got passed.
Your soln is not clear how do you find minimum while traversing the array?
I have stored all the values in a vector which can be obtained either by multiplying or dividing. then sorted the vector and took the difference of first 2 elements.
It has to be 3 becuz you are either replacing 2 by 1 or keeping as it is. Min abs difference will occur with 2 so need to change. The problem with your algo is that you are not removing the E’th element after replacing it with E/2 from Hash.
My issue is my solution got accepted.
And I am not getting correct solution of this question in nlogn complexity.
Can’t exactly tell why your solution got accepted. Weak Cases maybe! But your hash should either look like [2, 5], [1, 5], [2, 10], [1, 10]. And you are getting ans as 1 becuz your hash is somewhat
[2,1,5]. Min abs diff possible is 1 in that case.
One of the solution is to insert elements in set one by one i.e. while traversing the array suppose you’ve a number x the first take the lower_bound, lower_boun-1 and lower_bound+1 to get min difference. Then check for x/2, x/4…,x/(2^i) if its even other wise check for 2*x. Then insert all possible elements in set i.e insert x,x/2,x/4 or 2x etc.
