Author: Abhishek Mishra
Tester: VIPUL JAIN
Editorial: Abhishek Mishra
Difficulty:
Easy.
Prerequisite:
Loops, conditional statements, mathematics, deques
Explanation & Algorithm:
We can solve this problem with multiple approaches using deque or simple while loops.
Problem states that in a range between m and n we have to eliminate all the possible k numbers from first and last of the given range and print the remaining number.
Now in first approach we can use to variable in which first is minimum range i.e. 0 and another is maximum range i.e. n. We have to run a loop iterating from both front and end remove k elements using a separate loop for both side and store the last element and return it.
Another approach could be using deques. In deques we pop k elements from front and back. And return the remaining elements of the queue.
Another simple approach and most efficient approach could be using mathematics (division rule). The number remaining last would be in case if k is odd multiple of n and divisible by k then last remaining number would be (k(q/2 +1))+1)* and if not divisible by k then we subtract 1 from previous answer as it will be already included and if k is even multiple and divisible by k then remaining number would be (k*q/2 + r) and if not divisible then increment by 1.
Time Complexity:
O(n*logn)
Space Complexity :
O(n)
Solution:
Setter's Code
#include<bits/stdc++.h>
using namespace std;
int main(){
int t; cin >> t;
while (t–){
int n; cin >> n;
int k; cin >> k;
int last = 1;
int i = 1, j = n;
while (i <= j) {
int temp = k;
while (temp-- && i <= j) {
last = i;
i++;
}
temp = k;
while (temp-- && i <= j) {
last = j;
j--;
}
}
cout << last << endl;
}
}
Tester's Code
#include<bits/stdc++.h>
using namespace std;
int main(){
int t;
cin>>t;
for(int i=0;i<t;i++){
int n,k;
cin>>n>>k;
int r=n%k;
int q=n/k;
int ans=0;
if (q%2!=0){
ans=(k*(q/2 +1))+1;
if (r==0){
ans–;
}
}
else {
ans=k*q/2 + r;
if (r==0){
ans++;
}
}
cout<<ans<<endl;
}
}