Transcript Math
Mathematical
Approach
Many of these problems read as brain teasers at first, but
can be worked through in a logical way.
Just remember to rely on the rules of mathematics to
develop an approach, and then to carefully translate that
idea into code.
Example
Given two numbers m and n, write a method to return
the first number r that is divisible by both (e.g., the least
common multiple).
hints
What does it mean for r to be divisible by m and n?
It means that all the primes in m must go into r, and all primes
in n must be in r.
What if m and n have primes in common?
For example, if m is divisible by 3^5 and n is divisible by 3^7,
what does this mean about r?
It means r must be divisible by 3^7.
The Rule
For each prime p such that p^a \ m (e.g., m is divisible by p^a) and p^b \ n,
r must be divisible by p^max(a, b).
Find the LCM of these sets of numbers.
3, 9, 21
Solution: List the prime factors of each.
3: 3
9: 3 × 3
21: 3 × 7
63 can be divided evenly by 3, 9, and 21.
12, 80
Solution: List the prime factors of each.
12: 2 × 2 × 3
80: 2 × 2 × 2 × 2 × 5 = 80
240 can be divided by both 12 and 80.
Algorithm
Prime
A number is prime if it is only divisible by 1 and itself. So
for example 2, 3, 5, 79, 311 and 1931 are all prime, while
21 is not prime because it is divisible by 3 and 7.
To find if a number n is prime we could simply check if it
divides any numbers below it.
We can use the modulus (%) operator to check for
divisibility:
Solution
for (int i=2; i<n; i++)
if (n%i==0)
return false;
return true;
We can make this code run faster by noticing that we
only need to check divisibility for values of i that are less
or equal to the square root of n
Implementation
public boolean isPrime (int n) {
if (n<=1)
if (n==2)
return true;
if (n%2==0)
return false;
return false;
int m=Math.sqrt(n);
for (int i=3; i<=m; i+=2)
if (n%i==0)
}
return false;
return true;
Problem
Design an algorithm to find the kth number such that the
only prime factors are 3, 5, and 7.
Hints
Hints
3 * (previous number in list)
5 * (previous number in list)
7 * (previous number in list)
How would we find the next number in the list?
Well, we could multiply 3, 5 and 7 times each number in the list
and find the smallest element that has not yet been added to
our list.
This solution is O(n^2).
Not bad, but I think we can do better
Hints
3
5
7
3
3*3
3*5
3*7
5
5*3
5*5
5*7
7
7*3
7*5
7*7
Red: duplications
3*3
3*5
3*7
5*5
7*7
3
3*3*3
3*3*5
3*3*7
3*5*5
3*7*7
5
5*3*3
5*5*3
5*3*7
5*5*5
5*7*7
7
7*3*3
7*3*5
7*3*7
7*5*5
7*7*7
Hints
In our current algorithm, we’re doing 3*1, 3*3, 3*5, 3*7,
3*9, 3*15, 3*21, 3*25 …, and the same for 5 and 7.We’ve
already done almost all this work before—why are we
doing it again?
We can fix this by multiplying each number we add to our
list by 3, 5, 7 and putting the results in one of the three
first-in-first-out queues.
To look for the next “magic” number, we pick the smallest
element in the three queues.
Solution