cpps: math

[hon9g]

modulabs cpps study ✔️ Problems from LeetCode 🌐

#	title	my solution
1	Reverse Integer	✔️
2	Palindrome Number
3	Divide Two Integers	✔️
4	Happy Number	✔️
5	Count Primes	✔️
6	Perfect Squares
7	Least Operators to Express Number

[hon9g]

Q1. Reverse Integer

• 🌐problem

convert int to str to int

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

  class Solution:
  def reverse(self, x: int) -> int:
     flag = 1
     if x < 0:
         flag = -1
     y = int(str(x*flag)[::-1])*flag
     if y > (2**31) -1 or y < (2**31)*-1:
         return 0
     return y

[hon9g]

Q2. Palindrome Number

• 🌐problem
• Time complexity: O()
• Space complexity: O()

[hon9g]

Q3. Divide Two Integers

• 🌐problem
• Time complexity: O()
• Space complexity: O()

  class Solution:
  def divide(self, dividend: int, divisor: int) -> int:
      isMinus = ['+', '+']
      dividend = str(dividend)
      if dividend[0] == '-':
          isMinus[0] = '-'
          dividend = dividend[1:]
      if divisor < 0:
          isMinus[1] = '-'
          divisor = str(divisor)[1:]
          divisor = int(divisor)        
      remain = ''
      result = []
      for d in dividend:
          remain += d
          if int( remain ) < divisor:
              result.append('0')
              continue
          remain = int( remain )
          times = 0
          while remain-divisor >= 0:
              remain -= divisor
              times += 1
          else:
              result.append(str(times))
              remain = str(remain)
      result = ''.join(result)
      if int(result) >= (2**31):
          return (2**31)-1 if isMinus[0] == isMinus[1] else (2**31)*-1
      if isMinus[0] != isMinus[1]:
          result = '-' + result
      return int(result)

[hon9g]

Q4. Happy Number

• 🌐problem
• Time complexity: O()
• Space complexity: O(N)

class Solution:
    def getNext(self, n: int) -> int:
        answer = 0
        for i in str(n):
            answer += int(i)**2
        return answer

    def isHappy(self, n: int) -> bool:
        seen = set()
        while n != 1:
            if n in seen:
                return False
            seen.add(n)
            n = self.getNext(n)
        return True

[hon9g]

Q5. Count Primes

• 🌐problem
• Time complexity: O(N^2)
• Space complexity: O(N)

  class Solution:
  def countPrimes(self, n: int) -> int:
      if n < 3:
          return 0
      if n == 3:
          return 1
      cnt = 1
      notPrime = set()
      for i in range(3, n, 2):
          if i not in notPrime:
              cnt += 1
              k = 2
              while i*k < n:
                  notPrime.add(i*k)
                  k += 1
      return cnt

[hon9g]

Q6. Perfect Squares

• 🌐problem
• Time complexity: O()
• Space complexity: O()

[hon9g]

Q7. Least Operators to Express Number

• 🌐problem
• Time complexity: O()
• Space complexity: O()