Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
A 'Decent Number' has only 3s and 5s, with the count of 5s divisible by 3 and the count of 3s divisible by 5. To make it the LARGEST n-digit decent number, you want as many leading 5s as possible (5 > 3, and all 5s sit before all 3s). So maximise the number of fives: scan the count of threes upward in multiples of 5 (0, 5, 10, …) and take the first one where `(n − threes)` is divisible by 3. Then print `'5' × fives + '3' × threes`. If no valid split exists, print `-1`. O(n) to build the string.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you translate 'largest number' into 'maximise the leading larger digit', and whether you map the two divisibility rules onto a clean linear search rather than brute-forcing strings.
Where candidates slip
Mixing up which count must be divisible by which (5s divisible by 3, 3s divisible by 5), or sorting digits the wrong way so 3s come before 5s.
How to stand out
Argue why all 5s must precede all 3s (5 > 3 at every position) and why maximising fives — not just satisfying the constraints — gives the largest value.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewLength nfives = n − threes fives % 3 == 0?NoYes (first hit)Explore the full treeCollapse the tree
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Brute Force — Enumerate Every Digit String
1Hint 1Explore hintHide hint
A decent number is a length-n string over {3, 5}. The most literal search is to generate every such string.
2Hint 2Explore hintHide hint
For each generated string, check the two rules: count of 5s divisible by 3, count of 3s divisible by 5.
3Hint 3Explore hintHide hint
Among all valid strings keep the largest. Correct, but there are 2ⁿ strings — useless beyond tiny n; use it only to anchor the constraints.
A · Core idea
Treat a decent number as any length-n string made only of 3 and 5. Enumerate all 2ⁿ of them, keep the ones satisfying both divisibility rules, and return the maximum.
Why it's correct. Every candidate is examined, so if a decent number exists the largest one is found; otherwise we return -1.
Why it's hopeless. 2ⁿ strings is astronomical — even n = 40 is a trillion. With n up to 100000 this never finishes. It exists only to make the rules concrete.
The structure it reveals. All valid strings share the same multiset shape: some number of 5s and some number of 3s summing to n. To be largest, the 5s must lead. So the only real choice is how many 5s — and the rules pin that to: fives a multiple of 3, threes a multiple of 5. That collapses 2ⁿ strings into a single linear scan over one count.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 3555
fives=3 (÷3 ✓), threes=0 (÷5 ✓) → valid
best = 555555C · Code with teaching comments
Reference implementation previewpublic String decentNumberBrute(int n) { String best = "-1"; for (int mask = (1 << n) - 1; mask >= 0; mask--) { StringBuilder sb = new StringBuilder(); int fives = 0, threes = 0;Explore the full codeHide the full code
D · Why it works and complexityO(2ⁿ · n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
The 2ⁿ search hides a one-dimensional choice: only the COUNT of 5s matters (they always lead), and the two rules turn that into a tiny linear scan.
ComplexityO(2ⁿ · n) time, O(n) space — There are 2ⁿ strings of length n over two symbols; validating and comparing each is O(n). The exponential dominates.
E · Edge cases and pitfalls32ⁿ explosion — only runs for n ≤ ~20; never a submission.Explore edge casesHide edge cases
Pitfalls
- 2ⁿ explosion — only runs for n ≤ ~20; never a submission.
- Comparing as integers overflows; compare as fixed-length strings.
- Swapping the two divisibility rules.
Approach 2 of 2 · Optimal
Greedy — Maximise Fives via a Linear Scan (Optimal)
1Hint 1Explore hintHide hint
All 5s come before all 3s (5 > 3). So the number is fully determined by how many 5s it has. To be largest, maximise the 5 count.
2Hint 2Explore hintHide hint
The 3-count must be a multiple of 5 and the 5-count a multiple of 3. Walk the 3-count over 0, 5, 10, … and stop at the first value where the remaining digits (the 5-count) is a multiple of 3.
3Hint 3Explore hintHide hint
That first hit minimises threes, hence maximises fives — the largest decent number. Build '5'×fives + '3'×threes. If the scan finds nothing, return -1.
A · Core idea
Because 5 > 3, the largest decent number puts every 5 ahead of every 3, so the only degree of freedom is how many 5s appear. We want that count as large as possible, which is the same as making the count of 3s as small as possible.
Why scan the 3-count in multiples of 5. The constraint says the number of 3s must be divisible by 5, so the only candidate 3-counts are 0, 5, 10, …. For each, the remaining digits become 5s: fives = n − threes. We accept the first candidate where fives is divisible by 3 (the second rule). Scanning threes upward from 0 means we try the smallest legal 3-count first — equivalently the largest 5-count first — so the first hit is optimal.
Why front-loading the larger digit is optimal — the exchange argument. Take any valid decent number that is NOT all-5s-then-all-3s; then somewhere a 3 sits immediately before a 5. Swap that adjacent 35 into 53: the multiset of digits (and hence both counts and both divisibility properties) is unchanged, but the value strictly increases because a larger digit moved to a more significant position. Repeating these swaps sorts all 5s before all 3s without ever breaking the constraints, and strictly increases the value each time. So the maximum must have all 5s first — and among those, the one with the most 5s is largest.
Why −1 when the scan fails. If no 3-count that is a multiple of 5 leaves a 5-count divisible by 3, then n simply cannot be partitioned to satisfy both rules and no decent number of length n exists.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 11Array state
threes=0
fives=11, 11%3=2 → reject
55555533333C · Code with teaching comments
D · Why it works and complexityO(n) timeO(n) spaceOpen the invariant and proofExplore the proofHide the proof
'Largest fixed-length number from digits {a > b}' always means: all a first, as many as the constraints permit. The two divisibility rules then reduce a string search to a one-dimensional scan over a single count — an exchange-argument greedy with a number-theoretic twist.
ComplexityO(n) time, O(n) space — The scan over multiples of 5 runs at most n/5 + 1 iterations (O(n) worst case), and assembling the result string is O(n). No structure beyond a single pass.
E · Edge cases and pitfalls6n = 1 — threes=0 → fives=1 (1%3≠0); no further multiple of 5 ≤ 1 → return -1.Explore edge casesHide edge cases
Edge cases handled
n = 1threes=0 → fives=1 (1%3≠0); no further multiple of 5 ≤ 1 → return -1.n = 15threes=0 → fives=15 (÷3 ✓) → all fifteen 5s, '555555555555555'.n = 8threes=0 → fives=8 (8%3≠0); threes=5 → fives=3 (÷3 ✓) → '55533333'.
Pitfalls
- Scanning the fives count and forgetting to keep threes a multiple of 5 — yields invalid numbers.
- Building the number as an int — overflows for large n; always use a string.
- Returning the first VALID number found while scanning threes downward — that minimises fives and gives a smaller number.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic String decentNumber(int n) { for (int threes = 0; threes <= n; threes += 5) { int fives = n - threes; if (fives % 3 == 0) { StringBuilder sb = new StringBuilder();Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Crossing the divisibility rules
It is easy to write '5s divisible by 5'. The rule is 5s ÷ 3 and 3s ÷ 5. Swapping them produces wrong splits.
Explore the code comparisonHide the code comparison
Crossing the divisibility rules
It is easy to write '5s divisible by 5'. The rule is 5s ÷ 3 and 3s ÷ 5. Swapping them produces wrong splits.
Don't write this
for fives in range(0, n + 1, 5): # wrong: fives stepped by 5
threes = n - fives
if threes % 3 == 0:
return "5" * fives + "3" * threesWrite this instead
for threes in range(0, n + 1, 5):
fives = n - threes
if fives % 3 == 0:
return "5" * fives + "3" * threes2Using an integer instead of a string
For n up to 100000 the number has up to 100000 digits; long/BigInteger arithmetic is unnecessary and int overflows immediately.
Explore the code comparisonHide the code comparison
Using an integer instead of a string
For n up to 100000 the number has up to 100000 digits; long/BigInteger arithmetic is unnecessary and int overflows immediately.
Don't write this
long num = 0;
for (int i = 0; i < fives; i++) num = num * 10 + 5; // overflowWrite this instead
StringBuilder sb = new StringBuilder();
for (int i = 0; i < fives; i++) sb.append('5');3Minimising fives instead of maximising
Scanning threes from high to low (or fives from low to high) returns a valid but smaller number. Start threes at 0 to get the most fives.
Explore the code comparisonHide the code comparison
Minimising fives instead of maximising
Scanning threes from high to low (or fives from low to high) returns a valid but smaller number. Start threes at 0 to get the most fives.
Don't write this
for threes in range(n - (n % 5), -1, -5): # threes large first → fewer fives
fives = n - threes
if fives % 3 == 0:
return "5" * fives + "3" * threesWrite this instead
for threes in range(0, n + 1, 5):
fives = n - threes
if fives % 3 == 0:
return "5" * fives + "3" * threesRevise
Carry the pattern into the interview
Pattern to remember
Greedy constructive: maximise the high digit (5) subject to two divisibility constraints
Code pattern to memorize
for threes in 0, 5, 10, ... up to n: # multiples of 5
fives = n - threes
if fives >= 0 and fives % 3 == 0:
return '5' * fives + '3' * threes
return '-1'Rules to remember
- 1A decent number uses only the digits 3 and 5 — nothing else.
- 2Count of 5s must be divisible by 3; count of 3s must be divisible by 5.
- 3Largest number of fixed length = most 5s up front, then 3s. So maximise fives (equivalently minimise threes).
- 4Iterate threes as multiples of 5 (the 3-count constraint), and accept the first where the remaining digits (the fives) are divisible by 3.
- 5If no split satisfies both constraints, the answer is
-1— e.g. n = 1, 2, 4, 7.
Use this pattern when
- Constructing the lexicographically/numerically largest string from a fixed digit set
- Two coupled divisibility constraints partition a known total
- You greedily front-load the larger symbol then fill with the smaller
- The search space is a single linear scan over one count
Choose another pattern when
- Digits can be arbitrary (not a fixed two-symbol set) → different construction
- No length constraint / variable length → optimisation changes
- Constraints are not pure divisibility (e.g. sum-of-digits target) → DP or math, not a linear scan
- You need ALL decent numbers, not the largest → enumeration
Interview takeaway
To build the largest fixed-length number from two digits, put the bigger digit first and as often as possible. Here that means maximising 5s, which reduces to a one-line linear scan over the count of 3s (kept a multiple of 5) checking the 5-count is a multiple of 3.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternConstructive greedy: to build the largest fixed-length string from digits {5 > 3}, front-load 5s and let two divisibility constraints collapse the search to a single linear scan over one count. The adjacent-swap exchange argument justifies sorting the larger digit first.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Largest Number (digit reorder)Coming soonArrange given numbers to form the largest concatenation — comparator-based greedy ordering.
- Largest PermutationMaximise a sequence under a swap budget — greedy placing the largest value first.
- Lily's HomeworkComing soonConstructive greedy producing a target arrangement with minimal operations.
- Greedy FloristAnother sort/assign greedy proven by an exchange argument.