 # Chef and step game

Practice

Author: Aryan KD
Tester: Aryan KD
Editorialist: Aryan KD

# DIFFICULTY:

CAKEWALK, SIMPLE, EASY.

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

# 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;
}