Easiest Program: Minimum Steps to One

Hi Folks,

In this post, I would like to add the easiest program I had come up with for the problem “Minimum Steps to One”. Target audience are beginner programmers, self-taught programmers who understand RECURSION.

For those who are new to the problem, the problem statement is,

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 your task is to find the minimum number of steps that n takes to become 1. Without much time, let’s get into it.

int naive(int n) {
    int a = 999999, b = 999999, c = 999999;
    if (n == 1)
        return 0;
    if (n % 3 == 0)
            a = naive(n / 3);
    if (n % 2 == 0)
            b = naive(n / 2);
    c = naive(n - 1);
    return 1 + minimum(a, b, c);
}

Note that, the function uses “minimum” function, which returns the minimum element among a, b, c.

Thanks for reading, Hope you enjoyed my program. Let me know in the comments below.