Saturday, October 8, 2016

LeetCode OJ - Integer Replacement

Problem:

Please find the problem here.

Analysis:

Intuitively speaking, there is simply no reason to increment the number, except when that actually speed up things. A key example would be 15.

A pure greedy strategy would be 15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1, but a smarter strategy would be
15 -> 16 -> 8 -> 4 -> 2 -> 1. 5 replacement rather than 6.

Solution:

Notice that 4x - 1 -> 4x -> 2x -> x is always faster than 4x - 1 > 4x - 2 -> 2x - 1 -> 2x - 2. Therefore, whenever we see 4x - 1, we should always + 1, the only special case is 3 because 3 -> 4 -> 2 -> 1 is actually slower than 3 -> 2 -> 1.

The code also handled an extreme case for overflow when x is $ 2^{31} - 1 $.

Code:

#include "stdafx.h"

// https://leetcode.com/contest/4/problems/integer-replacement/

#include "LEET_INTEGER_REPLACEMENT.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_INTEGER_REPLACEMENT
{
    class Solution {
    public:
        int integerReplacement(int n)
        {
            return integerReplacementLong(n);
        }

        int integerReplacementLong(long long n)
        {
            if (n == 0)
            {
                return 1;
            }
            else if (n == 1)
            {
                return 0;
            }
            else if (n == 3)
            {
                // The divide by 4 rule does not apply for it
                return 2;
            }
            else if (n % 2 == 0)
            {
                return integerReplacementLong(n / 2) + 1;
            }
            else if ((n + 1) % 4 == 0)
            {
                return integerReplacementLong(n + 1) + 1;
            }
            else
            {
                return integerReplacementLong(n - 1) + 1;
            }
        }
    };
};

using namespace _LEET_INTEGER_REPLACEMENT;

int LEET_INTEGER_REPLACEMENT()
{
    Solution solution;
    for (int i = 0; i < 10; i++) {
        cout << i << "\t" << solution.integerReplacement(i) << endl;
    }
    cout << solution.integerReplacement(2147483647) << endl;
    return 0;
}

No comments :

Post a Comment