Primitive Calculator - Dynamic Approach

Question

I'm having some trouble getting the correct solution for the following problem:

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.

More specifically the test case I have in the comments below.

 # Failed case #3/16: (Wrong answer)
    # got: 15 expected: 14
    # Input:
    # 96234
    #
    # Your output:
    # 15
    # 1 2 4 5 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
    # Correct output:
    # 14
    # 1 3 9 10 11 22 66 198 594 1782 5346 16038 16039 32078 96234
    #  (Time used: 0.10/5.50, memory used: 8601600/134217728.)


    def optimal_sequence(n):
        sequence = []

        while n >= 1:
            sequence.append(n)

            if n % 3 == 0:
                n = n // 3
                optimal_sequence(n)

            elif n % 2 == 0:
               n = n // 2
               optimal_sequence(n)

            else:
               n = n - 1
               optimal_sequence(n)

        return reversed(sequence)

    input = sys.stdin.read()
    n = int(input)
    sequence = list(optimal_sequence(n))
    print(len(sequence) - 1)
    for x in sequence:
        print(x, end=' ')

It looks like I should be outputting 9 where I'm outputting 4 & 5 but I'm not sure why this isn't the case. What's the best way to troubleshoot this problem?

Solution 1

You are doing a greedy approach. When n == 10, you check and see if it's divisible by 2 assuming that's the best step, which is wrong in this case.

What you need to do is proper dynamic programming. v[x] will hold the minimum number of steps to get to result x.

def solve(n):
  v = [0]*(n+1)  # so that v[n] is there
  v[1] = 1  # length of the sequence to 1 is 1
  for i in range(1,n):
    if not v[i]: continue
    if v[i+1] == 0 or v[i+1] > v[i] + 1: v[i+1] = v[i] + 1
    # Similar for i*2 and i*3
  
  solution = []
  while n > 1:
    solution.append(n)
    if v[n-1] == v[n] - 1: n = n-1
    if n%2 == 0 and v[n//2] == v[n] -1: n = n//2
    # Likewise for n//3
  solution.append(1)
  return reverse(solution)

Solution 2

One more solution:

private static List<Integer> optimal_sequence(int n) {
    List<Integer> sequence = new ArrayList<>();

    int[] arr = new int[n + 1];

    for (int i = 1; i < arr.length; i++) {
        arr[i] = arr[i - 1] + 1;
        if (i % 2 == 0) arr[i] = Math.min(1 + arr[i / 2], arr[i]);
        if (i % 3 == 0) arr[i] = Math.min(1 + arr[i / 3], arr[i]);

    }

    for (int i = n; i > 1; ) {
        sequence.add(i);
        if (arr[i - 1] == arr[i] - 1)
            i = i - 1;
        else if (i % 2 == 0 && (arr[i / 2] == arr[i] - 1))
            i = i / 2;
        else if (i % 3 == 0 && (arr[i / 3] == arr[i] - 1))
            i = i / 3;
    }
    sequence.add(1);

    Collections.reverse(sequence);
    return sequence;
}

Comments

[execv3]

So it seems I'm having a hard time grasping how the minimum number of steps is determined in this case. Looks like the list gets updated in the event that the i-th plus one element is equal to 0 or greater than the i-th, but I'm just not seeing at first glance the significance of this.

[Sorin]

Take 10 as an example. when i = 5, v[i]= 4 so via the i*2 branch you are going to write 5 to v[10]. As you progress you will reach i=9 with v[9] = 3. so now you want to update v[10] which is no longer 0 with 4. Since 5 > 4 you will write there 4. In short the condition says update a position if this is the first time you get there (v[i+1] == 0) or the number of steps to get there from the current position is less than what you've found so far (v[i+1], what you've found so far, > v[i] + 1, what you would get if you go from i). Does this it make it clearer?

[execv3]

I think so, let me try and debug your example and reference what you've pointed out here.

[labheshr]

can you explain the algorithm?

[Sarah]

I'm getting an error: if v[i + 1] == 0 or v[i + 1] > v[i] + 1: IndexError: list index out of range Can anyone help with this? I'm trying to understand the solution but no idea. Any help will be appreciated!

[Sorin]

@sarahkim You need to check that the destination is in bounds (i+1 <= n in this case). Always check you bounds unless you can prove that you're never going outside.

[Sarah]

@Sorin Thank you!

[DCCoder]

Generally, answers are much more helpful if they include an explanation of what the code is intended to do, and why that solves the problem without introducing others.

[MOHAN SHARMA]

First i calculated the no of operations to reach the target no and then using that information calculated the required sequence using dynamic approach.If you need and explanation ask in the comments

[Carmoreno]

Hi MOHAN and welcome to SO, why not simply you edit the question and put the descriptions and clarifications there? ... Check it out: stackoverflow.com/help/how-to-answer

[fql]

Explanation: First, we create a indexed 0 to n list, put all numbers as 0(hop_count), then we iterate from 2 to n, append the number(x)'s possible previous numbers(x-1,x//2,x//3) to a temporary list(indices), then we find the min(min_hop) number of optimal count of every number in the temporary list, the number with the least number of optimal count will be x's previous number, hence optimal number of count will be hop_count[min_hop] + 1.

[fql]

Then, after we've gotten the list of optimal number of counts for every number to n, we will then create the optimal_seq list, first number will be n, then, create the second temporary list within the while loop(candidates), put in all the possible previous number starting with n(ptr), find the min of all the optimal number of count of these numbers, append the number that has the lowest number of count to the optimal seq list.

[Admin]

As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center.

[All Downhill From Here]

Hi fql! Your explanatory comments would be good to add to the main answer (through editing), so we have everything in one convenient place.