## Saturday, October 8, 2016

### LeetCode OJ - Integer Replacement

Problem:

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;
}