 # REACHZERO - Editorial

Setter: Rahul Kumar
Tester: Rahul Kumar
Editorialist: Rahul Kumar

DIFFICULTY:
SIMPLE - SIMPLE

PROBLEM:
Given an integer N. Chef has to perform the following operation on N, in one move:

• Choose an integer K, 1 \lt K \leq N.
• Make N=N−K.

If it is not possible to get N=0 then print “−1” else print the maximum number of moves to achieve this.

EXPLANATION:
Each number can be represented as some of 2’s and 3’s. To maximise the number of steps we choose all 2’s for a even N and one 3 and rest 2’s for odd N. SO its every time N/2.
For N = 1, its impossible so -1.

TIME COMPLEXITY:
O(1)

SOLUTION:

#include<bits/stdc++.h>
using namespace std;
#define int long long int

int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
if(n==1)
cout<<"-1\n";
else
cout<<n/2<<"\n";
}
}


Hey, don’t you think there is a flaw in the problem statement?

It was mentioned to choose an Integer K, 1\lt K\lt N. But in the sample, when N became 2 at the end of the first move, you cannot take K = 2 in the second move since K < N is not satisfied.

1 Like

Hey, it was intended 1<k<=N … otherwise it will never be possible to reach zero… sorry for the inconvenience… thanks for pointing out…will update this

1 Like