LeetCode [397] Integer Replacement

397. Integer Replacement

Medium

Given a positive integer n and you can do operations as follow:

1. If n is even, replace n with n/2.
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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

typedef long long ll; class Solution { int countBit(ll n){ int cnt = 0; while(n){ cnt += (0x1 & n); n = n>>1; } return cnt; } public: int integerReplacement(int n) { int step = 0; ll m = n; while(m!=1){ if(m%2==0){ m = m>>1; }else if (m==3){ m--; }else if (countBit(m-1)<countBit(m+1)){ m--; }else{ m++; } step++; } return step; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

class Solution { public: int integerReplacement(int n) { vector<int> dp(n+1, INT_MAX); dp[1] = 0; for(int i=2; i<=n; ++i){ if(i%2==0){ dp[i] = min(dp[i], dp[i/2]+1); }else{ dp[i] = min(dp[i], min(1+dp[i-1], 2+dp[i/2+1]));//(i+1)/2==i/2+1, avoid overflow } } return dp[n]; } };

1 2 3 4 5 6 7 8 9 10 11 12 13

typedef long long ll; class Solution { public: int integerReplacement(int n) { return dfs(n); } int dfs(ll m){ if(m==1) return 0; if(m%2==0) return 1+dfs(m/2); return min(dfs(m+1), dfs(m-1))+1; } };

• https://leetcode.com/problems/integer-replacement/discuss/87920/A-couple-of-Java-solutions-with-explanations