c++ – Can't solve the programming problem: calculator

Question:

I am trying to solve the problem of the condition, which is given below. The problem is that on large numbers my program produces some absolutely hellish result. For example, for the number 96234, the program produces such a sheet of numbers http://pastebin.com/8H5SvPKb (compare with the result given in the condition). In principle, I understand why this is happening, but I have no other idea for solving this problem. Tell me how to competently solve this problem.

The task:

You have a primitive calculator that can perform only three operations on the current number x: replace x with 2x, 3x, or x + 1. Given an integer 1≤n≤10 ^ 5, determine the minimum number of operations k required to get n out of 1. Print k and a sequence of intermediate numbers.

Sample Input 1:
1
Sample Output 1:
0
1 

Sample Input 2:
5
Sample Output 2:
3
1 2 4 5 

Sample Input 3:
96234
Sample Output 3:
14
1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234

My decision:

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;

    int i = 1;
    vector<int> m;
    m.push_back(i);
    while (i != n) {
        if (i * 3 <= n) {
            i *= 3;
        } else if (i * 2 <= n) {
            i *= 2;
        } else {
            i++;
        }
        m.push_back(i);
    }

    cout << m.size() - 1 << endl;
    for (int i = 0; i < m.size(); i++) cout << m[i] << " ";

    return 0;
}

Answer:

I will write my own solution, which, in my opinion, is much easier to understand than those already published (I, for example, do not understand why they are correct).

The algorithm is as follows: we start a list in which in the i-th position we will store the minimum number of steps, known at the moment, for which you can get to N. At the beginning, we will only know that in the N-th position is 0. Then we start run through the list from end to beginning. At each step, we check from which positions we can get to the current one, and for these positions we update the distance if it is better than the previously calculated one. By the time we arrive at the i-th element, the minimum distance will be written there, since we went through all the options. The code is like this:

#include <iostream>
#include <vector>
#include <climits>

int main() {
  int N;
  std::cin >> N;
  std::vector<int> steps(N + 1, INT_MAX);
  steps[N] = 0;
  std::vector<int> next_num(N + 1, -1);

  for (int i = N; i > 1; --i) {
    int s = steps[i] + 1;
    // 3 * x
    if (!(i % 3) && steps[i / 3] > s) {
      steps[i / 3] = s;
      next_num[i / 3] = i;
    }
    // 2 * x
    if (!(i % 2) && steps[i / 2] > s) {
      steps[i / 2] = s;
      next_num[i / 2] = i;
    }
    // x + 1
    if (steps[i - 1] > s) {
      steps[i - 1] = s;
      next_num[i - 1] = i;
    }
  }

  std::cout << steps[1] << std::endl;
  for (int i = 1; i != -1; i = next_num[i])
    std::cout << i << ' ';
  std::cout << std::endl;
}

The complexity of the algorithm is linear.

Test results:

http://ideone.com/cuHyDP

 stdin
1
 stdout
0
1

http://ideone.com/Ttku2H

 stdin
5
 stdout
3
1 3 4 5

http://ideone.com/G5yg1I

 stdin
96234
 stdout
14
1 3 9 10 11 33 99 297 891 2673 8019 16038 16039 48117 96234
Post Views: 3
Scroll to Top