"""
# 67. Add Binary

Given two binary strings `a` and `b`, return their sum as a binary string.

## Examples

```text
Input: a = "11", b = "1"
Output: "100"

Input: a = "1010", b = "1011"
Output: "10101"
```

## Constraints
- 1 <= a.length, b.length <= 10^4
- a and b consist only of '0' or '1' characters.
- Each string does not contain leading zeros except for the zero itself.
"""


class Solution:
    def addBinary(self, a: str, b: str) -> str:
        # Simulate binary addition from right to left with carry
        # O(max(m,n)) time — iterate from end with carry, build result in reverse
        i, j, carry = len(a) - 1, len(b) - 1, 0
        result = []
        while i >= 0 or j >= 0 or carry:
            total = carry
            if i >= 0:
                total += ord(a[i]) - 48
                i -= 1
            if j >= 0:
                total += ord(b[j]) - 48
                j -= 1
            result.append(str(total % 2))
            carry = total // 2
        return ''.join(reversed(result))


if __name__ == '__main__':
    s = Solution()
    assert s.addBinary("11", "1") == "100"
    assert s.addBinary("1010", "1011") == "10101"
    assert s.addBinary("0", "0") == "0"
    print("All tests passed.")

"""
# 201. Bitwise AND of Numbers Range

Given two integers `left` and `right` that represent the range `[left, right]`,
return the bitwise AND of all numbers in this range, inclusive.

## Examples

```text
Input: left = 5, right = 7
Output: 4

Input: left = 0, right = 0
Output: 0

Input: left = 1, right = 2147483647
Output: 0
```

## Constraints
- 0 <= left <= right <= 2^31 - 1
"""


class Solution:
    def rangeBitwiseAnd_shift(self, left: int, right: int) -> int:
        # O(32) time — right-shift both until equal to find common prefix
        shift = 0
        while left != right:
            left >>= 1
            right >>= 1
            shift += 1
        return left << shift

    def rangeBitwiseAnd(self, left: int, right: int) -> int:
        # Right-shift both until equal: common prefix of all numbers in range
        # Bits that differ across the range will be 0 in the AND result
        # O(32) time — Brian Kernighan: strip lowest set bit of right until right <= left
        while right > left:
            right &= right - 1
        return right


if __name__ == '__main__':
    s = Solution()
    for method in (s.rangeBitwiseAnd_shift, s.rangeBitwiseAnd):
        assert method(5, 7) == 4
        assert method(0, 0) == 0
        assert method(1, 2147483647) == 0
    print("All tests passed.")

"""
# 338. Counting Bits

Given an integer `n`, return an array `ans` of length `n + 1` such that for each `i`
(0 <= i <= n), `ans[i]` is the number of 1's in the binary representation of `i`.

## Examples

```text
Input: n = 2
Output: [0,1,1]

Input: n = 5
Output: [0,1,1,2,1,2]
```

## Constraints
- 0 <= n <= 10^5
"""

from typing import List


class Solution:
    def countBits_naive(self, n: int) -> List[int]:
        # O(n * 32) time — count bits for each number independently
        def count(x: int) -> int:
            c = 0
            while x:
                x &= x - 1
                c += 1
            return c
        return [count(i) for i in range(n + 1)]

    def countBits(self, n: int) -> List[int]:
        # dp[i] = dp[i >> 1] + (i & 1): right shift removes last bit, add it back
        # O(n) time — dp: bits[i] = bits[i >> 1] + (i & 1)
        dp = [0] * (n + 1)
        for i in range(1, n + 1):
            dp[i] = dp[i >> 1] + (i & 1)
        return dp


if __name__ == '__main__':
    s = Solution()
    for method in (s.countBits_naive, s.countBits):
        assert method(2) == [0, 1, 1]
        assert method(5) == [0, 1, 1, 2, 1, 2]
    print("All tests passed.")

"""
# 3133. Minimum Array End

You are given two integers `n` and `x`. You have to construct an array of **positive** integers
`nums` of size `n` where for every `0 <= i < n - 1`, `nums[i + 1]` is greater than `nums[i]`,
and the result of the bitwise AND of all elements of `nums` is `x`.

Return the **minimum** possible value of `nums[n - 1]`.

## Examples

```text
Input: n = 3, x = 4
Output: 6
Explanation: nums = [4, 5, 6], AND = 4 & 5 & 6 = 4.

Input: n = 2, x = 7
Output: 15
Explanation: nums = [7, 15], AND = 7 & 15 = 7.
```

## Constraints
- 1 <= n, x <= 10^8
"""


