397. Integer Replacement Medium

1/**
2 * [397] Integer Replacement
3 *
4 * Given a positive integer n, you can apply one of the following operations:
5 * <ol>
6 * If n is even, replace n with n / 2.
7 * If n is odd, replace n with either n + 1 or n - 1.
8 * </ol>
9 * Return the minimum number of operations needed for n to become 1.
10 *  
11 * Example 1:
12 * 
13 * Input: n = 8
14 * Output: 3
15 * Explanation: 8 -> 4 -> 2 -> 1
16 * 
17 * Example 2:
18 * 
19 * Input: n = 7
20 * Output: 4
21 * Explanation: 7 -> 8 -> 4 -> 2 -> 1
22 * or 7 -> 6 -> 3 -> 2 -> 1
23 * 
24 * Example 3:
25 * 
26 * Input: n = 4
27 * Output: 2
28 * 
29 *  
30 * Constraints:
31 * 
32 * 1 <= n <= 2^31 - 1
33 * 
34 */
35pub struct Solution {}
36
37// problem: https://leetcode.com/problems/integer-replacement/
38// discuss: https://leetcode.com/problems/integer-replacement/discuss/?currentPage=1&orderBy=most_votes&query=
39
40// submission codes start here
41impl Solution {
42    pub fn integer_replacement(n: i32) -> i32 {
43        let mut count = 0;
44        let mut num = n as i64;
45        while num != 1 {
46            if num & 1 == 0 {
47                num >>= 1;
48            } else if num == 3 || num >> 1 & 1 == 0 {
49                num -= 1;
50            } else {
51                num += 1;
52            }
53            count += 1;
54        }
55        count
56    }
57}
58
59// submission codes end
60
61#[cfg(test)]
62mod tests {
63    use super::*;
64
65    #[test]
66    fn test_397() {
67        assert_eq!(Solution::integer_replacement(2147483647), 32);
68        assert_eq!(Solution::integer_replacement(7), 4);
69        assert_eq!(Solution::integer_replacement(8), 3);
70        assert_eq!(Solution::integer_replacement(4), 2);
71        
72    }
73}
74