You are a legendary Alchemist known for transmuting any number N to 1. In this transmutation process, you do 2 operations: If a number is odd, you either add 1 to it or subtract 1 from it. If a number is even, you divide the number by 2. Now, you have received a special request from Your Highness himself to transmute N to 1; however, he wants you to do it in the minimum number of steps to save time. Can you maintain your status-quo as the legendary Alchemist? Input: The first line of input contains T, the number of testcases. T testcases follow. Each testcase contains one line of input containing number N. Output: For each testcase, in a new line, print the minimum number of steps. Constraints: 1 <= T <= 100 1 <= N <= 10000000 Example: Input: 4 1 2 3 4 Output: 0 1 2 2 Explanation: Testcase1: 1 can be converted into 1 in 0 steps. Testcase2: 2 can be converted into 1 in 1 step: 2-1 [2:03 PM, 7/15/2019] A_man: I have solved the the question but getting tle please help.
Transmutation problem of dp
@amanm2292 hey aman can you please share the link of the question so that I can check this question is also covered by deepak bhaiya.
this is almost same as the question covered in the video by deepak bhaia but here a more option to reduce a number is there ie here we can reduce the no. (n-1) when it is odd as per the question that i sent you.this
yes ? have you saw the question?
@amanm2292 hey aman this will work
Given a number N. The task is to reduce the given number N to 1 in the minimum number of steps. You can perform any one of the below operations in each step.
Operation 1: If the number is even then you can divide the number by 2.
Operation 2: If the number is odd then you are allowed to perform either (n+1) or (n-1).
You need to print the minimum number of steps required to reduce the number N to 1 by performing the above operations.
Examples:
Input : n = 15
Output : 5
15 is odd 15+1=16
16 is even 16/2=8
8 is even 8/2=4
4 is even 4/2=2
2 is even 2/2=1
Input : n = 7
Output : 4
7->6
6->3
3->2
2->1
try to form recursive form this will work If you able to forn recursive solution do tag I will help you out with coding part.
i have tried with recursive solution but it is taking too much time
i actually not able to implement top down dp approach well thats why i used bottom up solution
i have given the code link above that is not fast it is giving TLE.HELP MW IN OPTIMIZING THAT CODE
althogh i think as far as i think logic is right.
this is my code.
@amanm2292 hey aman you can do this without dp
here is the recursive form it’s execution time is 0.02
recursive solution.
now with the help of this approach try memoization and bottom-up approach
i saw this solution already from gfg only but i could not be able to implement it through the bottom help help me in that please. because here we can apply dp as it is same as the deepak bhaiyas question of reducing to 1 problem
i have tried and shared the code already please tell what is wrong in my code or what can i do to make it run for all test case with time limit
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.