</> MAANG.io

Intermediate

Intermediate problems that train you to pick the right approach: sliding windows, graphs, dynamic programming and more.

0 of 182 solved 0%

Number and Math

What is this?

Four problems that each have an obvious slow solution and a short correct one. Testing every number below n for primality by trial division costs O(n√n); crossing off multiples costs O(n log log n). Checking every triple for the largest product is cubic; sorting once (or one pass) leaves two candidates to compare. Factorising a number fully to ask whether its only prime factors are 2, 3 and 5 is unnecessary; dividing those factors out and checking what is left is three loops. Finding the weekday of a date by simulating every day is slow; counting days from one known anchor date and taking the result mod 7 is a short loop.

The pattern is the same each time: stop asking about every candidate and start eliminating whole classes at once.

Which number shortcut to use

Fun fact: the Sieve of Eratosthenes is more than 2,000 years old and is still the standard way to list primes up to a few million. Two details keep it fast. Start crossing off at p × p: every smaller multiple of p has a smaller prime factor and was already struck out. And stop the outer loop once p × p reaches n, because any composite below n has a prime factor no larger than √n. The total work is O(n log log n).

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.


In short: eliminate classes rather than testing individuals. Divide known factors out, cross off multiples in bulk, sort so that only two candidate answers remain, or count from a known anchor and take a remainder.


1. Divide the factors out

def is_ugly(n):
    if n <= 0:
        return False
    for p in (2, 3, 5):
        while n % p == 0:
            n //= p
    return n == 1

If dividing away every 2, 3 and 5 leaves exactly 1, the number had no other prime factors. The n <= 0 guard matters: zero would loop forever (0 % 2 == 0 is always true) and negatives are excluded by definition. 1 is ugly: no loop runs and the leftover is already 1.

2. Sieve, do not test

def count_primes(n):
    if n < 3:
        return 0
    is_prime = [True] * n
    is_prime[0] = is_prime[1] = False
    p = 2
    while p * p < n:
        if is_prime[p]:
            for multiple in range(p * p, n, p):     # start at p*p, not 2p
                is_prime[multiple] = False
        p += 1
    return sum(is_prime)

Starting at p × p is a saving, not a requirement: every multiple k × p with k < p has a prime factor smaller than p and was already crossed off when that smaller prime was processed.

3. Enumerate the sign cases

The largest product of three numbers is one of exactly two candidates:

  • the three largest values, or
  • the two most negative values times the largest.

The second wins when two large negatives multiply into a large positive. Sorting makes both readable in one line:

nums.sort()
return max(nums[-1] * nums[-2] * nums[-3],
           nums[0] * nums[1] * nums[-1])

There is a linear alternative that tracks the three largest and two smallest in one pass. Mention it as the O(n) improvement once the sorted version is on the board.

4. Count from an anchor

A weekday repeats every 7 days. If you know one date's weekday (1 January 1971 was a Friday), the weekday of any later date is the number of days since the anchor, mod 7. Add 365 or 366 for each full year before the target year, add each full month's length before the target month (February gets a 29th day in a leap year), then add the day of the month minus one. A closed form, Zeller's congruence, does the same in O(1) but is easy to misremember.


5. A 30-second worked example

nums = [-10, -10, 1, 3, 2]

sorted: [-10, -10, 1, 2, 3]

candidate A, three largest:       1 x 2 x 3       = 6
candidate B, two smallest x max: -10 x -10 x 3    = 300  (winner)

answer = 300

Taking only the three largest gives 6 and is wrong. The two negatives cancel, which is exactly the case the second candidate exists to catch.


6. Where you'll actually meet this

  • Cryptography and hashing. Prime generation underpins key selection and table sizing.
  • Numeric libraries. Smooth-number tests (only small prime factors) decide whether a fast Fourier transform size is efficient.
  • Financial and scoring calculations. Extreme-product selections where negative values are meaningful.
  • Load and shard sizing. Choosing sizes with convenient factorisations.
  • Scheduling and calendars. "Every second Tuesday" needs a date-to-weekday mapping that is right across leap years.

7. Problems in this chapter

Ugly Number

Decide whether a number's only prime factors are 2, 3 and 5. Divide each out repeatedly and check that 1 remains.
Pattern: factor elimination. Target: O(log n) time, O(1) space.

Count Primes

Count primes below n. Sieve of Eratosthenes, crossing off from p × p with the outer loop running while p × p < n.
Pattern: sieve. Target: O(n log log n) time, O(n) space.

Maximum Product of Three Numbers

Largest product of any three values. Sort, then take the better of the top three and the two smallest times the largest.
Pattern: sign-case enumeration. Target: O(n log n) sorted, or O(n) with a single tracking pass.

Day of the Week

The weekday for a given date between 1971 and 2100. Count days from the 1971-01-01 anchor (a Friday) and take the result mod 7, or apply Zeller's congruence. The leap-year rule (divisible by 4, except centuries, unless divisible by 400) is the part that must be exactly right, and 2100 is the one century year in range that is not a leap year.
Pattern: anchor and remainder. Target: O(1) for the bounded year range (the loop runs about 130 times at most), O(1) space.


8. Common pitfalls

  • Looping forever on zero in the factor test. Guard n <= 0 first.
  • Starting the sieve at 2p. Correct but does redundant work; p × p is the right lower bound.
  • Running the outer sieve loop to n. It only needs to run while p × p < n.
  • Off-by-one on "below n". Count Primes excludes n itself, so the array has n entries indexed 0..n-1.
  • Taking only the three largest for the product. Two negatives can beat them.
  • Assuming at least one positive value exists. An all-negative array still has a well-defined answer.
  • Overflow. In a 32-bit int, three values of magnitude around 1300 already overflow (1300³ is over 2.1 billion), so use a 64-bit type unless the value range is small.
  • Treating 2100 as a leap year. It is divisible by 100 but not by 400. Apply the leap rule both when summing full years and when adding February's length for the target year.

9. Key takeaways

  1. Eliminate classes, not individuals. Cross off multiples; divide out factors.
  2. p × p and √n are the two details that make a sieve fast.
  3. Two candidates decide the extreme product, and the negative case is the one that gets missed.
  4. Sort for clarity, then offer the linear version. Showing both is stronger than either alone.
  5. Guard the degenerate inputs. Zero, negatives and tiny n are where these fail.
  6. Know the standard complexities. O(n log log n) for a sieve is worth saying precisely.
  7. A weekday is days since an anchor, mod 7. All the difficulty is in the leap-year rule.
  8. Why interviewers like it: short problems with well-known optimal solutions, so they reveal quickly whether you know the standard tools or are improvising.

Order: Ugly Number → Count Primes → Maximum Product of Three Numbers → Day of the Week.

Core idea: Repeatedly divide the number by 2, then 3, then 5 as long as it stays divisible. Each division peels off one of the allowed prime factors. If everything that's left after the peeling is 1, the number was built only from 2s, 3s, and 5s, so it's ugly. If anything else survives, some forbidden prime (7, 11, 13, ...) was hiding inside.

Problem, rephrased

A signal-processing library vectorizes best on FFT lengths that factor entirely into small primes, so before accepting a buffer size it checks the number against the prime whitelist {2, 3, 5}. You're given an integer n, a proposed length.

This is LeetCode 263: Ugly Number.

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.