How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Schonfeld.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Schonfeld during technical interviews.

Find smallest N for 5-and-21 sums | Schonfeld Coding Question

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.

Input: (2, 3)

Expected Output: 2

Explanation: Largest non-representable value is 2*3 - 2 - 3 = 1, so every integer >= 2 is representable.

Input: (4, 6)

Expected Output: -1

Explanation: gcd(4,6)=2, so only even numbers are ever representable; no finite N can cover all integers above it.

Input: (1, 7)

Expected Output: 0

Explanation: With a denomination of 1, every non-negative integer is representable, so N = 0.

Input: (7, 11)

Expected Output: 60

Explanation: Coprime, so N = 7*11 - 7 - 11 + 1 = 60; the largest non-representable value is 59.

Input: (5, 5)

Expected Output: -1

Explanation: gcd(5,5)=5, only multiples of 5 are representable, so no finite N exists — edge case with equal denominations sharing a factor.

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.

Quick Overview

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.