1017. Convert to Base -2

leetcode medium

#backtracking#csharp#leetcode#math#medium#string

Task

Если задано целое число n, верните двоичную строку, представляющую его в базе -2. Обратите внимание, что возвращаемая строка не должна содержать ведущих нулей, за исключением случаев, когда строка равна "0".

Пример:

Input: n = 2

Output: "110"

C# solution

matched/original

public class Solution {
    public string BaseNeg2(int n) {
        if (n == 0) return "0";
        string res = "";
        while (n != 0) {
            int remainder = n % -2;
            n /= -2;
            if (remainder < 0) {
                remainder += 2;
                n += 1;
            }
            res = remainder.ToString() + res;
        }
        return res;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string BaseNeg2(int n) {
        if (n == 0) return "0";
        string res = "";
        while (n != 0) {
            int remainder = n % -2;
            n /= -2;
            if (remainder < 0) {
                remainder += 2;
                n += 1;
            }
            res = remainder.ToString() + res;
        }
        return res;
    }
}

Java solution

matched/original

public class Solution {
    public String baseNeg2(int n) {
        if (n == 0) return "0";
        StringBuilder res = new StringBuilder();
        while (n != 0) {
            int remainder = n % -2;
            n /= -2;
            if (remainder < 0) {
                remainder += 2;
                n += 1;
            }
            res.insert(0, remainder);
        }
        return res.toString();
    }
}

JavaScript solution

matched/original

class Solution {
    baseNeg2(n) {
        if (n === 0) return "0";
        let res = "";
        while (n !== 0) {
            let remainder = n % -2;
            n = Math.floor(n / -2);
            if (remainder < 0) {
                remainder += 2;
                n += 1;
            }
            res = remainder + res;
        }
        return res;
    }
}

Python solution

matched/original

class Solution:
    def baseNeg2(self, n: int) -> str:
        if n == 0:
            return "0"
        res = ""
        while n != 0:
            n, remainder = divmod(n, -2)
            if remainder < 0:
                remainder += 2
                n += 1
            res = str(remainder) + res
        return res

Go solution

matched/original

func baseNeg2(n int) string {
    if n == 0 {
        return "0"
    }
    res := ""
    for n != 0 {
        remainder := n % -2
        n /= -2
        if remainder < 0 {
            remainder += 2
            n += 1
        }
        res = strconv.Itoa(remainder) + res
    }
    return res
}

Explanation

Algorithm

Инициализация переменных:

Создайте пустую строку для хранения двоичного представления числа.

Используйте цикл для вычисления каждой цифры числа в базе -2.

Вычисление цифр:

В цикле, пока число не равно 0, вычисляйте остаток от деления числа на -2.

Если остаток отрицательный, корректируйте его, добавляя 2, и увеличивайте число на 1.

Добавляйте остаток в начало строки.

Возврат результата:

Верните строку, представляющую число в базе -2. Если строка пустая, верните "0".

😎