Skip to content

Bit Others

Table of Contents

136. Single Number

from functools import reduce
from operator import xor
from typing import List


# XOR
def singleNumber(nums: List[int]) -> int:
    res = 0
    for num in nums:
        res ^= num
    return res


# XOR
def singleNumberXOR(nums: List[int]) -> int:
    return reduce(xor, nums)


# XOR
def singleNumberXORLambda(nums: List[int]) -> int:
    return reduce(lambda x, y: x ^ y, nums)


nums = [4, 1, 2, 1, 2]
print(singleNumber(nums))  # 4
print(singleNumberXOR(nums))  # 4
print(singleNumberXORLambda(nums))  # 4

287. Find the Duplicate Number

"""
-   Find the duplicate number in an array containing `n + 1` integers where each integer is between `1` and `n` inclusive.
-   Floyd's Tortoise and Hare (Cycle Detection)
    -   141. Linked List Cycle
    -   142. Linked List Cycle II
-   Time Complexity: O(n)
-   Space Complexity: O(1)

Example: `nums = [1, 3, 4, 2, 2]`

|  0   |  1   |  2   |  3   |  4   |
| :--: | :--: | :--: | :--: | :--: |
|  1   |  3   |  4   |  2   |  2   |


"""

from typing import List


# Floyd Cycle Detection Algorithm
def findDuplicate(nums: List[int]) -> int:
    fast, slow = nums[0], nums[0]

    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break

    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]

    return slow


nums = [1, 3, 4, 2, 2]
print(findDuplicate(nums))  # 2

260. Single Number III

2965. Find Missing and Repeated Values

137. Single Number II

645. Set Mismatch

190. Reverse Bits

# Bit Manipulation
def reverseBits(n: int) -> int:
    res = 0

    for i in range(32):
        res = (res << 1) | (n & 1)
        n >>= 1

    return res


n = 0b00000010100101000001111010011100
print(reverseBits(n))  # 964176192

371. Sum of Two Integers

# Bit Manipulation
def getSum(a: int, b: int) -> int:
    MASK = 0xFFFFFFFF
    MAX_INT = 0x7FFFFFFF

    while b != 0:
        temp = (a ^ b) & MASK
        b = ((a & b) << 1) & MASK
        a = temp

    return a if a <= MAX_INT else ~(a ^ MASK)


print(getSum(1, 2))  # 3

201. Bitwise AND of Numbers Range

2154. Keep Multiplying Found Values by Two

2044. Count Number of Maximum Bitwise-OR Subsets

2438. Range Product Queries of Powers

1680. Concatenation of Consecutive Binary Numbers

1261. Find Elements in a Contaminated Binary Tree

  • LeetCode | 力扣

  • Tags: Hash Table, Tree, Depth First Search, Breadth First Search, Design, Binary Tree

89. Gray Code

1238. Circular Permutation in Binary Representation

982. Triples with Bitwise AND Equal To Zero

3307. Find the K-th Character in String Game II

1611. Minimum One Bit Operations to Make Integers Zero

751. IP to CIDR

3141. Maximum Hamming Distances

Comments