Primitive calculator - Dynamic Programming

Question

So, the problem task is:

Given an integer , compute the minimum number of operations needed to obtain the number starting from the number 1.

And here is my code for doing this:

#include<bits/stdc++.h>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int> v(n+1);
    for(int i = 0; i < n+1; i++)
    {
        v[i] = 0;
    }
    v[1] = 1;
    for(int i = 1; i <= v.size() - 1; i++)
    {
        if((v[i + 1] == 0) || (v[i + 1] > v[i] + 1))
        {
            v[i + 1] = v[i] + 1;
        }
        if((2*i <= n) && (v[2*i] == 0 || v[2*i] > v[i] + 1))
        {
            v[2*i] = v[i] + 1;
        }
        if((3*i <= n) && (v[3*i] == 0 || v[3*i] > v[i] + 1))
        {
            v[3*i] = v[i] + 1;
        }
    }
    vector<int> solution;
    while(n > 1)
    {
        solution.push_back(n);
        if(v[n - 1] == v[n] - 1)
        {
            n = n-1;
        }
        else if(n%2 == 0 && v[n/2] == v[n] - 1)
        {
            n = n/2;
        }
        else if(n%3 == 0 && v[n/3] == v[n] - 1)
        {
            n = n/3;
        }
    }
    solution.push_back(1);
    reverse(solution.begin(), solution.end());
    for(size_t k = 0; k < solution.size(); k++)
    {
        cout << solution[k] << ' ';
    }
}

I am not able to figure out any mistake. This is not giving me any output. It will be great if you could help me out. Input and output have been shown here:

Input:

Output:

3
1 2 4 5

So, basically you have to give number of operations needed to do this task for n and provide the sequence of intermediate numbers.

Did you debug? https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ — Yunnosch, Jul 08 '20 at 05:42
What operations are valid? And before coding it in C++, what algorithm do you plan to use? — Serge Ballesta, Jul 08 '20 at 05:49
Unrelated: `i <= v.size() - 1` can be expressed more readable as `i < v.size()` — Lukas-T, Jul 08 '20 at 05:51
@Yunnosch Yes, I tried debugging but could not find my fault. — baapcoder_, Jul 08 '20 at 05:56
Side note: `std::vector(n+1, 0)` initalises the vector to all 0 and you don't need the loop... — Aconcagua, Jul 08 '20 at 05:57
@SergeBallesta I want to use dynamic programming for this, greedy will not provide me correct answer. — baapcoder_, Jul 08 '20 at 05:58
Please don't ever [`include `](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). — Aconcagua, Jul 08 '20 at 05:58
@imgeek_ You can't be using a debugger correctly, your code has immediate and obvious errors. — john, Jul 08 '20 at 05:59
@Aconcagua But why is this, I am kinda new to cpp. It will be great if you could explain a bit. — baapcoder_, Jul 08 '20 at 05:59
@imgeek_ It is explained in the link provided. In short: This is a GCC-specific header not intended for inclusion and other compilers don't provide it. So you have non-portable code. — Aconcagua, Jul 08 '20 at 06:01
@Aconcagua number n means any integer which you want to reach from 1 with three operations, namely, +1, X2 and X3. — baapcoder_, Jul 08 '20 at 06:06

score 4 · Accepted Answer · answered Jul 08 '20 at 05:42

4

You have pretty blatant out of bounds accesses on your vector v.

for(int i = 1; i <= v.size() - 1; i++)
    ,,,
    v[3*i] = v[i] + 1;

3*i is obviously bigger than the size of v for most of your loop.

answered Jul 08 '20 at 05:42

john

85,011
4
57
81

Yeah, I accept that! I have modified this code by adding conditions like 3*i <= n etc. – baapcoder_ Jul 08 '20 at 06:20
I got that! I added this line and bingo! – baapcoder_ Jul 08 '20 at 06:25

Primitive calculator - Dynamic Programming

1 Answers1