[HackerRank 30 days of code] [第10天] Binary Numbers

最近開始HackerRank的30天程式挑戰，今天碰到稍微需要動腦的題目，順手來記錄一下 (前幾天的題目基本上沒動到什麼腦，所以就省略不寫了……)。

題目大意

題目連結在此：Day 10: Binary Numbers

這題會給定一個十進位的整數 n 當作輸入，題目要求我們將 n 轉為二進位，並且計算 n 在二進位表示下，有多少個連續的1。

例如:
n = 125
則 125₁₀ 可以用二進位表示成 1111101₂，可以發現二進位表示法當中總共有5個連續的1出現，因此最終輸出 5 。

我的解題方式

回憶10進位轉2進位的方式

這邊的做法是使用短除法，對要被轉換的數一直除以2，並記錄每次除2得到的餘數。記得當年大學上數位邏輯是這樣寫的：

我在網路上找到了一篇新竹中學的教材，可以做為參考：電腦數值資料的換算 (Archive)

十進位轉二進位的程式

姑且不論如何計算連續的1，單就十進位轉二進位就可以用迴圈辦到。用Java來寫的話程式大概會長這樣：

public static short[] decimalToBinary(int n) {
    int quotient = n;
    while (quotient != 0) {
        short bit = (short) (quotient % 2);

        // 設法紀錄餘數 bit...
        quotient = quotient / 2;
    }
    
    // 設法回傳結果...
}

其實就是對一個數值不斷除以2，然後把商記錄下來繼續除。迴圈的停止條件是當商(quotient)等於0的時候，其實就是 1 / 2 發生的時候。由於我們用整數型態來儲存商，所以當 1 / 2 發生時得到的值會是0而非浮點數0.5。

上一個段落用短除法說明時，當遇到1就停止不除了，接著把最後一個商當作二進位的最左邊的位數，依序由下往上解讀餘數。換個想法，由於我們用MOD(%)來取餘數，而1 % 2的值會是1，所以我們其實可以一路取餘數到底而不用特別去讀商的值。

紀錄1的連續出現次數

我的想法是先用一個變數儲存連續1的數量，我把這個變數叫做consecutiveCount。只要短除法的餘數出現1，就在consecutiveCount加1。反之，如果餘數是0，則代表連續的1已經中斷，所以直接把consecutiveCount設為0。

紀錄最大的連續出現次數

我另外宣告了一個變數來儲存最大的連續出現次數，我叫那個變數。maxConsecutiveCount當我更新consecutiveCount之後，我馬把consecutiveCount和maxConsecutiveCount比較，如果目前的連續出現次數大於目前最大的連續出現次數，則更新最大出現次數。

綜合上面的敘述，最終程式碼長這樣：

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;



public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        bufferedReader.close();
        
        
        int quotient = n;
        int maxConsecutiveCount = 0;
        int consecutiveCount = 0;
        while (quotient != 0) {
            short currenBit = (short) (quotient % 2);
            if (currenBit == 1) {
                consecutiveCount += 1;
                maxConsecutiveCount = Math.max(maxConsecutiveCount, consecutiveCount);
            } else {
                consecutiveCount = 0;
            }
            quotient = quotient / 2;
        }
        
        System.out.println(maxConsecutiveCount);
    }
}

後記

如果不來做HackerRank的題目，其實我大概也沒什麼機會回憶這種2進位的轉換。其實剛看到題目的時候我幾乎快把短除法給忘了，只能說溫故而知新是很重要的。另外本來想評估一下上面那段程式的時間複雜度，無奈演算法我也還給老師還得差不多了，只能很心虛地說時間複雜度的BigO大概是 log₂n ? 真的該找機會回去回憶一下……

如果有發現錯誤或能改進之處，歡迎透過留言指教!