CODEWITHSUNDEEP
c++performanceoptimizationdynamic-programming
A.Gautam
A.Gautam

Reputation: 35

Why my program is failing for large input? more than 10^5

I am learning dynamic programming.i'm trying to solve the following question :

Problem Introduction : You are given a primitive calculator that can perform the following three operations with the current number x: multiply x by 2, multiply x by 3, or add 1 to x. Your goal is given a positive integer n, find the minimum number of operations needed to obtain the number n starting from the number 1.

Task Given an integer n, compute the minimum number of operations needed to obtain the number n starting from the number 1. The input consists of a single integer 1 < n < 10^6.

code

#include <iostream>
#include <climits>
#include<vector>
#include<list>
void primitive_calculator(int number)
{
    std::vector<int> min_steps(number+1,INT_MAX);
    std::list<int> path[number+1];
    min_steps[0]=0; min_steps[1]=0;
    path[0].push_back(0);
    path[1].push_back(1);
    for (int i=2 ; i<=number ; i++)
    {
        if(i%3==0)
        {
            if(min_steps[i/3] < min_steps[i])
            {
                min_steps[i]=min_steps[i/3]+1;
                path[i]=path[i/3];
                path[i].push_back(i);
            }
        }
        if(i%2==0)
        {
            if( min_steps[i/2] < min_steps[i])
            {
                min_steps[i]=min_steps[i/2]+1;
                path[i]=path[i/2];
                path[i].push_back(i);
            }
        }

        if( min_steps[i-1] < min_steps[i])
        {
             min_steps[i]=min_steps[i-1]+1;
             path[i]=path[i-1];
             path[i].push_back(i);
        }
    }
    std::cout<<min_steps[number]<<"\n";
    while(!path[number].empty())
    {
        std::cout<<path[number].front()<<" ";
        path[number].pop_front();
    }

}
int main()
{
    int number;
    std::cin>>number;
    primitive_calculator(number);
    return 0;
}

This program is failing for input number greater than 10^5 .Why so? And how can i improve the code?

Upvotes: 1

Views: 329

Answers (1)

Mine
Mine

Reputation: 4241

Your issue is on line:

std::list<int> path[number+1];
  1. It creates an array of std::list variable on stack, so if the number is huge, the stack overflows and gets segment fault.
  2. This code gets warning from GCC:

    warning: ISO C++ forbids variable length array 'path' [-Wvla]

  3. It is rejected by clang as well:

    error: variable length array of non-POD element type 'std::list'

So do NOT define huge variables on stack.

Instead, what you should do is use std::vector, e.g. change the line to:

std::vector<std::list<int>> path(number+1);

Then your problem is solved.

Upvotes: 1

Related Questions