Correctness and Logic of algorithm: minimum steps to one

Question

Problem Statement:

On a positive integer, you can perform any one of the following 3 steps.

1. Subtract 1 from it. ( n = n - 1 )

2. If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2 )

3. If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3 )

Given a positive integer n and you task is find the minimum number of steps that takes n to one .

My Recursive Solution (in C++) compares all the 3 cases when N is divisible by 3, while the general solution compares only 2, but still gives the correct solution.

int min_steps(int N){ 
        if(N==1) return 0;    
        else{
                if(N%3==0){
                       if(N%2==0) 
                          return (1+min(min_steps(N/3),min_steps(N/2),min_steps(N-1)));
                       else
                          return(1+min(min_steps(N/3),min_steps(N-1)));
                }
                else if(N%2==0){
                        return(1+min(min_steps(N/2),min_steps(N-1)));
                }
                else
                        return(1+min_steps(N-1));
        }
}

But the general solution is,

int min_steps(int N){ 
        if(N==1) return 0;    
        else{
                if(N%3==0){
                        return(1+min(min_steps(N/3),min_steps(N-1)));
                }
                else if(N%2==0){
                        return(1+min(min_steps(N/2),min_steps(N-1)));
                }
                else
                        return(1+min_steps(N-1));
        }
}

My question is, how come we don't compare all the 3 cases but still derive at the correct solution. I cannot follow the general solution's algorithm. Any help for letting me understand would be appreciated hugely.

Hollywood

Answer 1

The "general solution" is incorrect. Sometime's it's optimal to divide by 2 and then subtract 1, and the general solution code doesn't allow for that.

The "general solution" produces incorrect results for 642.

642 -> 214 -> 107 -> 106 -> 53 -> 52 -> 26 -> 13 -> 12 -> 4 -> 2 -> 1

However, this is optimal, being one shorter:

642 -> 321 -> 320 -> 160 -> 80 -> 40 -> 20 -> 10 -> 9 -> 3 -> 1

You can see the general solution starts by dividing by 3, and the optimal solution starts by dividing by 2 and then subtracting 1... which is exactly the case that's been removed.

While it's not directly relevant to your question, here's the code I used to find the counter-example (albeit greatly tidied up since I wrote it). It uses the two algorithms you gave, but memoizes them for an exponential speed increase. It also uses a trick of returning two results from min_steps: not only the length of the shortest path, but also the first step in that path. This makes it extremely convenient to reconstruct the path without writing much extra code.

def memoize(f):
    """Simple memoization decorator"""
    def mf(n, div2, cache={}):
        if (n, div2) not in cache:
            cache[n, div2] = f(n, div2)
        return cache[(n, div2)]
    return mf

@memoize
def min_steps(n, div2):
    """Returns the number of steps and the next number in the solution.

    If div2 is false, the function doesn't consider solutions
    which involve dividing n by 2 if n is divisible by 3.
    """
    if n == 1:
        return 0, None
    best = min_steps(n - 1, div2)[0] + 1, n-1
    if n % 3 == 0:
        best = min(best, (min_steps(n // 3, div2)[0] + 1, n//3))
    if n % 2 == 0 and (div2 or n%3):
        best = min(best, (min_steps(n // 2, div2)[0] + 1, n//2))
    return best

def path(n, div2):
    """Generates an optimal path starting from n.

    The argument div2 has the same meaning as in min_steps.
    """
    while n:
        yield n
        _, n = min_steps(n, div2)

# Search for values of n for which the two methods of finding
# an optimal path give different results.
for i in xrange(1, 1000):
    ms1, _ = min_steps(i, True)
    ms2, _ = min_steps(i, False)
    if ms1 != ms2:
        print i, ms1, ms2
        print ' -> '.join(map(str, path(i, True)))
        print ' -> '.join(map(str, path(i, False)))

Here's the output, including run-times:

$ time python minsteps.py 
642 10 11
642 -> 321 -> 320 -> 160 -> 80 -> 40 -> 20 -> 10 -> 9 -> 3 -> 1
642 -> 214 -> 107 -> 106 -> 53 -> 52 -> 26 -> 13 -> 12 -> 4 -> 2 -> 1
643 11 12
643 -> 642 -> 321 -> 320 -> 160 -> 80 -> 40 -> 20 -> 10 -> 9 -> 3 -> 1
643 -> 642 -> 214 -> 107 -> 106 -> 53 -> 52 -> 26 -> 13 -> 12 -> 4 -> 2 -> 1

real    0m0.009s
user    0m0.009s
sys 0m0.000s

Nikos

Also, it reassured the correctness of my algorithm. – Hollywood

Answer 2

If n is divisible by 3 and divisible by 2, then it does not matter if you divide by 3 first and then by 2 in the next step, or by 2 first and then by 3 in the next step.

Example: 18 = 3*3*2

a) 18/3 = 6, 6/3 = 2, 2/2 = 1, or

b) 18/2 = 9, 9/2 = #!?#, 9/3 = 3, 3/3 = 1, or ...

Citadel

If you've got a multiple of 6, it's never optimal to divide by two and then subtract 1? That may be, but it's not obvious. – Nikos