Getting negative outputs for large enough inputs in vector

Question

I was writing an algorithm for a problem that goes as follows:

Consider an algorithm that takes as input a positive integer n. If n is even, the algorithm divides it by two, and if n is odd, the algorithm multiplies it by three and adds one. The algorithm repeats this until n is one. For example, the sequence for n=3 is as follows: 3→10→5→16→8→4→2→1

Original question can be found here

The algorithm that I wrote for it is as follows:

#include <iostream>
#include<vector>
using namespace std;
void check(long int n, vector<int> &arr);
int main(){
    long int n;
    cin>>n;
    vector<int> arr; //Vector to store values of n
    check(n,arr);
    for(unsigned int i=0;i<arr.size();i++){
      cout<<arr[i]<<' ';    //Printing the final values of n
    }
    return 0;
}

void check(long int n,vector<int> &arr){
    arr.push_back(n);
    if(n%2==0){   //if n is even
      n=n/2;
      if(n!=1){
        check(n,arr);
      }
      else if(n==1){
        arr.push_back(1);
      }
    }
    else{         //if n is odd
      n=(n*3)+1;
      if(n!=1){
        check(n,arr);
      }
      else if(n==1){
        arr.push_back(1);
      }
    }
    return;
}

My solution is working perfectly for smaller values of n. However when n becomes large enough- especially somewhere around 138367(this was the first test case when the answer got wrong according to the compiler), the values of n printed at the end also start to include some 'negative numbers', which is somewhat unreasonable.

For instance, if I input n=986089625, in the beginning, the next number that follows it in the end result is -1336698420. While the correct number should be 2958268876. Surprisingly the next number that follows is correct, but at certain (random) intervals, the numbers are becoming negative.

I know the algorithm can be simplified further, but I'm not able to understand the problem with this one. I assume there's something subtle that I'm missing!

Answer 1

You can see how this works with this simple example

#include <limits.h>
#include <iostream>

int main()
{
    int n = INT_MAX;
    std::cout << "n=" << n << '\n';
    std::cout << "n+1=" << n + 1 << '\n';

    unsigned m = UINT_MAX;
    std::cout << "m=" << m << '\n';
    std::cout << "m+1=" << m + 1 << '\n';
}

giving

n=2147483647
n+1=-2147483648
m=4294967295
m+1=0

When the limit is reached, a wrap around occurs to either INT_MIN or zero, depending on the signedness of the integer type.

The same happens also in the opposite direction of course, wrapping from INT_MIN to INT_MAX or from zero to UINT_MAX.