Music Chairs problem implementation in C-CodePudding

I am currently practicing algorithms and DS. I have stumbled upon a question that I can't figure out how to solve. So the question's link is there:

In summary, it says that there is a number of chairs in a circle, and the position of the person (relative to a certain chair), and how many M movements he should make.

So the input is as following:

3 integer numbers N, M, X , The number of chairs, the number of times the boy should move and the first chair he will start from respectively ( 1 ≤ X ≤ N < 2^63 , 0 ≤ M < 2^63 )

So, what have I done so far? I thought about the following:

So I thought that the relative position after M movements is (x m) % n, and since this can cause Integer overflow, I have done it like that, ((x%n) (m%n)) % n. I have figured out that if the person has reached the last index of chair, it will be 0 so I handled that. However, it passes only 2 tests. I don't need any code to be written, I want to directed in the right way of thinking. Here is my code so far:

#include <iostream>

using namespace std;

int main() {

    long long n, m, x;

    cin >> n >> m >> x;



    // After each move, he reaches (X 1).

    // X, N chairs. 

    // ((X % N)   (M % N)) % N; 

    // Odd conideration.
    if ( m % 2 == 1) {
        m  = 1;
    }

    long long position = (x % n   m % n) % n;
    if (position == 0) {
        position = n;
    }
    cout << position;

    return 0;
}

CodePudding user response：

Here's the problem:

Say the value of N is 2^63-1, and X and M are all 2^63 - 2.

When your program runs to the ((X % N) (M % N)) % N part, X%N evaluates into 2^63 - 2 (not changed), and so does M%N. Then, the addition between the two results occur: 2^63 - 2 2^63 - 2, there is the overflow happening.

CodePudding user response：

If the question required specific error handling, it should have stated so (so don't feel bad).

In every real-world project, there should be a standard to dictate what to do with weird input. Do you throw? Do you output a warning? If so, does it have to be translated to the system language?

In the absence of such instructions I would err toward excluding these values after reading them. Print an error to std::cerr (or throw an exception). Do this as close to where you read them as possible.
For overflow detection, you can use the methods described here. Some may disagree, and for a lab-exercise, it's probably not important. However, there is a saying in computing "Garbage in == Garbage out". It's a good habit to check for garbage before processing, rather than attempting to "recycle" garbage as you process.

CodePudding user response：

After the comment of @WBuck, the answer is actually rather easy which is to change the long long to unsigned because there are no negative numbers and therefore, increase the MAX VALUE of long long (when using unsigned).

Thank you so much.