Introduction

• a foundational aspect of Computer Science and every programmer and computer scientist needs to have basic mathematical knowledge
• thankfully, for the purpose of coding interviews, there’s usually won't be that much math involved, but some basic math techniques is helpful to know as you may be asked to implement mathematical operations

Topics

GCD

• GCD of two numbers is the greatest number which divides both numbers

Implementation

For two numbers:

• a simple solution is to:
  • first find the minimum of the two numbers
  • then find the highest common factor of that minimum which is also the factor of the other number

"""
@complexity:
Time:  O(min(a,b))
Space: O(1)
"""
#iteratively 
def gcd(a, b):
    result = min(a, b)
 
    while result:
        if a % result == 0 and b % result == 0:
            break
        result -= 1
 
    return result

# recursively
def gcd(a,b):
    if a == 0:
        return b
    return gcd(b % a, a)

• an efficient solution is to use Euclidean algorithm :
  • GCD of two numbers doesn’t change if a smaller number is subtracted from a bigger number.

"""
@complexity:
Time:  O(min(a,b))
Space: O(1)
"""
# recursively
def gcd(a, b):
    if (a == 0):
        return b
    if (b == 0):
        return a

    if (a == b):
        return a
 
    if (a > b):
        return gcd(a-b, b)
    return gcd(a, b-a)

• Instead of Euclidean algorithm by subtraction, a better approach is to not perform subtraction, but continuously divide the bigger number by the smaller number

"""
@complexity:
Time:  O(log(min(a,b)))
Space: O(log(min(a,b)))
"""
# recursively
def gcd(a,b):
    
    if (b == 0):
         return a
    return gcd(b, a%b)

For more numbers:

Prime Factorization and Divisors

LCM (Least Common Multiple)

• LCM of two numbers is the smallest number which can be divided by both numbers.

  e.g. LCM of 15 and 20 is 60

        LCM of 5 and 7 is 35