Integer Replacement

Problem: Given a positive integer n, you can apply one of the following operations:

• If n is even, replace n with n / 2.
• If n is odd, replace n with either n + 1 or n - 1.

Return the minimum number of operations needed for n to become 1.

Example:

Input: n = 9
Output: 4
Explanation: 9 -> 8 -> 4 -> 2 -> 1

Approach: Here is the simple recursive approach to solve this problem:

• Solve(n)
• IF n == 1
• RETURN 0
• IF n % 2 == 0
• RETURN 1 + Solve (n / 2)
• RETURN 1 + Min (Solve(n - 1), Solve (n + 1)

But it will be very expensive in terms of time. If you see there are subproblems which we are solving multiple times and that means we can use DP here. 

We can memorize(store it in a table) the result for the values for which we have already solved the problem so whenever we try to solve the problem for the those values, we immediately return the result stored, so now the changed algorithm will look like:

• Solve(n , table)
• table has n
• RETURN table[n]
• IF n%2 == 0
• table[n] = 1 + Solve(n/2)
• ELSE
• table[n] = 1 +  Math.Min(Solve(n-1), Solve(n + 1))
• RETURN table[n]

That's all!

Implementation in C#:

        public static int IntegerReplacement(int n)

        {

            if (n <= 2)

            {

                return n - 1;

            }

            if (n == int.MaxValue)

            {

                return 32;

            }

            Dictionary<int, int> hash = new Dictionary<int, int>();

            hash.Add(1, 0);

            hash.Add(int.MaxValue, 32);

            return IntegerReplacement(n, hash);

        }

        private static int IntegerReplacement(int n, Dictionary<int, int> hash)

        {

            if (hash.ContainsKey(n))

            {

                return hash[n];

            }

            if (n % 2 == 0)

            {

                hash.Add(n, 1 + IntegerReplacement(n / 2, hash));

            }

            else

            {

                hash.Add(n, 1 + Math.Min(IntegerReplacement(n - 1, hash), IntegerReplacement(n + 1, hash)));

            }

            return hash[n];

        }

Complexity: O(logn)