PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Setter: Utkarsh Gupta
Tester: Tejas Pandey, Abhinav Sharma
Editorialist: Kanhaiya Mohan
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Chef is using a new data type that can store values only in the range 0 to N (both inclusive). If a value greater than N is received, it is cyclically converted to fit in the range 0 to N. Given X, determine what will be the actual value in memory after storing X in this new data type.
QUICK EXPLANATION:
- The answer is X \% (N+1).
EXPLANATION:
Brute Force
Simply translate the problem statement into error-free code. Since the values of N and X are very small, the solution passes within the time limit.
We keep a counter to store our current answer. Initialise this counter with -1. Run a loop from 0 to X (inclusive) and increment the counter in each iteration. Each time the counter hits the value N+1, reset its value to 0.
This approach has a time complexity of O(X) per testcase.
Optimised Approach
Observe that the value in this new data type always lies in the range 0 to N. All greater values are cyclically converted to this range. The new value of X is the remainder when X is divided by (N+1).
Thus, the answer is simply X \% (N+1). The complexity for this is O(1) per testcase.
TIME COMPLEXITY:
The time complexity is O(1) per test case.
SOLUTION:
Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
using namespace std;
void solve()
{
int n,x;
cin>>n>>x;
cout<<(x%(n+1))<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int t;
cin>>t;
while(t--)
solve();
}
Editorialist's Solution
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;
while(t--){
int n, x;
cin>>n>>x;
int cnt = -1;
for(int i = 0; i<=x; i++){
cnt++;
if(cnt==n+1){
cnt = 0;
}
}
cout<<cnt<<endl;
}
return 0;
}