C/C++ Coding Exercise – Minimal Number of Replacements for Integer to Become One?

Any positive integers will become 1 following the steps: (1) divide by 2 if it is even (2) otherwise increment or decrement by 1. So the question is: could you write a function that computes the minimal number of steps required for integer n to become 1. For example, input 8, the output is 3 because 8 – 4 – 2 – 1. Another example 7, it takes 4 steps, 7 – 6 – 3 – 2 – 1 or 7 – 8 – 4 – 2 – 1.

The key idea is to use recursion. However, make sure the input parameter is unsigned int otherwise the maximum signed 32-bit integer 2147483647 plus 1 will overflow (becomes negative 1) and give the incorrect result.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int minimalSteps(unsigned int n) {
        if (n == 1) {
            return 0;
        }
        if (n % 2 == 0) {
            return minimalSteps(n / 2) + 1;
        }
        return min(minimalSteps(n + 1), minimalSteps(n - 1)) + 1;
    }
};

class Solution {
public:
    int minimalSteps(unsigned int n) {
        if (n == 1) {
            return 0;
        }
        if (n % 2 == 0) {
            return minimalSteps(n / 2) + 1;
        }
        return min(minimalSteps(n + 1), minimalSteps(n - 1)) + 1;
    }
};

In the above C/C++ solution, the time complexity is . Does it always terminate? Well… this is actually quite similar to that famous math problem e.g. Collatz, easy to guess, but hard to prove.

–EOF (The Ultimate Computing & Technology Blog) —