This is my code for finding the longest collatz sequence between 1 and n. And obviously for t test cases. Here, I have also used memoization and thus malloced 'v'. But as the input to the function cycles(int x) goes beyond 4254, ie. 4255, there is something peculiar happening. The function is being input a number 6053452 instead of 4255. And due to this, the program segfaults, as we have only allocated space for 5000000 integers. What have I done wrong?

Note: The program works pleasantly till n = 4254! (not the factorial)

#include <iostream>
#include <cstdlib>

    #define RANGE 5000000
    using namespace std;

    int *v = (int*)malloc(sizeof(int)*RANGE);

    int cycles(int x){
        int c = 1;
        
        
        while(x!=1){
            
            if(v[x]!=0){
                c = c   v[x];
                break;
            }
            
            if(x%2){
                x = 3*x   1;
            }else{
                x/=2;
            }
            c  ;
        }
        
        v[x] = c;
        
        return c;
        
    }


    void solve(int n){
        
        int mx = 0;
        int mx_cnt = 0;
        int c;
        
        for(int i=1;i<=n;i  ){
            c = cycles(i);
            if(c >= mx_cnt){
                mx = i;
                mx_cnt = c;
            }
            
        }
        
        cout << mx << endl;
        
    }

    int main(){
        
        
        int t,n;

        cin >> t;

        while(t--){

            cin >> n;

            solve(n);


        }
        

        
        return 0;
    }

CodePudding user response：

The main problem that you observe is that you access v out of bounds. You also use the mallocd memory uninitialized which makes the program have another problem. Both results in undefined behavior.

int cycles(int x){
    int c = 1;
        
    while(x!=1){
        if(v[x]!=0){               // <-    x >= RANGE
            c = c   v[x];
            break;
        }
        // ...

To find problems like this I suggest using a vector instead and, at least when developing the program, use the vector::at() bounds checking member function.

std::vector<int> v(RANGE);

int cycles(int x){
    int c = 1;
        
    while(x!=1){
        // The below use of `v.at(x)` may result in an exception like:
        // what():  vector::_M_range_check:
        //          __n (which is 6053452) >= this->size() (which is 5000000)

        if(v.at(x)!=0){  
            c = c   v[x];
            break;
        }
        // ...

To catch the exception, you could rewrite main like this:

#include <exception>

int main() {
    int t, n;
    try {
        std::cin >> t;
        while(t--) {
            cin >> n;
            solve(n);
        }
    } catch(const std::exception& ex) {
        std::cout << "Exception: " << ex.what() << '\n';
    }
}

If you have a modern 64 bit computer, allocating a lot more shouldn't be a problem. I did this and it solved 4255 fine:

constexpr size_t RANGE = 6810137;

CodePudding user response：

v points to a malloced array and malloc does no initialization. You have if(v[x]!=0) and c = c v[x]; operating on an uninitialized variables. Embrace C and replace the malloced array with a std::vector. vector initializes its contents.

This might not be the only bug, just the most obvious.

Correction based on point raised by molbdnilo in the comments: I reached for too complicated a tool. int v[RANGE]; will allocate and zero-initialize the array. Since the array never changes size, a vector's dynamic array is unnecessary. Use std::array<int, RANGE> v; and you'll have a zero-initialized fixed-size array and still get useful functions like at for debugging.