class Solution {
    /**
     * Input: digits = [4,3,2,1]
     * Output: [4,3,2,2]
     * Explanation: The array represents the integer 4321.
     * Incrementing by one gives 4321 + 1 = 4322.
     * Thus, the result should be [4,3,2,2].
     */
    // 從最後一位數開始遍歷(向前)，不為9時直接加一，為9時讓當前元素重置為0(進位了)
    public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            // 如果等於 9 ，重置為0
            if (digits[i] == 9){
                digits[i] = 0;
            } else {
                // 不為9，直接加一返回
                digits[i] ++;
                return digits;
            }
        }
        // 循環出來如果沒返回(原數字剛好是999之類的情況)，
        // 所有的位都已經重置為0了 ，只需要數組擴容，在第一位數加一即可
        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }
}

class Solution {
    /**
     * Input: a = "1010", b = "1011"
     * Output: "10101"
     */
    public String addBinary(String a, String b) {
        StringBuilder res = new StringBuilder(); // 預計返回的結果
        int i = a.length() - 1; // 標記遍歷到 a 的位置，準備從最後一位向前遍歷
        int j = b.length() - 1; // 標記遍歷到 b 的位置
        int carry = 0; // 進位
        while (i >= 0 || j >= 0 || carry != 0) { // a 沒遍歷完，或 b 沒遍歷完，或進位不為 0
            int digitA = (i >= 0 ? a.charAt(i) - '0' : 0); // 當前 a 的取值(如果是'1' - '0' 剛好就是1)
            int digitB = (j >= 0 ? b.charAt(j) - '0' : 0); // 當前 b 的取值
            int sum = digitA + digitB + carry; // 當前位置相加的結果
            carry = (sum >= 2 ? 1 : 0); // 是否有進位(相加=2就是要進位)
            sum = (sum >= 2 ? sum - 2 : sum); // 去除進位后留下的数字
            res.append(sum); // 把去除進位后留下的数字拼接到結果中
            // 若最後一次有進位也是while的第三個條件，不會遺漏
            i--;  // 遍歷到 a 的位置向左移動
            j--;  // 遍歷到 b 的位置向左移動
        }
        return res.reverse().toString(); // 把結果反轉並返回
    }
}

/**
 * Input: x = 8
 * Output: 2
 * Explanation: The square root of 8 is 2.82842...,
 * and since the decimal part is truncated, 2 is returned.
 */
public class Solution {
    public int mySqrt(int x) {
        // 特殊值判斷
        if (x == 0) {
            return 0;
        }
        if (x == 1) {
            return 1;
        }

        int left = 1;
        int right = x / 2;
        // 在區間 [left..right] 查找目標元素
        while (left < right) {
            // mid需要進位，否則最後區間剩2數時會卡死
            int mid = left + (right - left + 1) / 2;

            if (mid > x / mid) {
                // 下一輪搜索區間是 [left..mid - 1]
                right = mid - 1;
            } else {
                // 下一輪搜索區間是 [mid..right]
                left = mid;
            }
        }
        return left;
    }
}