http://bookshadow.com/weblog/2016/09/11/leetcode-integer-replacement/
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 + 1
orn - 1
.
What is the minimum number of replacements needed for n to become 1?
Example 1:
Example 2:
X.
常规思路就是递归,但事实告诉你,下面这种写法,绝对是通不过的。栈溢出,时间问题导致这么写不行
def integerReplacement(self, n): """ :type n: int :rtype: int """ if n == 1: return 0 if n & 1 == 0: return self.integerReplacement(n / 2) + 1 return min(self.integerReplacement(n + 1), self.integerReplacement(n - 1)) + 1
X.
http://bookshadow.com/weblog/2016/09/11/leetcode-integer-replacement/
http://www.cnblogs.com/grandyang/p/5873525.html
https://discuss.leetcode.com/topic/58334/a-couple-of-java-solutions-with-explanations
http://www.dongcoder.com/detail-229130.html
X. BFS
https://discuss.leetcode.com/topic/58422/java-bfs-solution-tail-recursion
X. Proof
https://leetcode.com/problems/integer-replacement/discuss/87952/a-formal-complete-prove-of-the-theory-easy-to-understand
def integerReplacement(self, n): """ :type n: int :rtype: int """ if n == 1: return 0 if n & 1 == 0: return self.integerReplacement(n / 2) + 1 return min(self.integerReplacement(n + 1), self.integerReplacement(n - 1)) + 1
X.
http://bookshadow.com/weblog/2016/09/11/leetcode-integer-replacement/
需要注意的是,当n = 3时,不满足上述判定条件,需要单独处理
public int integerReplacement(int n) {
int c = 0;
while (n != 1) {
if ((n & 1) == 0) {
n >>>= 1;
} else if (n == 3 || ((n >>> 1) & 1) == 0) {
--n;
} else {
++n;
}
++c;
}
return c;
}http://www.cnblogs.com/grandyang/p/5873525.html
我们也可以使用迭代的解法,那么这里就有小技巧了,当n为奇数的时候,我们什么时候应该加1,什么时候应该减1呢,通过观察来说,除了3和7意外,所有加1就变成4的倍数的奇数,适合加1运算,比如15:
15 -> 16 -> 8 -> 4 -> 2 -> 1
15 -> 14 -> 7 -> 6 -> 3 -> 2 -> 1
对于7来说,加1和减1的结果相同,我们可以不用管,对于3来说,减1的步骤小,所以我们需要去掉这种情况。那么我们如何知道某个数字加1后是否是4的倍数呢,我们可以用个小技巧,由于我们之前判定其是奇数了,那么最右边一位肯定是1,如果其右边第二位也是1的话,那么进行加1运算,进位后右边肯定会出现两个0,则一定是4的倍数,搞定。如果之前判定是偶数,那么除以2即可
https://leetcode.com/problems/integer-replacement/discuss/87928/Java-12-line-4(5)ms-iterative-solution-with-explanations.-No-other-data-structures.https://discuss.leetcode.com/topic/58334/a-couple-of-java-solutions-with-explanations
The first step towards solution is to realize that you're allowed to remove the LSB only if it's zero. And to reach the target as fast as possible, removing digits is the best way to go. Hence, even numbers are better than odd. This is quite obvious.
What is not so obvious is what to do with odd numbers. One may think that you just need to remove as many 1's as possible to increase the evenness of the number. Wrong! Look at this example:
111011 -> 111010 -> 11101 -> 11100 -> 1110 -> 111 -> 1000 -> 100 -> 10 -> 1
And yet, this is not the best way because
111011 -> 111100 -> 11110 -> 1111 -> 10000 -> 1000 -> 100 -> 10 -> 1
See? Both
111011 -> 111010
and 111011 -> 111100
remove the same number of 1's, but the second way is better.
So, we just need to remove as many 1's as possible, doing +1 in case of a tie? Not quite. The infamous test with n=3 fails for that strategy because
11 -> 10 -> 1
is better than 11 -> 100 -> 10 -> 1
. Fortunately, that's the only exception (or at least I can't think of any other, and there are none in the tests).
So the logic is:
- If
n
is even, halve it. - If
n=3
orn-1
has less 1's thann+1
, decrementn
. - Otherwise, increment
n
.
public int integerReplacement(int n) {
int c = 0;
while (n != 1) {
if ((n & 1) == 0) {
n >>>= 1;
} else if (n == 3 || Integer.bitCount(n + 1) > Integer.bitCount(n - 1)) {
--n;
} else {
++n;
}
++c;
}
return c;
}
Of course, doing
bitCount
on every iteration is not the best way. It is enough to examine the last two digits to figure out whether incrementing or decrementing will give more 1's. Indeed, if a number ends with 01, then certainly decrementing is the way to go. Otherwise, if it ends with 11, then certainly incrementing is at least as good as incrementing (*011 -> *010 / *100
) or even better (if there are three or more 1's). This leads to the following solution:public int integerReplacement(int n) {
int c = 0;
while (n != 1) {
if ((n & 1) == 0) {
n >>>= 1;
} else if (n == 3 || ((n >>> 1) & 1) == 0) {
--n;
} else {
++n;
}
++c;
}
return c;
}
how to better deal with overflow?
public int integerReplacement(int n) {
if(n==1) return 0;
if(n==3) return 2;
if(n==2147483647) return integerReplacement(n/2+1)+2;
if(n%2==0) return integerReplacement(n/2)+1;
else return n%4==1?integerReplacement(n-1)+1:integerReplacement(n+1)+1;
}
http://blog.csdn.net/yeqiuzs/article/details/52506492
https://segmentfault.com/a/1190000007318944
https://blog.csdn.net/u014422406/article/details/52563273
上面做了很多重复的运算,所以自然而然想到将前面算的结果保存下来。所以有了下面的dp算法。
但是这种方法当测试到100万时会报错out of memory。
int integerReplacement(int n) {
int dp[n + 1];
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
dp[i] = dp[i / 2] + 1;
}
else {
if (i == INT_MAX) dp[i] = 2 + dp[i/2+1];
dp[i] = min(dp[i - 1], dp[(i + 1) / 2] + 1) + 1;
}
}
https://leetcode.com/problems/integer-replacement/discuss/88016/c-0ms-11-lines-dp-solution
no need to use int dp[n + 1], you just need int dp[(n + 1)/2] or less.
http://www.jianshu.com/p/cd525bed9b41
- public int integerReplacement(int n) {
- if (n == Integer.MAX_VALUE)
- return 32;
- int count = 0;
- while (n != 1) {
- if ((n & 1) == 0) {
- n = n >> 1;
- count++;
- } else {
- if (n == 3)
- n = 2;
- else {
- if (countTrailZero(n - 1) > countTrailZero(n + 1)) {
- n = n - 1;
- } else {
- n = n + 1;
- }
- }
- count++;
- }
- }
- return count;
- }
- public int countTrailZero(int n) {
- int c = 0;
- while ((n & 1) == 0) {
- n = n >> 1;
- c++;
- }
- return c;
- }
https://segmentfault.com/a/1190000007318944
对于奇数的操作
如果倒数第二位是0,那么n-1的操作比n+1的操作能消掉更多的1。
1001 + 1 = 1010
1001 - 1 = 1000
如果倒数第二位是1,那么n+1的操作能比n-1的操作消掉更多的1。
1011 + 1 = 1100
1111 + 1 = 10000
如果倒数第二位是0,那么n-1的操作比n+1的操作能消掉更多的1。
1001 + 1 = 1010
1001 - 1 = 1000
如果倒数第二位是1,那么n+1的操作能比n-1的操作消掉更多的1。
1011 + 1 = 1100
1111 + 1 = 10000
还有一个tricky的地方是,为了防止integer越界,可以将n先转换成long。long N = n;这样的处理。
public int integerReplacement(int n) {
// 处理大数据的时候tricky part, 用Long来代替int数据
long N = n;
int count = 0;
while(N != 1) {
if(N % 2 == 0) {
N = N >> 1;
}
else {
// corner case;
if(N == 3) {
count += 2;
break;
}
N = (N & 2) == 2 ? N + 1 : N - 1;
}
count ++;
}
return count;
}
http://www.voidcn.com/article/p-qykgdfsx-bee.html
每遇到奇数时,分别判断n-1还是n+1的尾部零更多,越多的当然步骤越少。
特殊case:当n==Integer 最大值时,当n==3时
public int integerReplacement(int n) {
if (n == Integer.MAX_VALUE)
return 32;
int count = 0;
while (n != 1) {
if ((n & 1) == 0) {
n = n >> 1;
count++;
} else {
if (n == 3)
n = 2;
else {
if (countTrailZero(n - 1) > countTrailZero(n + 1)) {
n = n - 1;
} else {
n = n + 1;
}
}
count++;
}
}
return count;
}
public int countTrailZero(int n) {
int c = 0;
while ((n & 1) == 0) {
n = n >> 1;
c++;
}
return c;
}
X. DPhttps://blog.csdn.net/u014422406/article/details/52563273
上面做了很多重复的运算,所以自然而然想到将前面算的结果保存下来。所以有了下面的dp算法。
但是这种方法当测试到100万时会报错out of memory。
int integerReplacement(int n) {
int dp[n + 1];
dp[0] = 0;
dp[1] = 0;
for (int i = 2; i <= n; i++) {
if (i % 2 == 0) {
dp[i] = dp[i / 2] + 1;
}
else {
if (i == INT_MAX) dp[i] = 2 + dp[i/2+1];
dp[i] = min(dp[i - 1], dp[(i + 1) / 2] + 1) + 1;
}
}
https://leetcode.com/problems/integer-replacement/discuss/88016/c-0ms-11-lines-dp-solution
no need to use int dp[n + 1], you just need int dp[(n + 1)/2] or less.
int integerReplacement(int n) {
int dp[n + 1]; memset(dp, 0, sizeof(dp));
for (int i = 2; i <= n; i++) {
dp[i] = 1 + (i & 1 == 0 ? dp[i / 2] : min(dp[i - 1], 1 + dp[i / 2 + 1]));
}
return dp[n];
}
int integerReplacement(int n) {
if (n == 1) { return 0; }
if (visited.count(n) == 0) {
if (n & 1 == 1) {
visited[n] = 2 + min(integerReplacement(n / 2), integerReplacement(n / 2 + 1));
} else {
visited[n] = 1 + integerReplacement(n / 2);
}
}
return visited[n];
}
X. DPhttp://www.jianshu.com/p/cd525bed9b41
int integerReplacement(int n) {
if(n <= 1) return 0;
else if(n == INT_MAX) return 32;
vector<int> dp(n+2, n+2);
dp[1] = 0, dp[2] = 1;
for(int i=2; i<n+2; i++){
if(i % 2 == 0 && dp[i] > dp[i/2] + 1) dp[i] = dp[i/2]+1;
if(i+1 <= n+1 && dp[i] > dp[i+1] + 1) dp[i] = dp[i+1] + 1;
if(i % 2 == 0){
if(i+1 <= n+1) dp[i+1] = min(dp[i+1], dp[i]+1);
dp[i-1] = min(dp[i-1], dp[i]+1);
}
}
return dp[n];
}
X.DFS + cache
Same idea with other recursive solutions, but two ticky points here.
- With the helper of hashmap, we don't need to search for one intermediate result multiple times
- To hand the overflow for test case INT.MAX, use
1 + (n - 1) / 2
instead of(n + 1) / 2
. The idea comes from solving some binary search questions. To avoid overflow, we useint mid = start + (end - start) / 2
instead ofint mid = (start + end) / 2
public int integerReplacement(int n) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
map.put(1, 0);
map.put(2, 1);
return helper(n, map);
}
private int helper(int n, Map<Integer, Integer> map) {
if (map.containsKey(n)) {
return map.get(n);
}
int steps = -1;
if (n % 2 == 0) {
steps = helper(n / 2, map) + 1;
} else {
steps = Math.min(helper((n - 1), map) + 1, helper(1 + (n - 1) / 2, map) + 2);
}
map.put(n, steps);
return steps;
}
X. BFS
https://discuss.leetcode.com/topic/58422/java-bfs-solution-tail-recursion
public int integerReplacement(int n) {
assert n > 0;
Queue<Long> queue = new LinkedList<>();
queue.offer((long)n);
return bfs(queue, 0);
}
private int bfs(Queue<Long> oldqueue, int level) {
Queue<Long> newqueue = new LinkedList<>();
while (!oldqueue.isEmpty()) {
long n = oldqueue.poll();
if (n == 1) {
return level;
}
if (n % 2 == 0) {
newqueue.offer(n / 2);
} else {
newqueue.offer(n + 1);
newqueue.offer(n - 1);
}
}
return bfs(newqueue, level + 1);
}
https://discuss.leetcode.com/topic/58422/java-bfs-solution-tail-recursion public int integerReplacement(int n) {
assert n > 0;
Queue<Long> queue = new LinkedList<>();
queue.offer((long)n);
return bfs(queue, 0);
}
private int bfs(Queue<Long> oldqueue, int level) {
Queue<Long> newqueue = new LinkedList<>();
while (!oldqueue.isEmpty()) {
long n = oldqueue.poll();
if (n == 1) {
return level;
}
if (n % 2 == 0) {
newqueue.offer(n / 2);
} else {
newqueue.offer(n + 1);
newqueue.offer(n - 1);
}
}
return bfs(newqueue, level + 1);
}
X. Proof
https://leetcode.com/problems/integer-replacement/discuss/87952/a-formal-complete-prove-of-the-theory-easy-to-understand
For any odd number k >= 3, f(k-1) <= f(k) and f(k+1) <= f(k), where f denotes "integerReplacement(int n)".
In another words, for two adjacent numbers the even one needs less or equal steps to get to 1 than that of the odd one.
In another words, for two adjacent numbers the even one needs less or equal steps to get to 1 than that of the odd one.
This can be proven by induction:
- for 2,3,4,5,6 we have f(2) = 1, f(3) = 2, f(4) = 2, f(5) = 3, f(6) = 3 which agree with the statement
- for and odd number k let's prove f(k-1) <= f(k) (f(k+1) < f(k) can be proven in the same manner):
for k-1: k-1 -> (k-1)/2
for k: a. k -> k-1 -> (k-1)/2 OR
b. k -> k+1->(k+1)/2
if we take path a, it's obvious that k takes one more step than k-1 to get (k-1)/2 so f(k-1) < f(k)
if we take path b,
if (k+1)/2 is even and (k-1)/2 is odd, then for k-1 we can also take two step to reach (k+1)/2 by k-1 -> (k-1)/2 - > (k+1)/2, so f(k-1) = f(k)
if (k+1)/2 is odd number, by induction we know f[(k-1)/2] <= f[(k+1)/2], so overall f(k-1) < f(k) (because it takes one step from k-1 to (k-1)/2 but two steps from k to (k+1)/2)
So in all the cases f(k-1) <= f(k)
Corollary:
For our problem: if we have an odd number we need increase or decrease to make it be 4n. The reason is for an odd number after two steps it could become an odd or even number differed by 1 and the theorm above tell us you better become an even number after two steps.
Why 3 is an exception? The theorem only applies for odd numbers >= 3 because f(2) > f(1) is an exception!!
https://leetcode.com/problems/integer-replacement/discuss/87948/Python-O(log-n)-time-O(1)-space-with-explanation-and-proofFor our problem: if we have an odd number we need increase or decrease to make it be 4n. The reason is for an odd number after two steps it could become an odd or even number differed by 1 and the theorm above tell us you better become an even number after two steps.
Why 3 is an exception? The theorem only applies for odd numbers >= 3 because f(2) > f(1) is an exception!!
Lemma 1. f(k+1) <= f(k) + 1
Prove by induction:
f(2) = 1 <= 0 + 1 = f(1) + 1
Assume this hold for any 1 <= k' < k,
If k is even, f(k + 1) = min(f(k) + 1, f(k + 2) + 1) <= f(k) + 1;
If k is odd, denote k = 2l + 1 (l >= 1), then f(k + 1) = f(2l + 2) = 1 + f(l + 1) <= 1 + 1 + f(l) = 1 + f(2l) = 1 + f(k - 1). Also, f(k + 1) = 1 + f(l + 1) = f(2l + 2) = f(k + 1) <= f(k + 1) + 1. Hence, f(k + 1) <= min(f(k - 1) + 1, f(k + 1) + 1) = f(k) <= f(k) + 1.
Prove by induction:
f(2) = 1 <= 0 + 1 = f(1) + 1
Assume this hold for any 1 <= k' < k,
If k is even, f(k + 1) = min(f(k) + 1, f(k + 2) + 1) <= f(k) + 1;
If k is odd, denote k = 2l + 1 (l >= 1), then f(k + 1) = f(2l + 2) = 1 + f(l + 1) <= 1 + 1 + f(l) = 1 + f(2l) = 1 + f(k - 1). Also, f(k + 1) = 1 + f(l + 1) = f(2l + 2) = f(k + 1) <= f(k + 1) + 1. Hence, f(k + 1) <= min(f(k - 1) + 1, f(k + 1) + 1) = f(k) <= f(k) + 1.
Lemma 2. f(k) <= 1 + f(k + 1), k >= 1
Prove by induction:
f(1) = 0 <= 1 + f(2)
Assume this hold for any 1 <= k' < k,
If k is odd, f(k) = min(1 + f(k - 1), 1 + f(k + 1)) <= 1 + f(k + 1)
If k is even, denote k = 2l (l >= 1), then f(k) = f(2l) = 1 + f(l)
1 + f(l) <= 3 + f(l) = 2 + f(2l) = 1 + (1 + f(2l))
1 + f(l) <= 1 + 1 + f(l + 1) <= 3 + f(l + 1) = 2 + f(2l + 2) = 1 + (1 + f(2l + 2))
=> f(k) = 1 + f(l) <= 1 + min(1 + f(2l), 1 + f(2l + 2)) = 1 + f(2l + 1) = 1 + f(k + 1).
Prove by induction:
f(1) = 0 <= 1 + f(2)
Assume this hold for any 1 <= k' < k,
If k is odd, f(k) = min(1 + f(k - 1), 1 + f(k + 1)) <= 1 + f(k + 1)
If k is even, denote k = 2l (l >= 1), then f(k) = f(2l) = 1 + f(l)
1 + f(l) <= 3 + f(l) = 2 + f(2l) = 1 + (1 + f(2l))
1 + f(l) <= 1 + 1 + f(l + 1) <= 3 + f(l + 1) = 2 + f(2l + 2) = 1 + (1 + f(2l + 2))
=> f(k) = 1 + f(l) <= 1 + min(1 + f(2l), 1 + f(2l + 2)) = 1 + f(2l + 1) = 1 + f(k + 1).
Proof of (*):
- If n % 4 = 3 and n != 3, denote n = 4k + 3 where k >= 1.
f(n - 1) = f(4k + 2) = 1 + f(2k + 1) = 1 + min(f(2k) + 1, f(2k + 2) + 1) = min(f(2k) + 2, f(2k + 2) + 2)
f(2k) + 2 = f(k) + 3 >= f(k + 1) + 2 = 1 + f(2k + 2)
and f(2k + 2) + 2 > f(2k + 2) + 1, so f(n - 1) >= 1 + f(2k + 2) = f(4k + 4) = f(n + 1) => f(n) = min(f(n - 1) + 1, f(n + 1) + 1) = f(n + 1) + 1. - If n = 3, it's obvious that f(3) = min(f(2) + 1, f(2) + 2) = f(2) + 1.
- If n % 4 = 1 and n > 1, denote n = 4k + 1 where k >= 1.
f(n - 1) = f(4k) = 1 + f(2k)
1 + f(2k) < 2 + f(2k)
1 + f(2k) = 2 + f(k) <= 3 + f(k + 1) = 2 + f(2k + 2)
=> f(n - 1) = 1 + f(2k) <= min(2 + f(2k), 2 + f(2k + 2)) = 1 + min(f(2k) + 1, f(2k + 2) + 1) = 1 + f(2k + 1) = f(4k + 2) = f(n + 1)=> f(n) = min(f(n - 1) + 1, f(n + 1) + 1) = f(n - 1) + 1