-2

I'm trying to find a solution to a task. My code passed only 3 autotests. I checked that the solution satisfies the max/min cases. Probably there are situations when my code is not valid.

Description of the task: Find the remainder after dividing the sum of two integers by the third.

Input: The first line of input contains two integers A and B (-10^18 ≤ A, B ≤ 10^18). The second line contains an integer C (2 ≤ C 10^9).

Output: Print the remainder of dividing A + B by C.

My code:

#include <iostream>
// int64_t
#include <cstdint>
#include <stdint.h>

// #include <math.h>

// 3 tests passed
int main() {
    int64_t a, b, c;
    std::cin >> a >> b >> c;

    // a = pow(-10, 18);
    // b = pow(-10, 18);
    // // c = pow(10, 9);
    // c = 3;

    // c = pow(10, 18) - 20;
    // c = 1000000000000000000 + 1;
    // c = 1000000000000000000 + 2;


    // std::cout << a << std::endl;
    // std::cout << b << std::endl;
    // std::cout << c << std::endl;

    std::cout << (a + b) % c << std::endl;

    return 0;
}
Kuznetsov-M
  • 346
  • 7
  • 18
  • Guess it is already be answered [here](https://math.stackexchange.com/questions/3122038/remainders-of-two-integers-when-divided-by-another-integer-n) – Zenek Jul 25 '22 at 08:48
  • 3
    what test case fails? In the code in comments you are using `pow` which can easily produce wrong/unexpected results when used with integers. `pow` is not made to be used with integers. – 463035818_is_not_an_ai Jul 25 '22 at 08:52
  • The range of an `int64_t` is +/- ~9.2e18 ... so why not just `(A + B) % C` ? – Adrian Mole Jul 25 '22 at 08:52
  • @Zenek that quesitons is about whether `a % b + c%b == (a+c)%b` holds. Not relevant here. – 463035818_is_not_an_ai Jul 25 '22 at 08:54
  • is this the code that fails? Or is it the code in comments? Also you should include the input that leads to wrong output. If you don't know what fails you cannot fix it – 463035818_is_not_an_ai Jul 25 '22 at 08:55
  • 1
    Please read about [modular arithmetic](https://en.wikipedia.org/wiki/Modular_arithmetic)!!! – Marek R Jul 25 '22 at 08:57
  • 2
    btw `pow(-10, 18);` is the same as `pow(10, 18);` I think you wanted `-pow(10,18);`, but consider comment above, `std::pow` is not for integers – 463035818_is_not_an_ai Jul 25 '22 at 08:58
  • the code looks fine. Its not clear what you are asking – 463035818_is_not_an_ai Jul 25 '22 at 09:03
  • 2
    Do you have an example of the failed tests? It may be related to https://stackoverflow.com/questions/13683563/whats-the-difference-between-mod-and-remainder – Bob__ Jul 25 '22 at 09:06
  • 2
    Please provide link to a task. Note in case of negative values there is ambiguity how modulo should be calculated. C++ standard says integer division is rounded toward to zero, but in modular arithmetic integer division is rounded down. This leads to different results of modulo for negative values. – Marek R Jul 25 '22 at 09:09
  • 1
    @Marek But, in C++, `%` is actually the *remainder* operator, not the modulo operator. – Adrian Mole Jul 25 '22 at 09:13
  • 1
    @AdrianMole Ok I used wrong wording. – Marek R Jul 25 '22 at 09:19
  • Thank you for the clarification! I don't have test cases data. I just send the code to the system and get the number of passed tests. Commented out code - I used to test myself. Thanks for pointing out the fact that `std::pow()` is not for integers. – Kuznetsov-M Jul 25 '22 at 21:38

3 Answers3

3

Please note that in C++ reminder for negative values:

  • was implementation defined until C++11
  • integer division is rounded towards zero since C++11 which makes reminder negative sometimes.

Now most probably in your task modulo result should be always in range <0, C) (or written differently <0, C - 1>). So to handle cases where A + B is negative, you have to take this into account that reminder may be negative.

So your code can look like this:

nt main() {
    int64_t a, b, c;
    std::cin >> a >> b >> c;
    std::cout << (a + b) % c + ((a + b) % c < 0) * c << '\n';

    return 0;
}

Which basically adds c to result if result is negative and makes result inside required range. (assuming c is positive).

Marek R
  • 32,568
  • 6
  • 55
  • 140
  • Thank you! You really understood my problem correctly. Previously, I used the operator only for positive numbers, but now I fell for the intricacies of working with a negative number. – Kuznetsov-M Jul 26 '22 at 09:03
  • 1
    Just to clarify. C++ is close to hardware and must support many platforms. So "implementation defined" was used initially to cover strange early processors which were doing that in different way. After processors design of division unified and support for older platforms was no longer needed, more strict rule has been introduced into a C++11 standard. Note other languages may enforce other rules. – Marek R Jul 26 '22 at 09:13
  • Yes, I checked different cases for Python and was surprised by the difference in results! – Kuznetsov-M Jul 26 '22 at 09:16
2

Modulo operation in C++ uses truncated division, i.e., the result of x % y is negative if x is negative.

To obtain a non-negative result congruent to (a + b) % c, you can use ((a + b) % c + c) % c.

Alwyn
  • 56
  • 4
  • stilling my comment ;). – Marek R Jul 25 '22 at 09:16
  • @MarekR Sorry, this is my first answer on stackoverflow. Your comment has not been posted when I started writing this answer. Should I delete it? – Alwyn Jul 25 '22 at 09:21
  • @MarekR where? I see your comment with the same link but not with the same contents. – YurkoFlisk Jul 26 '22 at 01:25
  • 1
    @YurkoFlisk Actually the links are different (https://en.wikipedia.org/wiki/Modular_arithmetic and https://en.wikipedia.org/wiki/Modulo_operation). Moreover, the first link has more emphasis on math, while the second link describes various methods used in programming languages to calculate the remainder (truncated divison, floored division, etc.). – Alwyn Jul 26 '22 at 10:59
  • 1
    Yes, I see, thanks. Then I even less understand what Marek meant by "stilling" his comment. Also, your answer was the first, so you could not steal from his or anyones answer either (and you have different formula for non-negagivizing modulo operation result which is easier, though maybe less efficient due to additional %). Anyway, I don't think your answer should be deleted. – YurkoFlisk Jul 26 '22 at 11:23
  • I think stilling means satisfying/fulfilling open issues from his comment to his satisfaction (instead of stealing). – Sebastian Jul 26 '22 at 12:08
1

I believe the point of the exercise is to handle overflows and underflow by realizing that the remainder of the sum is the sum of the remainder modulo c.

That's what my magic-8 ball says anyway. If that's not the solution the provide the failed input and expected and actual output.

Goswin von Brederlow
  • 11,875
  • 2
  • 24
  • 42