class Solution:
    def minEnd(self, n: int, x: int) -> int:
        # Fill the 0-bits of x with bits of (n-1) in order
        # This gives the smallest number >= x that ANDs with x to give x
        # O(64) time — embed (n-1) into the zero-bits of x to get minimum last element
        result = x
        remaining = n - 1
        bit = 1
        while remaining:
            if not (result & bit):          # bit position is free (0 in x)
                if remaining & 1:
                    result |= bit
                remaining >>= 1
            bit <<= 1
        return result


if __name__ == '__main__':
    s = Solution()
    assert s.minEnd(3, 4) == 6
    assert s.minEnd(2, 7) == 15
    assert s.minEnd(1, 1) == 1
    print("All tests passed.")

"""
# 268. Missing Number

Given an array `nums` containing `n` distinct numbers in the range `[0, n]`,
return the only number in the range that is missing from the array.

## Examples

```text
Input: nums = [3,0,1]
Output: 2

Input: nums = [0,1]
Output: 2

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
```

## Constraints
- n == nums.length
- 1 <= n <= 10^4
- 0 <= nums[i] <= n
- All the numbers of nums are unique.
"""

from typing import List


class Solution:
    def missingNumber_sum(self, nums: List[int]) -> int:
        # O(n) time, O(1) space — expected sum minus actual sum
        n = len(nums)
        return n * (n + 1) // 2 - sum(nums)

    def missingNumber(self, nums: List[int]) -> int:
        # XOR all indices 0..n with all values; pairs cancel, leaving the missing number
        # O(n) time, O(1) space — XOR all indices and values; pairs cancel out
        result = len(nums)
        for i, n in enumerate(nums):
            result ^= i ^ n
        return result


if __name__ == '__main__':
    s = Solution()
    for method in (s.missingNumber_sum, s.missingNumber):
        assert method([3, 0, 1]) == 2
        assert method([0, 1]) == 2
        assert method([9, 6, 4, 2, 3, 5, 7, 0, 1]) == 8
    print("All tests passed.")

"""
# 191. Number of 1 Bits

Given a positive integer `n`, write a function that returns the number of set bits
in its binary representation (also known as the **Hamming weight**).

## Examples

```text
Input: n = 11
Output: 3
Explanation: 11 in binary is 1011, which has 3 set bits.

Input: n = 128
Output: 1
Explanation: 128 in binary is 10000000, which has 1 set bit.

Input: n = 2147483645
Output: 30
```

## Constraints
- 1 <= n <= 2^31 - 1
"""


class Solution:
    def hammingWeight_each_bit(self, n: int) -> int:
        # O(32) time — check each of the 32 bits with a mask
        count = 0
        for _ in range(32):
            count += n & 1
            n >>= 1
        return count

    def hammingWeight(self, n: int) -> int:
        # n & (n-1) clears the lowest set bit; count how many times until n=0
        # O(k) time where k = number of set bits — n & (n-1) clears lowest set bit
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count


if __name__ == '__main__':
    s = Solution()
    for method in (s.hammingWeight_each_bit, s.hammingWeight):
        assert method(11) == 3
        assert method(128) == 1
        assert method(1) == 1
    print("All tests passed.")

"""
# 190. Reverse Bits

Reverse bits of a given 32 bits unsigned integer.

## Examples

```text
Input: n = 00000010100101000001111010011100
Output:    964176192 (00111001011110000010100101000000)

Input: n = 11111111111111111111111111111101
Output:    3221225471 (10111111111111111111111111111111)
```

## Constraints
- The input must be a binary string of length 32.
"""


class Solution:
    def reverseBits_bitbybit(self, n: int) -> int:
        # O(32) time — shift bits one at a time into result
        result = 0
        for _ in range(32):
            result = (result << 1) | (n & 1)
            n >>= 1
        return result

    def reverseBits(self, n: int) -> int:
        # For each of 32 bits: shift result left, OR in the lowest bit of n, shift n right
        # O(1) time — divide and conquer: swap 16, 8, 4, 2, 1-bit groups
        n = (n >> 16) | (n << 16)
        n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)
        n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)
        n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)
        return n & 0xFFFFFFFF


