Ch 6: Math and Logic Puzzles Flashcards
Common Math Puzzle Topics
- Prime Numbers
- Probability Calculation
Prime Numbers:
Essential Concepts
- Prime Factorization (Prime Number Law)
- Divisibility
- Greatest Common Denominator
- Least Common Multiple
- Multiplying GCD and LCM
- Checking for Primality
- Sieve of Eratosthenes
Prime Numbers:
Prime Factorization Law
Every positive integer can be decomposed into a product of primes
Examples:
3 = 2^0 * 3^1
10 = 2^1 * 3^0 * 5^1
84 = 2^2 * 3^1 * 5^0 * 7^1 * 11^0 * 13^0 * …..
Prime numbers in the factorization that are NOT factors have an exponent of 0
Prime Numbers:
Divisibility of Integers:
Is a number Y divisible by X?
Because all integers are products of prime factors,
for a number X to divide a number Y,
All primes in X’s factorization must be present in Y’s factorization.
Y must include all of the prime factors of X.
Formally:
X = 2^j0 * 3^j1 * 5^j2 * 7^j3 * ….
Y = 2^k0 * 3^k1 * 5^k2 * 7^k3 * ….
If X divides Y, then for all i, ji <= ki
Prime Numbers:
Greatest Common Divisor of two Integers
For each prime factor, use the smaller of the exponent between the two numbers:
Formally:
X = 2^j0 * 3^j1 * 5^j2 * 7^j3 * ….
Y = 2^k0 * 3^k1 * 5^k2 * 7^k3 * ….
GCD(X,Y) = 2^min(j0,k0) * 3^min(j1,k1) * 5^min(j2,k2) * …. * p^min(ji, ki)
Prime Numbers:
Least Common Multiple of Two Integers
For each prime factor, use the larger of the exponents between the two numbers:
Formally:
X = 2^j0 * 3^j1 * 5^j2 * 7^j3 * ….
Y = 2^k0 * 3^k1 * 5^k2 * 7^k3 * ….
LCM(X,Y) = 2^max(j0,k0) * 3^max(j1,k1) * 5^max(j2,k2) * …. * p^max(ji, ki)
Prime Numbers:
Three Common Ways to
Check if a Number is Prime
- Naive: Brute Force
Iterate from 2 to n-1,
Checking if n is divisible by the number
O(n) - Improved Naive:
Same, but only check through sqrt(n)
Everything larger is redundant
O(sqrt(n) ) - Sieve of Eratosthenes
Efficiently generates list of numbers 2 to n
If number is in the list, it is prime
Prime Numbers:
Sieve of Eratosthenes
*A highly efficient way to generate a list of prime numbers
* Core concept: all non-prime numbers are divisible by a prime number
Steps:
* Start with a list of numbers up through some value MAX
* Remove all numbers divisible by 2 (except 2)
Note: Can start here for increased efficiency
* Move to the next remaining number, this is the next prime
* Remove all numbers divisible by this prime
* Repeat until reaching sqrt(max)
Note: all non-primes larger than sqrt(max) will have already been
removed at this point
* The list now includes all primes from 2 to MAX
Probability:
Important Concepts
- Venn Diagram
- Bayes Theorem
- Probability of Events A AND B
- Probability of Event A OR B
- Independence
- Mutually Exclusive
Probability:
Bayes’ Theorem
The probability of event A given event B,
is equal to the probability of event B given event A
multiplied by the ratio of the independent probabilities.
P(A given B) = P(B given A) * P(A) / P(B)
Probability of A AND B
P(A and B) = P(B given A) * P(A)
alternatively,
P(A and B) = P(A given B) * P(B)
Together,
P(A given B)P(B) = P(B given A)P(A)
Probability of A OR B
Add the probability of P(A) and P(B).
This includes the intersection probability (A and B) twice,
so subtract it once
P(A or B) = P(A) + P(B) - P(A and B)
Probability:
Independence
Two events are independent if the probability of one happening doesn’t tell you anything about the probability of the other happening.
Probability:
Probability of A AND B when
A and B are independent
P(A and B) = P(A) * P(B)
Probability:
Mutual Exclusivity
If A and B are mutually exclusive, it means that if one happens, the other cannot happen.
Probability:
Probability of A and B
when A and B are mutually exlusive
P(A and B) = 0,
because they are mutually exclusive, it is by definition impossible
for both to happen.
Probability:
Probability of A or B
when A and B are mutually exclusive
P(A or B) = P(A) + P(B)
Note: when A and B are the only options,
this should add up to 100%
Probability:
When are two events both independent
and mutually exclusive
Never.
If the events are mutually exclusive, then one of the events happening
changes the probability of the other event happening(it becomes 0)
Because the probability of mutually exclusive events depends on each other,
they are by definition NOT independent.
Steps for approaching “Puzzle” or “Brainteaser” problems
- Start talking
* Show the interviewer how you approach a problem - Develop Rules and Patterns
* As you work through the problem, write down rules or patterns that
you discover or remember. - Wost Case Shifting
* Many brainteasers are worst-case minimization problems
* Minimize an action or do something AT MOST X times
* Try to “balance” the worst case:
* If an early decision skews the worst case, change decision to make
it better. - Use Algorithmic Approaches
* If stuck, use approaches for developing algorithms
* Brainteasers are often algorithm questions with technical aspects
removed
Problem Solving:
2 Especially useful
Algorithm Strategies
for Brainteaser problems
- Base Case
- Do It Yourself
