DATATYPE - Editorial

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

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.
#Please provide a teastcase.

cook your dish here

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

Can someone please advise? Many thanks