# DATATYPE - Editorial

Setter: Utkarsh Gupta
Tester: Tejas Pandey, Abhinav Sharma
Editorialist: Kanhaiya Mohan

Cakewalk

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


I’m getting a WA if I give something like this
(X % N) - 1

(12 % 11) - 1 = 0, which satisfies the scenario

Could not identify on what TC it fails.

Take any test case where X=N. Your code would give -1 output.

#Why I am getting Wrong answer
#Where my code is fails.

testcases = int(input())
for i in range(testcases):
#n,x=[int(i) for i in input().split()]
n,x=map(int,input().split())
if x <= n:
print(x%n)
else:
print((x%n)-1)

Sorry. I didn’t share my full code. It was like this

if(X > N)
{
Print((X % N) - 1)
}
else
{
Print(X)
}

Take X = 2 \cdot N. Your code gives -1 whenever X is a multiple of N.

Thanks. It helps

Hi, Can someone please tell me where will my code fail please?

Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-->0)
{
int n = sc.nextInt();
int x = sc.nextInt();
if(x<=n)
{
System.out.println(x);
}
else{

System.out.println(x-n-1);
}
}
1 Like

I am getting WA after writing this code. Could you please tell me the error.
#include
using namespace std;

int main() {
int t;
cin>>t;
while(t>0)
{
int n,x;
cin>>n>>x;
int ans=0;
if(x>0 && x<=n)
{
ans=x;
}
else{
if(x==n+1){ ans=0;}
if(x>n+1){ans=x-n-1;}
}
cout<<ans<<endl;
t–;
}
return 0;
}

Yeah, same confusion

Hi, I am passing the first test, but have no idea why it is failing the second test?

https://www.codechef.com/viewsolution/58055785