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!
2 answers

Typical
int
(signed 32bit long) can store numbers only upto 2,147,483,647 (2**31  1
) and the number2958268876
exceeds this limit.You are using
long int
for calculation, so you should use it also for the elements ofvector
.In other words, the three
vector<int>
s should be replaced withvector<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.