1017. Convert to Base -2

Leetcode 問題: 1017. Convert to Base -2
Categories:
Tags:

題目

Given an integer n, return a binary string representing its representation in base -2.

Note that the returned string should not have leading zeros unless the string is “0”.

傳入一個整數 n，將它轉換成 -2 進制 的數字

回傳的 -2 進制數字最前方不可以有 0 除非傳入的 整數 n 是 0

Example

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

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

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

2 進制

2 進制計算 2^5 2^4 2^3 2^2 2^1 2^0
10 進制 32 16 8 4 2 1

-2 進制

2 進制計算 -2^5 -2^4 -2^3 -2^2 -2^1 -2^0
10 進制 -32 16 -8 4 -2 1

當 -2 進制 遇到 奇數 次方時，運算出來的答案就會變成 負 的

-3 進制

2 進制計算 -3^5 -3^4 -3^3 -3^2 -3^1 -3^0
10 進制 -243 81 -27 9 -3 1

負進制 遇到 奇數 次方時，運算出來的答案都會變成 負 的

-2 進制轉換數字表

10 進制 -2 進制
10 11110
9 11001
8 11000
7 11011
6 11010
5 101
4 100
3 111
2 110
1 1
0 0
-1 11
-2 10
-3 1101
-4 1100
-5 1111
-6 1110
-7 1001
-8 1000
-9 1011
-10 1010

演算法

餘數運算

1. 餘數運算

因為是除以 -2(負數的 base)，所以原先的% mod 的餘數用來當作轉換後的數字，會有變成負數的狀況

數字運算 餘數
5 % -2 1
4 % -2 0
3 % -2 1
2 % -2 0
1 % -2 1
0 % -2 0
-1 % -2 -1
-2 % -2 0
-3 % -2 -1
-4 % -2 0
-5 % -2 -1

但使用 負數的 base，轉換後的數字也都為正整數，所以需要將餘數都轉換為正整數

2. 計算剩餘待運算數字

計算餘數後，會除以 負數的 base，去取得尚未完成轉換的數字，然後繼續進行轉換

在原本 正數的 base 是無條件捨去，用捨棄後的剩餘數字當作下一個要運算的數字

數字運算 i / -2 Math.floor( i / -2 ) Math.ceil( i / -2 )
-5 / -2 2.5 2 3
-4 / -2 2 2 2
-3 / -2 1.5 1 2
-2 / -2 1 1 1
-1 / -2 0.5 0 1
0 / -2 0 0 0
1 / -2 -0.5 -1 0
2 / -2 -1 -1 -1
3 / -2 -1.5 -2 -1
4 / -2 -2 -2 -2
5 / -2 -2.5 -3 -2

但是因為除以 負數的 base，所以當數字是正數時，除法運算後會變成負數，而無條件捨去後，會取比這個負數小的正整數，所以數字就越取越小，所以必須要無條件進位的方式取得剩餘的數字

Note: 當 base 不是 -2 時算法不太一樣，需要再確認

答案

JavaScript

function baseNeg2(sourceNumber) {
    // 如果來源數字是 0 直接回傳 0
    if (sourceNumber == 0) {
        return '0';
    }
    var negativeTargetBase = -2;
    // 轉換目標數字陣列
    var targetBaseNumberArray = [];
    while (sourceNumber != 0) {
        // 餘數
        var remainderNumber = Math.abs(sourceNumber % negativeTargetBase);
        // 下一進位計算數字
        sourceNumber = Math.ceil(sourceNumber / negativeTargetBase);
        // 轉換目標 base 數字加到前方
        targetBaseNumberArray.unshift(remainderNumber);
    }
    // 目標數字轉換並 join 成答案
    var targetBaseNumber = targetBaseNumberArray.join('');
    return targetBaseNumber;
}

TypeScript

function baseNeg2(sourceNumber: number): string {
    // 如果來源數字是 0 直接回傳 0
    if (sourceNumber == 0) {
        return '0';
    }
    // 目標 base
    let negativeTargetBase = -2;

    // 轉換目標數字陣列
    let targetBaseNumberArray: any = [];

    while (sourceNumber != 0) {
        // 餘數取正數
        let remainderNumber =  Math.abs(sourceNumber % negativeTargetBase);
        // 下一進位計算數字
        sourceNumber = Math.ceil(sourceNumber / negativeTargetBase);
        // 轉換目標 base 數字加到前方
        targetBaseNumberArray.unshift(remainderNumber);
    }

    // 目標數字轉換並 join 成答案
    let targetBaseNumber = targetBaseNumberArray.join('');

    return targetBaseNumber;
};

參考資料