首页 > 代码库 > Leetcode: Integer Replacement

Leetcode: Integer Replacement

2024-08-24 12:08:30   218人阅读

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 or n - 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

Refer to: https://discuss.leetcode.com/topic/58334/a-couple-of-java-solutions-with-explanations/2

When to add 1 instead of minus 1, here is an example:

 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.

 

 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 decrementing (*011 -> *010 / *100) or even better (if there are three or more 1‘s). This leads to the following solution:

 

So the logic is:

  1. If n is even, halve it.
  2. If n=3 or n ends with "01", decrease n
  3. Otherwise, increment n.(ends with "11", "111" or even more "1111")
 1 public class Solution {
 2     public int integerReplacement(int n) {
 3         int count = 0;
 4         while (n != 1) {
 5             if ((n & 1) == 0) 
 6                 n = n >>> 1;
 7             else if (n==3 || (n & 0b11) == 1)
 8                 n--;
 9             else n++;
10             count++;
11         }
12         return count;
13     }
14 }

 

Another logic is:

So the logic is:

  1. If n is even, halve it.
  2. If n=3 or n-1 has less 1‘s than n+1, decrement n.
  3. Otherwise, increment n.
 1 public int integerReplacement(int n) {
 2     int c = 0;
 3     while (n != 1) {
 4         if ((n & 1) == 0) {
 5             n >>>= 1;
 6         } else if (n == 3 || Integer.bitCount(n + 1) > Integer.bitCount(n - 1)) {
 7             --n;
 8         } else {
 9             ++n;
10         }
11         ++c;
12     }
13     return c;
14 }

 

Leetcode: Integer Replacement


联系
我们