 # ISPAR-Editorial

Setter: kryptonix171
Tester: Abhinav Sharma, Lavish Gupta
Editorialist: Devendra Singh

1305

None

# PROBLEM:

Ashish gave you two positive integers N and K . You have a circular sequence 1, 2, 3, 4, 5.....N-1, N . That means the number after N is 1 .

In one operation you remove the kth element towards right starting from the position of the smallest element in sequence at that time. After N-1 operations, only one element remains in the sequence.

Tell the parity of the last element left in the sequence.

# EXPLANATION:

There are three cases:

Case 1 K = 1: All numbers starting from 1 to N-1 will be deleted. N is the last remaining element. The parity of N is the answer is this case.
Case 2 K=2: All numbers starting from 2 to N will be deleted. 1 is the last remaining element. Answer in this case is `ODD`.
Case 3 K>=3 :All numbers from K to N will be deleted first. Now numbers from 1 to K-1 remain in the list. K^{th} number from 1 is 1. 1 will be deleted. Now numbers from 2 to K-1 are present. Now K^{th} number from 2 is 3.
Since the size of the list decreases by 1 after each iteration and number of numbers till the next odd number also decreases by 1. Therefore only odd numbers starting from 1 are deleted till there are no odd numbers left in the list. Hence only an even number must be left in the end. Answer for this case is `EVEN`.

# TIME COMPLEXITY:

O(1) for each test case.

# SOLUTION:

Setter's Solution
``````#include <bits/stdc++.h>
#define int long long int
#define debug cout<<"K"
#define mod 1000000007

using namespace std;

int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t>0)
{
int n,k;
cin>>n>>k;
if((k==2)||(n%2==1&&k==1))
cout<<"ODD\n";
else
cout<<"EVEN\n";
t--;
}
return 0;
}

``````
Editorialist's solution
``````#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
void sol(void)
{
ll n, k;
cin >> n >> k;
if (k == 1)
{
if (n % 2)
cout << "ODD\n";
else
cout << "EVEN\n";
}
else if (k == 2)
{
cout << "ODD\n";
}
else
{
cout << "EVEN\n";
}
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int test = 1;
cin >> test;
while (test--)
sol();
}

``````

Test Case:
1
1 5
EVEN
but it should be ODD

2 Likes

K has to be less than or equal to N

5 Likes

I am dumb.( in general )

Exactly what I was thinking!

1 Like