0

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!

1

2 Answers 2

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.

1

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>.

4
  • long int can also be 32-bits (as it is on Windows/MSVC). Mar 18, 2021 at 16:29
  • @AdrianMole But it looks working in the OP's environment because "Surprisingly the next number that follows is correct"
    – MikeCAT
    Mar 18, 2021 at 16:30
  • Maybe. But calculations should be done in maximum size (long long int) and the result checked against INT_MAX or LONG_MAX before being assigned to the vector element. Mar 18, 2021 at 16:32
  • @MikeCAT Thanks! I made both the corrections, and it works now.
    – Harsh
    Mar 18, 2021 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.