Music Chairs problem implementation in C++

Question

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

_(x+m) % n, and since this can cause StackOverflow_ What? Do you mean integer overflow? — Scheff's Cat, Nov 05 '21 at 12:33
Are you aware that negative number `% n` result in negative numbers? (Not sure whether this is relevant...) — Scheff's Cat, Nov 05 '21 at 12:37
Thanks for your comment! This isn't relative since the problem constraints are all positive numbers, I thought about this but this isn't relative here :) — Mahmoud amr, Nov 05 '21 at 12:39
For `long long`, negative numbers are not excluded. (I didn't follow the link, and you didn't mention this in your question.) — Scheff's Cat, Nov 05 '21 at 12:40
The negative numbers shall be excluded cause this is a position problem :) And I edited the question to mention it :) — Mahmoud amr, Nov 05 '21 at 12:44
Stop using `long long` and use `unsigned long long` or `std::uint64_t` instead. The larger range of an `std::uint64_t` will prevent overflow from occurring. Also, your `position` calculation can be simplfied to `std::uint64_t position = ( x + m ) % n`. — WBuck, Nov 05 '21 at 13:21
I could have never imagined that this was actually what needed! I have to think about the constraints more often! Thank you so much! — Mahmoud amr, Nov 05 '21 at 14:08

Uduru · Answer 1 · 2022-05-03T02:09:14.560

1

Here's the problem:

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

When your program runs untill 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 occurs, 2^63 - 2 + 2^63 - 2 there is the overflow happening.

edited May 03 '22 at 02:09

answered Nov 05 '21 at 12:50

Uduru

511
2
10

score 1 · Answer 2 · answered Nov 05 '21 at 14:03

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.

Thank you, this is really helpful! – Mahmoud amr Nov 05 '21 at 14:10 — Mahmoud amr, Nov 05 '21 at 14:10

score 0 · Answer 3 · answered Nov 05 '21 at 14:09

0

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.

answered Nov 05 '21 at 14:09

Mahmoud amr

108
1
8

Music Chairs problem implementation in C++

3 Answers3