Author: Aryan KD
Tester: Aryan KD
Editorialist: Aryan KD
DIFFICULTY:
CAKEWALK, SIMPLE, EASY.
PREREQUISITES:
Math .
PROBLEM:
Chef is alone at home and he is now going to play a game in this game there is some steps that numbers from 0 to N step. at the starting of game chef is on last step that is Nth step . and the goal of chef is to reach the 00th step at the end of game with minimum number of jump.
- Rule
- If the given steps number is even then chef is allowed to jump N/2 steps below at maximum
- If the given step number is odd chef allowed to jump 1 step below.
Now find the minimum number of steps required to win the game from given input . if chef is not win the game then print â1 else print minimum number of steps required to win the game .
EXPLANATION:
You simply given N number you have to take some steps according to given rule
rule is state that if the given number is even then chef can take N/2 step below and if the given number is odd chef can take 1 step below we have to count every step and print it
we have to iterate a loop until N become 0
so lets take an example suppose given number is 5
now chef can take 1 step below now N become 4
now it is even and chef can take N/2 step now n became 2 still it is even now chef can take n/2 step now n become 1 now chef can take 1 step below and the number of step is 4
hence answer is 4
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
void testcase()
{
long long int n;
cin>>n;
long long int cnt=0;
while(n!=0){
if(n%2==0){
n=n/2;
cnt++;
}
else{
n=n-1;
cnt++;
}
}
cout<<cnt;
}
int main()
{
int t;
cin>>t;
while(tâ)
{
testcase();
cout<<endl;
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
void testcase()
{
long long int n;
cin>>n;
long long int cnt=0;
while(n!=0){
if(n%2==0){
n=n/2;
cnt++;
}
else{
n=n-1;
cnt++;
}
}
cout<<cnt;
}
int main()
{
int t;
cin>>t;
while(tâ)
{
testcase();
cout<<endl;
}
return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
using namespace std;
void testcase()
{
long long int n;
cin>>n;
long long int cnt=0;
while(n!=0){
if(n%2==0){
n=n/2;
cnt++;
}
else{
n=n-1;
cnt++;
}
}
cout<<cnt;
}
int main()
{
int t;
cin>>t;
while(tâ)
{
testcase();
cout<<endl;
}
return 0;
}