Find smallest N for 5-and-21 sums
Company: Schonfeld
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given two positive integers: 5 and 21. We say a positive integer `x` is **representable** if it can be written in the form
\[
x = 5a + 21b
\]
for some non‑negative integers `a` and `b` (i.e., using any number of 5s and 21s, order does not matter).
For example, 99 is representable because:
- 99 = 21 + 21 + 21 + 21 + 5 + 5 + 5.
Find the **smallest integer N** such that **every integer greater than or equal to N** is representable.
Output this minimal value of `N`.
Quick Answer: This question evaluates understanding of integer linear combinations and elementary number theory, framed as a Frobenius coin problem that examines representability using non-negative multiples of 5 and 21.
You are given two positive integers `p` and `q`. A positive integer `x` is **representable** if it can be written as
```
x = p*a + q*b
```
for some non-negative integers `a` and `b` (any number of `p`s and any number of `q`s, order does not matter).
For example, with `p = 5` and `q = 21`, the value 99 is representable because `99 = 21+21+21+21+5+5+5`.
Return the **smallest integer N** such that **every** integer greater than or equal to `N` is representable.
Special cases:
- If `p` and `q` share a common factor greater than 1, only multiples of that factor are ever representable, so no finite `N` can cover every integer at or above it — return `-1`.
- If either denomination is 1, every non-negative integer is representable, so return `0`.
The original interview question is the concrete instance `p = 5`, `q = 21`, whose answer is `80`. This is the Frobenius / Chicken McNugget problem: for coprime `p` and `q` the largest non-representable integer is `p*q - p - q`, so `N = p*q - p - q + 1`.
Constraints
- 1 <= p, q <= 10000
- p and q are positive integers
- Return -1 when gcd(p, q) > 1 (no finite N exists)
- Return 0 when either p or q equals 1
Examples
Input: (5, 21)
Expected Output: 80
Explanation: The original interview instance. Coprime, so N = 5*21 - 5 - 21 + 1 = 80; 79 is the largest value that cannot be written as 5a + 21b.
Input: (3, 5)
Expected Output: 8
Explanation: Largest non-representable value is 3*5 - 3 - 5 = 7 (you cannot make 7 from 3s and 5s), so every integer >= 8 is representable.
Hints
- This is the Frobenius (Chicken McNugget) problem. The answer N is one more than the largest integer that CANNOT be written as p*a + q*b.
- If p and q share a common factor > 1, only multiples of that factor are representable, so no finite N exists — handle that case separately.
- For coprime p and q there is a closed form: the largest non-representable integer is p*q - p - q, so N = p*q - p - q + 1. You can also compute it with a DP reachability scan up to p*q.
- A simple verification: build a boolean array `reachable[0..p*q]`, mark reachable[x] true if reachable[x-p] or reachable[x-q] is true, then N is the index after the last false.