1017. Convert to Base -2

Given a number N, return a string consisting of "0"s and "1"s that represents its value in base -2 (negative two).

The returned string must have no leading zeroes, unless the string is "0".

 

Example 1:

Input: 2
Output: "110"
Explantion: (-2) ^ 2 + (-2) ^ 1 = 2

Example 2:

Input: 3
Output: "111"
Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3

Example 3:

Input: 4
Output: "100"
Explantion: (-2) ^ 2 = 4

 

Note:

  1. 0 <= N <= 10^9

Rust Solution

struct Solution;

impl Solution {
    fn base_neg2(mut n: i32) -> String {
        if n == 0 {
            return "0".to_string();
        }
        let mut res = vec![];
        while n != 0 {
            res.push((b'0' + (n & 1) as u8) as char);
            n = -(n >> 1);
        }
        res.reverse();
        res.into_iter().collect()
    }
}

#[test]
fn test() {
    let n = 2;
    let res = "110".to_string();
    assert_eq!(Solution::base_neg2(n), res);
    let n = 3;
    let res = "111".to_string();
    assert_eq!(Solution::base_neg2(n), res);
    let n = 4;
    let res = "100".to_string();
    assert_eq!(Solution::base_neg2(n), res);
}

Having problems with this solution? Click here to submit an issue on github.