700
The 700th LC problem that I solved reminds me of the Collatz Conjecture. Here it is https://leetcode.com/problems/integer-replacement/
397. Integer Replacement
Medium
Given a positive integer n and you can do operations as follow:
- If n is even, replace n with
n/2. - If n is odd, you can replace n with either
n + 1orn - 1.
What is the minimum number of replacements needed for n to become 1?
Example 1:
Input: 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1
Example 2:
Input: 7 Output: 4 Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1
The idea is to implement the rules mentioned in the problem statement, but with the following observations and optimizations:
1) Use a static hash table to keep track of the results. That's your cache
2) Use long instead of int to avoid overflows
3) Last but not least, optimize for when N is a power of 2. If N is a power of 2, the solution if Log(N,2). To check whether a number is a power of 2, simply count the number of bits. If the sum is 1, you have a power of 2.
That's it. Code is below. Cheers friends, ACC.
static Hashtable irCache = new Hashtable();
public int IntegerReplacement(int n)
{
return IntegerReplacementLong(n);
}
private int IntegerReplacementLong(long n)
{
if (irCache.ContainsKey(n))
{
return (int)irCache[n];
}
if (n == 1)
{
irCache.Add(n, 0);
return 0;
}
//Power of 2
if (IsPowerOfTwo(n))
{
irCache.Add(n, (int)Math.Log(n, 2));
return (int)Math.Log(n, 2);
}
if (n % 2 == 0)
{
int val = IntegerReplacementLong(n / 2);
if (!irCache.ContainsKey(n))
{
irCache.Add(n, val + 1);
}
return val + 1;
}
else
{
int valMinus = IntegerReplacementLong(n - 1);
int valPlus = Int32.MaxValue;
if (valMinus != 0) valPlus = IntegerReplacementLong(n + 1);
int min = Math.Min(valPlus, valMinus);
if (!irCache.ContainsKey(n))
{
irCache.Add(n, min + 1);
}
return min + 1;
}
}
private bool IsPowerOfTwo(long n)
{
int bits = 0;
while (n > 0)
{
bits += (int)(n % 2);
if (bits > 1) return false;
n /= 2;
}
return bits == 1;
}
Comments
Post a Comment