Trailing Zeros
"count = 0
while n!=0:
n /= 5
count += n
return count"
Count Primes
" def countPrimes(self, n):
if n < 3:
return 0
primes = [True] * n
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
print(len(primes[i * i: n: i]))
return sum(primes)"
twitch_prime_factor
"#Function to check if a number is prime. Function to find the prime factors of a number. Find ALL the prime numbers up to N
def create_sieve(n):
arr = {}
for x in range(2, n + 1):
arr[x] = []
for x in range(2, n + 1):
if arr[x] == []:
iter_prime = 2 * x
while iter_prime <= n:
arr[iter_prime].append(x)
iter_prime += x
return arr
def get_factors(n, sieve):
if n <= 1:
return ""not prime""
if sieve[n] == []:
return ""prime""
else:
return sieve[n]
sieve = create_sieve(100)
print(sieve)
print(1 if get_factors(1, sieve) == ""not prime"" else 0)
print(1 if get_factors(2, sieve) == ""prime"" else 0)
print(1 if get_factors(3, sieve) == ""prime"" else 0)
print(1 if get_factors(4, sieve) == [2] else 0)
print(1 if get_factors(6, sieve) == [2,3] else 0)
print(1 if get_factors(8, sieve) == [2] else 0)
print(1 if get_factors(100, sieve) == [2,5] else 0)"
Sum of Square Numbers
" def judgeSquareSum(self, c):
""""""
:type c: int
:rtype: bool
""""""
if c == 0:
return True
left, right = 0, int(c**0.5)
while left <= right:
if left*left + right*right == c:
return True
elif left*left + right*right < c:
left += 1
else:
right -= 1
return False"
Number of 1 Bits
"count = 0
while n:
n &= n-1
count += 1
return count"
Reverse Bits
" def reverseBits(self, n):
ans = 0
for i in xrange(32):
ans = (ans<<1) | (n&1)
n >>= 1
return ans"
Reverse Integer
"def reverse(self, x):
""""""
:type x: int
:rtype: int
""""""
sign = 1
if x < 0:
sign = -1
x = -x
res = 0
while x != 0:
res = 10*res + x%10
if res > 2**31:
return 0
x /= 10
return sign*res"
Pow(x, n)
" def myPow(self, x, n):
""""""
:type x: float
:type n: int
:rtype: float
""""""
if n < 0:
x = 1 / x
n = -n
pow = 1
while n:
if n & 1:
pow *= x
x *= x
n >>= 1
return pow"
" def myPow(self, x, n):
""""""
:type x: float
:type n: int
:rtype: float
""""""
if n==0:
return 1
elif n==1:
return x
elif n<0:
return self.myPow(1/x, -n)
else:
if n%2==0:
return self.myPow(x*x, n/2)
else:
return self.myPow(x*x, (n-1)/2)*x"
Divide Two Integers
" neg = True if dividend < 0 and divisor > 0 or dividend > 0 and divisor < 0 else False
dividend, divisor = abs(dividend), abs(divisor)
res = 0
while dividend >= divisor:
tmp, i = divisor, 1
while dividend >= tmp:
dividend -= tmp
res += i
i <<= 1
tmp <<= 1
if neg:
res = -res
return min(max(-2**31, res), 2**31-1)"
- Integer to English Words sol: recursion, <20, <100, <1000, else enumerate()
class Solution(object):
def numberToWords(self, num):
"""
:type num: int
:rtype: str
"""
to19 = 'One Two Three Four Five Six Seven Eight Nine Ten Eleven Twelve ' \
'Thirteen Fourteen Fifteen Sixteen Seventeen Eighteen Nineteen'.split()
tens = 'Twenty Thirty Forty Fifty Sixty Seventy Eighty Ninety'.split()
def words(n):
if n < 20:
return to19[n-1:n]
if n < 100:
return [tens[n/10-2]] + words(n%10)
if n < 1000:
return [to19[n/100-1]] + ["Hundred"] + words(n%100)
else:
for k, v in enumerate(("Thousand", "Million", "Billion"), 1):
if n < 1000**(k+1):
return words(n/1000**k) + [v] + words(n%1000**k)
return ' '.join(words(num)) or 'Zero'
Valid Square sol: 4 same lenght, 2 same lenght
class Solution(object):
def validSquare(self, p1, p2, p3, p4):
"""
:type p1: List[int]
:type p2: List[int]
:type p3: List[int]
:type p4: List[int]
:rtype: bool
"""
if p1 == p2 == p3 == p4:
return False
lists = [self.dist(p1, p2), self.dist(p1, p3), self.dist(p1, p4), self.dist(p2, p3), self.dist(p2, p4), self.dist(p3, p4)]
lists.sort()
if lists[0] == lists[1] == lists[2] == lists[3]:
if lists[4] == lists[5]:
return True
return False
def dist(self, n1, n2):
return (n1[0] - n2[0])**2 + (n1[1] - n2[1])**2
- Rectangle Area
overlap = max(min(D, H) - max(B, F), 0) * max(min(C, G) - max(A, E), 0)
return (A-C)*(B-D) + (E-G)*(F-H) - overlap