if __name__ == '__main__':
    s = Solution()
    for method in (s.reverseBits_bitbybit, s.reverseBits):
        assert method(43261596) == 964176192
        assert method(0) == 0
        assert method(0xFFFFFFFF) == 0xFFFFFFFF
    print("All tests passed.")

"""
# 7. Reverse Integer

Given a signed 32-bit integer `x`, return `x` with its digits reversed.
If reversing `x` causes the value to go outside the signed 32-bit integer range [-2^31, 2^31 - 1],
return 0.

**Assume the environment does not allow you to store 64-bit integers (signed or unsigned).**

## Examples

```text
Input: x = 123
Output: 321

Input: x = -123
Output: -321

Input: x = 120
Output: 21
```

## Constraints
- -2^31 <= x <= 2^31 - 1
"""

INT_MIN, INT_MAX = -(2**31), 2**31 - 1


class Solution:
    def reverse_string(self, x: int) -> int:
        # O(log n) time — convert to string, reverse, check overflow
        sign = -1 if x < 0 else 1
        rev = int(str(abs(x))[::-1]) * sign
        return rev if INT_MIN <= rev <= INT_MAX else 0

    def reverse(self, x: int) -> int:
        # Extract digits via mod 10, build reversed number; check 32-bit overflow
        # O(log n) time — extract digits with modulo, check overflow before each step
        sign = -1 if x < 0 else 1
        x = abs(x)
        result = 0
        while x:
            x, digit = divmod(x, 10)
            result = result * 10 + digit
        result *= sign
        return result if INT_MIN <= result <= INT_MAX else 0


if __name__ == '__main__':
    s = Solution()
    for method in (s.reverse_string, s.reverse):
        assert method(123) == 321
        assert method(-123) == -321
        assert method(120) == 21
        assert method(1534236469) == 0  # overflow
    print("All tests passed.")

"""
# 136. Single Number

Given a non-empty array of integers `nums`, every element appears **twice** except for one.
Find that single one.

You must implement a solution with linear runtime complexity and use only constant extra space.

## Examples

```text
Input: nums = [2,2,1]
Output: 1

Input: nums = [4,1,2,1,2]
Output: 4

Input: nums = [1]
Output: 1
```

## Constraints
- 1 <= nums.length <= 3 * 10^4
- -3 * 10^4 <= nums[i] <= 3 * 10^4
- Each element in the array appears twice except for one element which appears only once.
"""

from typing import List


class Solution:
    def singleNumber_set(self, nums: List[int]) -> int:
        # O(n) time, O(n) space — hash set: add if unseen, remove if seen
        seen = set()
        for n in nums:
            if n in seen:
                seen.remove(n)
            else:
                seen.add(n)
        return seen.pop()

    def singleNumber(self, nums: List[int]) -> int:
        # XOR all numbers: pairs cancel out (a^a=0), leaving the single number
        # O(n) time, O(1) space — XOR cancels pairs, leaving the single element
        result = 0
        for n in nums:
            result ^= n
        return result


if __name__ == '__main__':
    s = Solution()
    for method in (s.singleNumber_set, s.singleNumber):
        assert method([2, 2, 1]) == 1
        assert method([4, 1, 2, 1, 2]) == 4
        assert method([1]) == 1
    print("All tests passed.")

"""
# 371. Sum of Two Integers

Given two integers `a` and `b`, return the sum of the two integers without using
the operators `+` and `-`.

## Examples

```text
Input: a = 1, b = 2
Output: 3

Input: a = 2, b = 3
Output: 5
```

## Constraints
- -1000 <= a, b <= 1000
"""


class Solution:
    def getSum(self, a: int, b: int) -> int:
        # XOR gives sum without carry; AND<<1 gives the carry
        # Repeat until no carry remains; mask to 32 bits to handle negatives
        # O(32) time — XOR gives sum without carry; AND<<1 gives carry; repeat until no carry
        mask = 0xFFFFFFFF
        while b & mask:
            carry = (a & b) << 1
            a = a ^ b
            b = carry
        # handle negative numbers in Python's arbitrary precision integers
        return a if b == 0 else a & mask if (a & (mask + 1)) else a


if __name__ == '__main__':
    s = Solution()
    assert s.getSum(1, 2) == 3
    assert s.getSum(2, 3) == 5
    assert s.getSum(-1, 1) == 0
    assert s.getSum(-5, 3) == -2
    print("All tests passed.")