You are given a positive integer 'N’. Your task is to find and return the minimum number of steps that 'N' has to take to get reduced to 1.
You can perform any one of the following 3 steps:
1) Subtract 1 from it. (n = n - 1) ,
2) If n is divisible by 2, divide by 2.( if n % 2 == 0, then n = n / 2 ) ,
3) If n is divisible by 3, divide by 3. (if n % 3 == 0, then n = n / 3 ).
For example:
Given:
‘N’ = 4, it will take 2 steps to reduce it to 1, i.e., first divide it by 2 giving 2 and then subtract 1, giving 1.
The first line of input contains an integer ‘T’ denoting the number of test cases.
The following ‘T’ lines contain a single integer ‘N’, denoting the number given to us.
For each test case, You are supposed to return an integer that denotes the minimum steps it takes to reduce the number to 1.
You are not required to print the expected output; it has already been taken care of. Just implement the function.
1 <= ‘T’ <= 5
1 <= ‘N’ <= 10 ^ 5
Time Limit: 1sec.
2
4
10
2
3
In the first test case, it will take 2 steps to reduce it to 1, i.e., first divide it by 2, giving 2, and then subtract 1, giving 1.
In the second test case, it will take 3 steps to reduce it to 1, i.e. first subtract 1, then divide by 3, two times. Therefore a total of 3 steps are required.
2
6
12
2
3
Can we use recursion for all possible cases?
The idea is to use recursion to find all possible cases and then, out of them, choose the minimum.
The steps are as follows:
O((3 ^ N)), Where ‘N’ is the number given to us.
Since we are using recursion and for each case, we have three calls, therefore the overall time complexity will be O(3 ^ N).
O(N), Where ‘N’ is the number given to us.
Since we are using recursion, a call stack up to height ‘N’ would be made. Hence the overall space complexity will be O(N).
All tags
Sort by
Interview problems
cpp soln
#include <bits/stdc++.h>
int solve(int n,vector<int>&arr)
{
if(n == 1)
{
return 0;
}
if(arr[n] != -1)
{
return arr[n];
}
int l = INT_MAX;
int m = INT_MAX;
if(n % 2 == 0)
{
l = solve(n / 2,arr);
}
if(n % 3 == 0)
{
m = solve(n / 3,arr);
}
int r = solve(n - 1,arr);
return arr[n] = min({l,m,r}) + 1;
}
int countStepsToOne(int n) {
vector<int>arr(n + 1,-1);
return solve(n,arr);
}Interview problems
Min Steps to one using DP
#include <bits/stdc++.h>
int countStepsToOne(int n) {
// Write your code here.
if(n==1){
return 0;
}
int*arr=new int[n+1];
arr[0]=0;
arr[1]=0;
for(int i=2;i<n+1;i++){
if(i%2==0 && i%3==0){
arr[i]=min(arr[i-1]+1,min(arr[i/2]+1,arr[i/3]+1));
}
else if(i%2==0){
arr[i]=min(1+arr[i-1],1+arr[i/2]);
}
else if(i%3==0){
arr[i]=min(arr[i-1]+1,arr[i/3]+1);
}
else{
arr[i]=1+arr[i-1];
}
}
return arr[n];
}Interview problems
dp approch
#include <bits/stdc++.h>
int countStepsToOne(int n) {
vector<int>dp(n+1,0);
dp[0]=0;
dp[1]=0;
dp[2]=1;
dp[3]=1;
for(int i=4;i<=n;i++)
{
int a=dp[i-1]+1;
int b=INT_MAX;
if(i%2==0)
{
b=dp[i/2]+1;
}
int c=INT_MAX;
if(i%3==0)
{
c=dp[i/3]+1;
}
dp[i]=min(a,min(b,c));
}
return dp[n];
}
Interview problems
problem in python compiler
problem in python compiler
Interview problems
Easy C++ Solution || Using DP
#include <bits/stdc++.h>
int countStepsToOne(int n) {
// Write your code here.
vector<int> dp(n+1);
dp[0]=0;
dp[1]=0;
dp[2]=1;
dp[3]=1;
for(int i =4;i<=n;i++)
{
int a = dp[i-1]+1;
int b = INT_MAX;
int c = INT_MAX;
if(i%2==0)
{
b = dp[i/2]+1;
}
if(i%3==0)
{
c = dp[i/3]+1;
}
dp[i]=min(a,min(b,c));
}
return dp[n];
}
Interview problems
Memoization and Iterative DP Code
#include <bits/stdc++.h>
int solve(int n, vector<int> &dp)
{
if(n==0)
return 0;
if(dp[n]!=0)
return dp[n];
int x=solve(n-1,dp);
int y=INT_MAX,z=INT_MAX;
if(n%2==0)
y=solve(n/2,dp);
if(n%3==0)
z=solve(n/3,dp);
return dp[n]=1+min(x,min(y,z));
}
int countStepsToOne(int n) {
vector<int> dp(n+1,0);
return solve(n,dp)-1;
}
Interview problems
Import Error!
I am getting import error. Anyone know how to resolve it?
Traceback (most recent call last): File runner.py , line 2, in from solution import countStepsToOne ImportError: No module named 'solution'
Interview problems
count to 1
why this problem is not working fine even after using memoization which take O(n) time only?
Interview problems
C++ | Memoization and Iterative DP Code | Easy to understand
#include <bits/stdc++.h>
// Memoization code
int countStepsToOne2(int n, int *dp) {
// Write your code here.
if(n<=1) return 0;
if(dp[n] != -1) return dp[n];
int x = countStepsToOne2(n-1, dp);
int y = INT_MAX, z=INT_MAX;
if(n%2==0)
y = countStepsToOne2(n/2, dp);
if(n%3==0)
z = countStepsToOne2(n/3, dp);
int ans = 1 + min(x, min(y,z));
dp[n] = ans;
return dp[n];
}
int countStepsToOne(int n) {
int *dp = new int[n+1];
for(int i=0; i<=n; i++) dp[i] = -1;
return countStepsToOne2(n,dp);
}
// iterative DP Code
int countStepsToOne(int n) {
int *dp = new int[n+1];
dp[1] = 0; // we know for n=1 ans is 0
for(int i=2; i<=n; i++){
int x = dp[i-1];
int y = INT_MAX;
int z = INT_MAX;
if(i%2 == 0 ) y = dp[i/2];
if(i%3 == 0 ) z = dp[i/3];
dp[i] = 1 + min(x, min(y,z));
}
int ans = dp[n];
delete [] dp;
return ans;
}
Interview problems
bottom top approach
is there a bottom top approach using loop(iteration) instead of recursion i tried but was getting wrong output. You can check the code suggest fixes
int minsteps3(int n){
int*ans=new int[n+1];
ans[1]=0;
for(int i=2;i<=n;i++){
int sub1=ans[i-1];
int div2=INT_MAX,div3=INT_MAX;
if(n%2==0){
div2=ans[i/2];
}
if(n%3==0){
div3=ans[i/3];
}
ans[i]=1+min(sub1,min(div2,div3));
}
return ans[n];
}
