Math
Palindrome Number (Easy)
Given an integer x, return true if x is a palindrome, and false otherwise.
def isPalindrome(x: int) -> bool: if x < 0: return False original, reverse = x, 0 while x > 0: reverse = reverse * 10 + x % 10 x = x // 10 return original == reverse
Time: O(n)
Space: O(1)
Alternative solution:
def isPalindrome(x: int) -> bool: if x == 0: return True if x < 0 or x % 10 == 0: return False reverse = 0 # Only check until middle digit while x > reverse: reverse = reverse * 10 + x % 10 x = x // 10 return x == reverse or x == reverse // 10
Time: O(n)
Space: O(1)
Plus One (Easy)
You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's.
Increment the large integer by one and return the resulting array of digits.
def plusOne(digits: List[int]) -> List[int]: for i in range(len(digits) - 1, -1, -1): if digits[i] < 9: digits[i] += 1 return digits digits[i] = 0 # Only reach this line if there is a carry return [1] + digits
Time: O(n)
Space: O(1)
Sqrt(x) (Easy)
Given a non-negative integer x, return the square root of x rounded down to the nearest integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator. For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
def mySqrt(x: int) -> int: # Binary search left, right = 1, x while left <= right: mid = (left + right) // 2 if mid * mid > x: right = mid - 1 else: left = mid + 1 # right is the last candidate that was not too large return right
Time: O(log n)
Space: O(1)
Factorial Trailing Zeroes (Medium)
Given an integer n, return the number of trailing zeroes in n!.
Note that n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1.
def trailingZeroes(n: int) -> int: # Trailing zeroes come from 5 * an even number (5 * 2 = 10) # Powers of 5 create more than 1 zero (25 * 4 = 100, 125 * 8 = 1000) # The goal is to count all multiples of 5^x count, multiple = 0, 5 while n >= multiple: count += n // multiple # 5, 25, 125, 625, ... multiple *= 5 return count
Time: O(log n)
Space: O(1)
Pow(x, n) (Medium)
Implement pow(x, n), which calculates x raised to the power n (i.e. x^n).
# Brute force solution of looping n times is slow if n is large # Example: x = 5, n = 11 (5^11) # 11 in binary = 1011 ---> 5^11 = 5^8 * 5^2 * 5^1 # Loop n in binary, multiplying answer only when current bit == 1 def myPow(x: float, n: int) -> float: # Use reciprocal if n is negative if n < 0: n = -n x = 1 / x answer = 1 while n: if n & 1: answer *= x # Double power of x to match n position (x^4 * x^4 = x^8) x *= x # Shift n right once to get next binary bit n >>= 1 return answer
Time: O(log n)
Space: O(1)