1

I am trying to solve a programming problem in c++ (version : (MinGW.org GCC Build-2) 9.2.0)
I am using modulo operator to give answer in int range but for 6 ,it is giving me -ve answer
why is this happening??
my code :

#include <cmath>
#include <iostream>

using namespace std;

int balancedBTs(int h) {
    if (h <= 1) return 1;
    
    int x = balancedBTs(h - 1);
    int y = balancedBTs(h - 2);
    int mod = (int)(pow(10, 9) + 7);
    
    int temp1 = (int)(((long)(x) * x) % mod);
    int temp2 = (int)((2 * (long)(x) * y) % mod);

    int ans = (temp1 + temp2) % mod;
    
    return ans;
}
int main()
{
    int h;
    cin >> h;
    cout << balancedBTs(h) << endl;
    return 0;
}

output : enter image description here

Ayush Yadav
  • 376
  • 2
  • 11
  • 3
    There's no output in your example so it's hard to know where those values came from. What are the values for `x` and `y` that replicate the issue? Consider putting together a [mcve]. – Retired Ninja Dec 13 '21 at 21:38
  • 2
    If `(temp1 + temp2)` is negative, then `%` will return negative. – ChrisMM Dec 13 '21 at 21:40
  • Possibly related: https://stackoverflow.com/questions/11630321/why-does-c-output-negative-numbers-when-using-modulo – Drew Dormann Dec 13 '21 at 21:41
  • @Retired Ninja edited the question to reproduce the issue – Ayush Yadav Dec 13 '21 at 21:47
  • thats why i have first taken their modulus in temp1 and temp2 @ChrisMM – Ayush Yadav Dec 13 '21 at 21:52
  • 1
    To expand on what Retired Ninja said: your code is about 10x more complicated than it needs to be to demonstrate the problem because it uses a recursive function and `cin`, and you didn't tell us what number you typed on the standard input. A true MRE would be something like: `int main() { return -5 % 4; }` and you would ask why it returns -1 instead of 3. And the answer would be that `%` is designed to work that way. – David Grayson Dec 13 '21 at 22:05
  • 1
    Assuming you're on Windows where `int` and `long` are both 32-bits. If you replace `long` with `int64_t` the result is 878720798. – Retired Ninja Dec 13 '21 at 22:14
  • The `%` operator does **not* compute a modulus. It computes a remainder, and the sightedness of the remainder depends on whether division involving negative numbers rounds down or toward zero. For example,if `-5/2` is `-2`, then `-5%2` has to be `-1`. If `-5/2` is `-3`, then `-5%2` has to be `+1`, – Pete Becker Dec 13 '21 at 22:23
  • In any event, your calculation is probably overflowing an `int` - which produces undefined behaviour. Without trying to track through the recursion, it seems pretty likely that can happen. One possible result of that is a value you expect to be positive turns out to be negative - in which case `%` will produce a negative result. – Peter Dec 13 '21 at 23:19

1 Answers1

1

The code makes two implicit assumptions:

  • int is at least 32 bit (otherwise the 1,000,000,007 for mod will not fit)
  • long is bigger than int (to avoid overflows in the multiplication)

Neither of these assumptions are guarantee by the standard https://en.cppreference.com/w/cpp/language/types

I don't have access to the same platform in the question, but I can reproduce the output exactly if I remove the cast to long in the assignment of temp1 and temp2 (effectively simulating a platform were sizeof int and long is both 4).

You can verify if the second assumptions hold in your platform checking the sizeof(int) and sizeof(long).

Alessandro Teruzzi
  • 3,918
  • 1
  • 27
  • 41