cpps: bit manipulation

[hon9g]

modulabs cpps study ✔️ Problems from LeetCode 🌐

#	title	my solution
1	Subsets	O(N 2^N)/O(N 2^N)✔️
2	Single Number	O(N)/O(1)✔️
3	Single Number II
4	Majority Element	O(N lg N)/O(1)✔️
5	Bitwise AND of Numbers Range	if len(bin((m)) == len(bin(n)) O(n-m) else O(n) / O(1)
6	Missing Number
7	Sum of Two Integers
8	UTF-8 Validation

[hon9g]

Clear

• i번째 비트 삭제

  def clearBitsthoughI(num: int, i: int) -> int:
  mask = (1 << i) -1
  return num & mask

• i부터 1의자리까지 비트 모두 삭제

  def clearBitsFromIthough0(num: int, i: int) -> int:
  mask = (1 << i) -1
  return num & ~mask

[hon9g]

Q1. Subsets

• Time complexity: O(N* 2^N)
• Space complexity: O(N* 2^N)

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        result = []
        for i in range(2**n):
            mask = str(bin(i))[2:]
            m = len(mask)
            if m < n:
                mask = '0'*(n-m) + mask
            sub = []
            for j in range(n):
                if mask[j] == '1':
                    sub.append(nums[j])
            result.append(sub)
        return result

[hon9g]

Q2. Single Number

• Time complexity: O(N)
• Space complexity: O(1)

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        n = 0
        for num in nums:
            n ^= num
        return n   

[hon9g]

Q3. Single Number II

• Time complexity:
• Space complexity:

[hon9g]

Q4. Majority Element

solution with sorting + counting

• Time complexity: O(N log N)
• Space complexity: O(1)

  class Solution:
  def majorityElement(self, nums: List[int]) -> int:
      nums = sorted(nums)
      cnt, half, prev = 0, len(nums)//2, nums[0]
      for num in nums:
          if prev != num:
              cnt = 0
          cnt += 1
          prev = num
          if half < cnt:
              break
      return prev

[hon9g]

Q5. Bitwise AND of Numbers Range

brute force

• Time complexity: O(n-m)
• Space complexity: O(1)
• Occur Time Limit Exceeded at input like m, n = 20000, 2147483647

  class Solution:
  def rangeBitwiseAnd(self, m: int, n: int) -> int:
      if m == 0:
          return 0
      for num in range(m+1, n+1):
          m &= num
      return m

  compare bits length

• Time complexity: when it have same bit length O(m-n) else O(1)
• Space complexity: O(1)

  class Solution:
  def rangeBitwiseAnd(self, m: int, n: int) -> int:
      if len(bin(m)) != len(bin(n)):
          return 0
      for num in range (m+1, n+1):
          m &= num
      return m