1404. Number of Steps to Reduce a Number in Binary Representation to One solved in Rustlang

Link

1404. Number of Steps to Reduce a Number in Binary Representation to One

Problem

The problem is asking to reduce a binary number to 1 by applying two operations:

• if the number is even, divide it by 2
• if the number is odd, add 1 to it

Idea

This problem is straight forward, there is no need for special key to unlock it. The intuitive approach would be to start by converting the binary string to a decimal and apply the operations. However, this approach will not fit in the type constraints of the problem. The string input can be 500 characters long.

The solution is to apply the operations directly on the binary string.

We check the last character of the string, if it is 0, we will jost pop it and remove the string.

If the last character is 1, we will add 1 to the string. The addition is done by iterating over the string from the end to the beginning. We will keep track of the carry and the result.

Solution

// src/lib.rs

pub struct Solution;

impl Solution {
    pub fn num_steps(s: String) -> i32 {
        let mut s = s;

        let mut operations = 0;

        while s != "1" {
            if s.ends_with('0') {
                s.pop();
            } else {
                s = Solution::add_one(&s);
            }

            operations += 1;
        }

        operations
    }

    fn add_one(s: &str) -> String {
        let mut carry = '1'; // we start with 1 right away
        let mut result: Vec<char> = vec![];

        for ch in s.chars().rev() {
            match (ch, carry) {
                ('1', '1') => {
                    result.push('0');
                    carry = '1';
                }
                ('1', _) => {
                    result.push('1');
                }
                (_, '1') => {
                    result.push('1');
                    carry = '0';
                }
                _ => {
                    result.push(carry);
                }
            }
        }

        if carry == '1' { // we need to track the last carry to add it
            result.push('1');
        }

        result.iter().rev().collect::<String>()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_add_one_ok() {
        let scenarios = vec![
            ("10".to_string(), "11".to_string()),
            ("101".to_string(), "110".to_string()),
            ("110".to_string(), "111".to_string()),
            ("111".to_string(), "1000".to_string()),
        ];

        scenarios
            .into_iter()
            .enumerate()
            .for_each(|(idx, (input, expected))| {
                let result = Solution::add_one(&input);
                assert_eq!(result, expected);
                println!("  ✓ scenario {}", idx + 1)
            });
    }

    #[test]
    fn it_works() {
        let scenarios = vec![
            ("1101".to_string(), 6),
            ("10".to_string(), 1),
            ("1".to_string(), 0),
        ];

        scenarios
            .into_iter()
            .enumerate()
            .for_each(|(idx, (input, expected))| {
                let result = Solution::num_steps(input);
                assert_eq!(result, expected);
                println!("  ✓ scenario {}", idx + 1)
            });
    }
}