# Getting negative outputs for large enough inputs in vector

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!

Typical `int` (signed 32-bit long) can store numbers only upto 2,147,483,647 (`2**31 - 1`) and the number `2958268876` exceeds this limit.

You are using `long int` for calculation, so you should use it also for the elements of `vector`.

In other words, the three `vector<int>`s should be replaced with `vector<long int>`.

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.