Why am I getting this single output wrong?

Question

I'm new to competitive programming and I participated in Codeforces #653 in which I spent the whole time solving this problem and did not submit any code because of exceeded time limits or wrong answer for test cases.

I wanted to solve this problem - https://codeforces.com/contest/1374/problem/A

You are given three integers x,y and n. Your task is to find the maximum integer k such that 0 ≤k≤ n that k mod x=y, where mod is modulo operation. Many programming languages use percent operator % to implement it.

In other words, with given x,y and n you need to find the maximum possible integer from 0 to n that has the remainder y modulo x

You have to answer t independent test cases. It is guaranteed that such k exists for each test case.

I wrote this following code:

#include <stdio.h>

int main(){
    int i,t,j,k=0;
    int x[60000],y[60000],n[60000],prev[60000];
    scanf("%d",&t);
    for(i=0; i<t; i++){
        scanf("%d %d %d",&x[i],&y[i],&n[i]);
    }

    for(i=0; i<t; i++){
        for(j=0, k=0; j<n[i]; j++ , k++){
            if(j%x[i]==y[i]){
                prev[i]=k;
            }
        }
    }

    for(i=0; i<t; i++){
        printf("%d",prev[i]);
        printf("\n");
    }

    return 0;
}

Everything was working fine but for some test cases I'm getting different answers.

This was the expected output

12339
0
15
54306
999999995
185
999999998

and my output was this:

12339
0
5
54306
999999995
185
999999998

I did not understand why I got 5 instead of 15 keeping all the other outputs correct and also could anyone please help me to optimize the code, its taking too long to compile for large inputs.

Answer 1

For the 1st part of your question, why the answer is wrong - has been answered nicely by others already. For the 2nd part about efficiency, the solution doesn't need any extra loop except the loop for iterating over the test case.

The solution could be as easy as this:

k = n - ((n - y) % x)

For example:x = 7, y = 5, n = 12345. Then,

k = 12345 - ((12345 - 5) % 7)
  = 12339

This small piece of code could get you accepted:

#include <stdio.h>
int main()
{
    int t, x, y, n;
    scanf("%d", &t);
    while (t > 0) {
        scanf("%d %d %d", &x, &y, &n);
        printf("%d\n", n - ((n - y) % x));
        t--;
    }
}

Answer 2

the following proposed code:

1. cleanly compiles
2. performs the desired functionality
3. is very quick (could be made quicker via different I/O functions)

and now, the proposed code:

#include <stdio.h>

int main()
{
    int x;
    int y;
    int n;
 
    
    size_t t;
    scanf("%zu",&t);
    for( ; t; t-- )
    {
        scanf( "%d %d %d", &x, &y, &n );
        printf( "%d\n",  n - ((n - y) % x) );    
    }

    return 0;
}

Answer 3

The first part of this answer will explain what's wrong in your logic. The second part will contain a plot twist.

---

How to get the correct answer

1. As you have correctly been told in comments by @ErichKitzmueller your inner loop searches k values in the range [0-n[. In other words, if you are not familiar to my mathematical notation, you are not even considering the value n that is not included in your loop search, as you do for(j=0, k=0; j<n[i]; j++ , k++).
   For the record, [0-n[ means "range from to 0 to n including 0 and not including n.
2. If you have to search the maximum value satisfying a given requirement... why starting counting from 0? You just need starting from the right limit of the range and loop backwards. The first k you will find satisfying the condition will be your output, so you'll just need to save it and exit the inner loop.
   No need to find ALL the numbers satisfying the condition and overwrite them until the last is found (as you do).

The main loop of your solution would become something like that:

for(i=0; i<t; i++){
    int found = 0;
    for(k=n[i]; k>=0 && found==0; k--)
    {
        if( ( k % x[i] ) == y[i] )
        {
            prev[i] = k;
            found = 1;
        }
    }
}

---

The plot twist (the REAL solution)

The previous solution will lead to correct answers... anyway it will be rejected as it exceeds the time limit.

Actually, all these competitive coding problems are all based on asking for a problem that in some way is simpler than it looks. In other words, it's always possible to find a way (usually after a mathematical analysis) that have a lower computational complexity than the one of the first solution that comes to your mind.

In this case we have to think:

1. What is the reminder of a division? y = k%x = k - x*int(k/x)
2. When has this expression its max? When k=n. So y = k - x*int(n/x)
3. So k = x*int(n/x) + y
4. Finally, we want make sure that this number is lower than n. If it is, we subtract x

The code becomes something like this:

#include <stdio.h>

int main(){
    int i, t;
    int x[60000],y[60000],n[60000],k[60000];
    scanf("%d",&t);
    for(i=0; i<t; i++){
        scanf("%d %d %d",&x[i],&y[i],&n[i]);
    }

    for(i=0; i<t; i++){
        int div = n[i] / x[i]; // Since div is an integer, only the integer part of the division is stored to div
        k[i] = x[i] * div + y[i];
        if( k[i] > n[i] )
             k[i] -= x[i];
    }

    for(i=0; i<t; i++){
        printf("%d", k[i]);
        printf("\n");
    }

    return 0;
}

I've tested the solution on Codeforce, and it has been accepted.

Answer 4

The reason you were getting TLE was because your code was taking too long. As I can see n could be upto 10^9 and so a O(N) solution would easily time-out at such constraints. Add to that, the fact that your code would be given upto 5*10^4 test cases. So, for your code to work, it should be much faster than O(N) time complexity. I have explained a better approach below which would satisfy the given constraints.

---

Optimised Approach :

• For each test case, we are given x, y, n. And we have to find the largest number( let's say ans) between 0 to n such that ans%x = y.

1. Let's first find the remainder when we divide n by x. So, remainder = n%x. Now, if the remainder >= y, this means that we would have to reduce n such that it will leave a smaller remainder that is => a remainder equal to y. For this, we can simply reduce n by (remainder - y) amount.

   Example :

   For better understanding, lets see an example where

   x = 10, y = 5, n = 16. 
   

   In this case remainder = n%x = 6. Now remainder > y, so we can just reduce our n by (remainder - y), that is n now becomes 15. We see that 15%x = y and so that's our answer.

2. The other case we might get is remainder < y. In this case, we have to increase the remainder. But we can't increase n (since it is the upper limit). So, what we can instead do is subtract x from n. The remainder will still be same. But now we are allowed to increase n by some amount which results in remainder to be y. For that we simply increase n by an amount y - remainder, so that new remainder will be equal to y.

   Example :

   Let's consider example where

   x = 10, y = 5 and n = 24
   

   Here, remainder = n%x = 4. So remainder < y. We subtract x from n, so n becomes 14 but still n%x = 4, so remainder remains same. But, we now have the advantage that we can increase x so that remainder would be equal to y. Since our remainder is 1 less than required (y), we increase n by 1 (or y - remainder = 1). Thus, we have the answer = 15.

---

This approach has time complexity of O(1) which is far better than O(N) approach. I hope that you got the idea of the approach I was trying to explain. Below is the pseudocode for same -

Pseudocode

remainder = n%x
if (remainder >= y)   // Case 1
    return n - ( remainder - y ) as the answer
else                  // Case 2
    return ( n - x ) + ( y - remainder ) as the answer

Hope this helps !