aboutsummaryrefslogtreecommitdiff
path: root/min_one_bit_0.rs
blob: 1b52362db09d7635788902506f3d764ec964d84f (plain)
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
struct Solution;

impl Solution {
    pub fn minimum_one_bit_operations(n: i32) -> i32 {
        if n <= 1 {
            return n;
        }
        let mut max = 1usize;
        while max < n as usize {
            max += max;
        }
        let mut dp = vec![0; max as usize + 1];
        dp[1] = 1;
        let (mut start, mut _i) = (2usize, 1);
        while start < max as usize {
            for i in 0..start / 2 {
                dp[start + i] = dp[start / 2 + i] + start;
                dp[start * 3 / 2 + i] = dp[i] + start;
            }
            start *= 2;
        }
        dp[max] = max * 2 - 1;
        dp[n as usize] as i32
    }
}

fn main() {
    print!("{}", Solution::minimum_one_bit_operations(39769175));
}