PROBLEM LINK:
Author: Bhupat Jangid
Tester: Dheeraj Bhagchandani
Editorialist: Bhupat Jangid
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Bit Manipulation
PROBLEM:
Ram plays a strange number game. There are N blocks numbered from 1 to N. At the beginning of game ram is at Nth block and he wants to come at 1st block to win the game in minimum number of moves.
In one move, he can perform one of the following operations
- If the number is power of two then divide it by 2 and that becomes the new position of Ram
- If not then reduce it by the next lower number which is power of 2 which is Ram’s new position
EXPLANATION:
Let we have a number and we have to check if it is power of 2 then we divide it by 2 otherwise subtract it by next lower number which is power of two till number become 1.
For example if we have 24 then we perform following operations and count number of operations.
let number is 24(binary repersentation is 11000)
- 24 is not power of 2 so subtract it by 16. 24-16=8(binary representation of 8 = 1000 which is equal to changing leftmost set bit into 0)
- 8 is power of 2 so divide it by 2 (8/2=4).
- 4 is also power of 2 so divide it by 2 (4/2=2).
- 2 is power of 2 so divide it by 2(2/2=1).
24 → 8 → 4 → 2-> 1.
so we perform 4 operations.
SOLUTIONS:
Setter's Solution
for y in range(int(input())):
n=int(input())
s=bin(n)[2:]
cnt=0
while s!='1':
cnt+=1
if s.count('1')>1:
ans=''
foo=0
for i in s[1:]:
if foo==1:
ans+=i
else:
if i=='1':
foo=1
ans='1'
s=ans
else:
s=s[2:]
s='1'+s
print(cnt)
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ll long long
#define M 1000000007
#define MM 998244353
#define fr first
#define sc second
#define vc vector
#define pii pair<int,int>
#define psi pair<string,int>
int main(){
ios_base::sync_with_stdio(false);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int t;
cin>> t;
while(t--){
ll n;
cin>>n;
ll step = 0;
while(n != 1){
step++;
int y=log2(n);
double x=log2(n);
if(x==y)n/=2;
else n-=pow(2,y);
}
cout<<step<<endl;
}
}