Loading…

easyStrings0Sometimes asked

Colorful Number

Q: How do you solve Colorful Number using the Brute Force — Recompute Each Run's Product approach?

When to use it: Mention to show the enumeration, then note that re-multiplying each run from scratch adds an avoidable O(d) factor. Enumerate every contiguous run with two indices `i ≤ j`, and for each run multiply `digits[i] · digits[i+1] · … · digits[j]` in a dedicated inner loop. Push each product into a set; if a product is already present, the number is not colorful. **Why it's the natural first attempt.** The definition is 'product of every contiguous run is distinct', so the literal translation fixes a run and computes its product directly. **Why it's wasteful.** Computing the product of `digits[i..j]` from scratch repeats the multiplications already done for `digits[i..j-1]`. That third loop is pure redundancy — the product of the longer run is just the shorter run's product times one more digit. **The bridge to optimal.** Carry the running product across the inner loop instead of recomputing it. That single change drops the cube to a square. Time complexity: O(d³). Space complexity: O(d²).

Q: How do you solve Colorful Number using the Incremental Product with a Hash Set (Optimal) approach?

When to use it: The answer they want — frame it as 'extend the running product by one digit and dedupe in a set'. Fix a start index `i`, initialise `product = 1`, then sweep `j` from `i` to the end, multiplying `product` by `digits[j]` exactly once per step. After each multiply, the running `product` is precisely the product of run `digits[i..j]`. Check it against the set; if present, return `"NO"`; otherwise add it. **Why the running product is the key.** Extending the run by one digit is one multiplication: `product(i..j) = product(i..j-1) · digit[j]`. Carrying `product` across the inner loop removes the third loop of the brute force, turning O(d³) into O(d²). **Why a set with early exit.** We only need to know whether any product repeats. A hash set answers 'seen this product?' in O(1), and the moment a duplicate appears the answer is settled — no need to enumerate the rest. **Why single digits matter.** When `j == i` the run is one digit, so each digit's own value enters the set. That's why `11` fails instantly: the second `1` reproduces product `1`, as does the run `1·1`. **Overflow note.** Products of up to ~10 digits (each ≤ 9) stay well within a 64-bit `long`, but say it aloud — for very long digit strings you'd reach for big integers (Python handles this natively). Time complexity: O(d²). Space complexity: O(d²).

Arrays & Hashing · 79 of 83 · 7 min

Consider a number as a sequence of its decimal digits. A number is colorful if the product of the digits of every contiguous subsequence (substring) of its digit-sequence is distinct.

For example, 3245 has digit-runs 3, 2, 4, 5, 32, 24, 45, 324, 245, 3245 with products 3, 2, 4, 5, 6, 8, 20, 24, 40, 120 — all different — so it is colorful.

Given a non-negative integer n, return "YES" if it is colorful, otherwise "NO".

In plain English

Spell the number out as digits. For each contiguous run of digits multiply them together; that run's product is one value to track. 'Colorful' means no two runs share a product. Because products are over contiguous runs, there are exactly d(d+1)/2 of them for d digits — and we just need them all to be distinct.

Examples

Example 1

Input: n = 3245
Output: YES
Note: Products of all runs: 3, 2, 4, 5, 6, 8, 20, 24, 40, 120 — ten distinct values, so colorful.

Example 2

Input: n = 326
Output: NO
Note: Runs: 3, 2, 6, 32→6, 26→12, 326→36. The single digit 6 and the run 3·2 = 6 collide, so not colorful.

Example 3

Input: n = 23
Output: YES
Note: Products: 2, 3, 2·3 = 6 — all distinct.

Example 4

Input: n = 11
Output: NO
Note: Products: 1, 1 (two single digits), 1·1 = 1 — the value 1 repeats immediately.

Constraints

0 ≤ n ≤ 2³¹ − 1 (fits in ~10 decimal digits)
Treat n as the string of its decimal digits
Products are of contiguous digit runs only
Return the literal strings "YES" or "NO"

Clarifying questions4First question: Contiguous runs or arbitrary subsets of digits?Explore questions

Q1.Contiguous runs or arbitrary subsets of digits?
Contiguous only — substrings of the digit string. That keeps the count at O(d²) rather than 2^d.
Q2.Do single digits count as runs?
Yes. Each individual digit is a length-1 run, so two equal digits anywhere immediately collide (same product).
Q3.Should I work with the integer or its digits?
Its digits. Convert n to a string (or extract digits) first; the products are over those digit characters.
Q4.What about digits 0 and 1?
They're allowed and are common collision sources — multiple 1s share product 1, and a 0 makes any run containing it product 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Treat the number as its string of digits. For every contiguous run of digits, compute the product of that run. The number is colorful if and only if all of these products are distinct. Store each product in a hash set; the moment a product repeats, return "NO". With d digits there are O(d²) runs, and you build each product incrementally, so it's O(d²) time and O(d²) space. Since d is small (a number fits in ~19 digits), this is effectively constant.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you enumerate contiguous sub-ranges with an incremental product (not a fresh O(d) multiply each time) and use a set for O(1) uniqueness checking with early exit.

Where candidates slip

Recomputing each sub-product from scratch (an extra O(d) factor), forgetting single-digit products, or treating the number arithmetically instead of as a digit string.

How to stand out

Note that extending digits[i..j] to digits[i..j+1] is one multiply, so the nested loops are O(d²) not O(d³), and that a hash set turns uniqueness into O(1) membership with an immediate exit on collision.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recompute Each Run's Product	`O(d³)`	`O(d²)`	Mention to show the enumeration, then note that re-multiplying each run from scratch adds an avoidable O(d) factor.	Read
2	Incremental Product with a Hash Set (Optimal)Optimal	`O(d²)`	`O(d²)`	The answer they want — frame it as 'extend the running product by one digit and dedupe in a set'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewDigits of nProduct already in set?YesNoExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Recompute Each Run's Product

TimeO(d³)SpaceO(d²)

Mention to show the enumeration, then note that re-multiplying each run from scratch adds an avoidable O(d) factor.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

There are O(d²) contiguous runs. For each, you need its digit product — how would you compute it most directly?

2Hint 2Explore hint

Two outer indices i ≤ j fix a run; multiply digits[i] through digits[j] in a fresh inner loop to get the product.

3Hint 3Explore hint

Collect every product. If you ever produce a value already collected, it isn't colorful. Re-multiplying each run is an extra O(d), making this O(d³).

A · Core idea

Enumerate every contiguous run with two indices i ≤ j, and for each run multiply digits[i] · digits[i+1] · … · digits[j] in a dedicated inner loop. Push each product into a set; if a product is already present, the number is not colorful.

Why it's the natural first attempt. The definition is 'product of every contiguous run is distinct', so the literal translation fixes a run and computes its product directly.

Why it's wasteful. Computing the product of digits[i..j] from scratch repeats the multiplications already done for digits[i..j-1]. That third loop is pure redundancy — the product of the longer run is just the shorter run's product times one more digit.

The bridge to optimal. Carry the running product across the inner loop instead of recomputing it. That single change drops the cube to a square.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 326

Array state

i=0

3, 32→6, 326→36

i ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final resultNO

C · Code with teaching comments

Reference implementation previewpublic String colorful(int n) { String digits = Integer.toString(n); Set<Long> seen = new HashSet<>(); for (int i = 0; i < digits.length(); i++) { for (int j = i; j < digits.length(); j++) {Explore the full code

solution.javaJava

Brute Force — Recompute Each Run's Product — reference

3 teaching notes

1
public String colorful(int n) {
2
    String digits = Integer.toString(n);
3
    Set<Long> seen = new HashSet<>();
4
    for (int i = 0; i < digits.length(); i++) {
5
        for (int j = i; j < digits.length(); j++) {
6
            long product = 1;
7
            // Innermost loop re-multiplies the whole run — the redundant O(d) factor.
8
            for (int k = i; k <= j; k++) {
9
                // Convert the digit char to its int value before multiplying.
10
                product *= digits.charAt(k) - '0';
11
            }
12
            // Set.add returns false if the product was already present → collision.
13
            if (!seen.add(product)) {
14
                return "NO";
15
            }
16
        }
17
    }
18
    return "YES";
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(d³) timeO(d²) spaceOpen the invariant and proofExplore the proof

The product of digits[i..j] equals the product of digits[i..j-1] times digits[j]. Recomputing from i every time throws that away — keeping a running product is the whole optimisation.

ComplexityO(d³) time, O(d²) space — O(d²) runs, and recomputing each product walks up to O(d) digits → O(d³) time. The set of products holds up to d(d+1)/2 values → O(d²) space.

E · Edge cases and pitfalls3Recomputing each run's product from scratch — an extra O(d) factor.Explore edge cases

Pitfalls

Recomputing each run's product from scratch — an extra O(d) factor.
Forgetting single-digit runs, which catch repeated digits immediately.
Using int that overflows for long digit runs — products grow fast; prefer long / Python big ints.

03.2

Approach 2 of 2 · Optimal

Incremental Product with a Hash Set (Optimal)

TimeO(d²)SpaceO(d²)

The answer they want — frame it as 'extend the running product by one digit and dedupe in a set'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Don't recompute digits[i..j] each time. As j advances, how does the product change?

2Hint 2Explore hint

Fix the start i, set product = 1, and for each j from i onward multiply product by digits[j] once.

3Hint 3Explore hint

Check the running product against the set before inserting; the first repeat means not colorful, so return immediately.

A · Core idea

Fix a start index i, initialise product = 1, then sweep j from i to the end, multiplying product by digits[j] exactly once per step. After each multiply, the running product is precisely the product of run digits[i..j]. Check it against the set; if present, return "NO"; otherwise add it.

Why the running product is the key. Extending the run by one digit is one multiplication: product(i..j) = product(i..j-1) · digit[j]. Carrying product across the inner loop removes the third loop of the brute force, turning O(d³) into O(d²).

Why a set with early exit. We only need to know whether any product repeats. A hash set answers 'seen this product?' in O(1), and the moment a duplicate appears the answer is settled — no need to enumerate the rest.

Why single digits matter. When j == i the run is one digit, so each digit's own value enters the set. That's why 11 fails instantly: the second 1 reproduces product 1, as does the run 1·1.

Overflow note. Products of up to ~10 digits (each ≤ 9) stay well within a 64-bit long, but say it aloud — for very long digit strings you'd reach for big integers (Python handles this natively).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3245

Array state

i=0, j=0

product = 3

i ↓j ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

solution.javaJava

Incremental Product with a Hash Set (Optimal) — optimal

4 teaching notes

1
public String colorful(int n) {
2
    String digits = Integer.toString(n);
3
    Set<Long> seen = new HashSet<>();
4
    for (int i = 0; i < digits.length(); i++) {
5
        // Reset the running product for each new start index i; long avoids overflow.
6
        long product = 1;
7
        for (int j = i; j < digits.length(); j++) {
8
            // Extend the run by one digit — a single multiply, not a recompute.
9
            product *= digits.charAt(j) - '0';
10
            // add returns false on a duplicate → the number isn't colorful.
11
            if (!seen.add(product)) {
12
                // First collision settles the answer; stop early.
13
                return "NO";
14
            }
15
        }
16
    }
17
    return "YES";
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(d²) timeO(d²) spaceOpen the invariant and proofExplore the proof

This is the canonical 'all O(n²) contiguous aggregates distinct?' shape: enumerate ranges, carry the aggregate incrementally, and dedupe with a set. The same skeleton answers distinct subarray sums or XORs — only the combine operation changes.

ComplexityO(d²) time, O(d²) space — Two loops over the d digits with O(1) work per (i, j) pair = O(d²) time. The set stores up to d(d+1)/2 products → O(d²) space. Since d ≤ ~10 for a 32-bit integer, this is effectively constant in practice.

E · Edge cases and pitfalls7n = 5 — Single digit → one product {5} → trivially distinct → "YES".Explore edge cases

Edge cases handled

n = 5Single digit → one product {5} → trivially distinct → "YES".
n = 11Products 1, 1, 1 → the value 1 repeats on the second single digit → "NO".
n = 263Products 2, 6, 3, 12, 18, 36 — all distinct → "YES" (contrast with 326).
n = 10Products 1, 0, 0 → 0 repeats (single '0' and run '1·0') → "NO".

Pitfalls

Resetting product inside the wrong loop — it must reset for each new start index i.
Using a 32-bit int that overflows on long digit runs — use long or big integers.
Forgetting that 0 and repeated 1s are frequent, instant collision sources.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic String colorful(int n) { String digits = Integer.toString(n); Set<Long> seen = new HashSet<>(); for (int i = 0; i < digits.length(); i++) { long product = 1;Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Recomputing the product every run

The product of digits[i..j] is just digits[i..j-1] times one more digit. A third loop to re-multiply is pure redundancy and makes it O(d³).

Explore the code comparison

Don't write this

for j in range(i, len(digits)):
    product = 1
    for k in range(i, j + 1):
        product *= int(digits[k])

Write this instead

product = 1
for j in range(i, len(digits)):
    product *= int(digits[j])

Resetting the running product in the wrong place

product must start at 1 for each new start index i. Resetting it inside the j-loop discards the running value; never resetting carries products across unrelated runs.

Explore the code comparison

Don't write this

for (int i = 0; i < digits.length(); i++) {
    for (int j = i; j < digits.length(); j++) {
        long product = 1;
        product *= digits.charAt(j) - '0';
    }
}

Write this instead

for (int i = 0; i < digits.length(); i++) {
    long product = 1;
    for (int j = i; j < digits.length(); j++) {
        product *= digits.charAt(j) - '0';
    }
}

Integer overflow on long digit runs

Products of many digits can exceed 32-bit range. Use a 64-bit long (Java) or Python's arbitrary-precision ints to keep comparisons correct.

Explore the code comparison

Don't write this

Set<Integer> seen = new HashSet<>();
int product = 1;

Write this instead

Set<Long> seen = new HashSet<>();
long product = 1;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

All contiguous-subarray products must be unique (hash set)

Code pattern to memorize

digits = str(n)
seen = set()
for i in range(len(digits)):
    p = 1
    for j in range(i, len(digits)):
        p *= int(digits[j])
        if p in seen: return "NO"
        seen.add(p)
return "YES"

Rules to remember

1Work on the digits, not the integer value — split the number into its decimal digits first.
2Consider every CONTIGUOUS run (substring of digits), not arbitrary subsets.
3Build the product of digits[i..j] incrementally: extend the previous product by one more digit — never recompute from scratch.
4Use a hash set of products; a single repeat means not colorful.
5Single digits count too — 1, 1 (two 1s anywhere) collide instantly, and so do 1·x = x clashes.

Use this pattern when

Need every contiguous-subarray aggregate (product/sum/xor) to be unique
Uniqueness check over O(n²) sub-ranges with O(1) membership
Small input where O(n²) is comfortably fast
You can extend an aggregate by one element instead of recomputing

Choose another pattern when

Aggregates over NON-contiguous subsets → 2ⁿ combinations, different problem
Only need the COUNT of distinct products, not a yes/no → still a set, but no early exit
Sums instead of products with huge ranges → watch overflow, prefer running sums
Need the actual colliding ranges → store product → range, not just the product

Interview takeaway

Generate every contiguous run, multiply incrementally, and drop each product into a set. The whole problem is 'are all O(d²) sub-products distinct?', answered with O(1) membership tests and an early exit on the first collision.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternEnumerate-all-contiguous-ranges with an incremental aggregate and a dedupe set. Whenever every sub-range's sum/product/xor must be unique (or counted), fix the start, carry the aggregate as you extend the end, and use a hash set for O(1) membership. The incremental carry is what keeps it O(n²) instead of O(n³).

Practice queueDirect variations and pattern siblings

Direct follow-ups

Distinct Subarray Sums
Coming soon
Same range-enumeration skeleton, but carry a running SUM and dedupe in a set.
Subarrays with Equal Product (count variant)
Coming soon
Instead of yes/no, count how many runs share a product — keep counts in the map.
Subarray Product Less Than K
Coming soon
Running product over a sliding window — related product-of-contiguous idea.
Maximum Product Subarray
Coming soon
Carry running products (track min too for negatives) across the array.

Same pattern

←

Triple Sum

Continue · Next problem

Reverse Shuffle Merge

easyStrings0Sometimes asked

Colorful Number

Arrays & Hashing · 79 of 83 · 7 min

Consider a number as a sequence of its decimal digits. A number is colorful if the product of the digits of every contiguous subsequence (substring) of its digit-sequence is distinct.

For example, 3245 has digit-runs 3, 2, 4, 5, 32, 24, 45, 324, 245, 3245 with products 3, 2, 4, 5, 6, 8, 20, 24, 40, 120 — all different — so it is colorful.

Given a non-negative integer n, return "YES" if it is colorful, otherwise "NO".

In plain English

Examples

Example 1

Input: n = 3245
Output: YES
Note: Products of all runs: 3, 2, 4, 5, 6, 8, 20, 24, 40, 120 — ten distinct values, so colorful.

Example 2

Input: n = 326
Output: NO
Note: Runs: 3, 2, 6, 32→6, 26→12, 326→36. The single digit 6 and the run 3·2 = 6 collide, so not colorful.

Example 3

Input: n = 23
Output: YES
Note: Products: 2, 3, 2·3 = 6 — all distinct.

Example 4

Input: n = 11
Output: NO
Note: Products: 1, 1 (two single digits), 1·1 = 1 — the value 1 repeats immediately.

Constraints

0 ≤ n ≤ 2³¹ − 1 (fits in ~10 decimal digits)
Treat n as the string of its decimal digits
Products are of contiguous digit runs only
Return the literal strings "YES" or "NO"

Clarifying questions4First question: Contiguous runs or arbitrary subsets of digits?Explore questions

Q1.Contiguous runs or arbitrary subsets of digits?
Contiguous only — substrings of the digit string. That keeps the count at O(d²) rather than 2^d.
Q2.Do single digits count as runs?
Yes. Each individual digit is a length-1 run, so two equal digits anywhere immediately collide (same product).
Q3.Should I work with the integer or its digits?
Its digits. Convert n to a string (or extract digits) first; the products are over those digit characters.
Q4.What about digits 0 and 1?
They're allowed and are common collision sources — multiple 1s share product 1, and a 0 makes any run containing it product 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you enumerate contiguous sub-ranges with an incremental product (not a fresh O(d) multiply each time) and use a set for O(1) uniqueness checking with early exit.

Where candidates slip

Recomputing each sub-product from scratch (an extra O(d) factor), forgetting single-digit products, or treating the number arithmetically instead of as a digit string.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recompute Each Run's Product	`O(d³)`	`O(d²)`	Mention to show the enumeration, then note that re-multiplying each run from scratch adds an avoidable O(d) factor.	Read
2	Incremental Product with a Hash Set (Optimal)Optimal	`O(d²)`	`O(d²)`	The answer they want — frame it as 'extend the running product by one digit and dedupe in a set'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Brute Force — Recompute Each Run's Product

TimeO(d³)SpaceO(d²)

Mention to show the enumeration, then note that re-multiplying each run from scratch adds an avoidable O(d) factor.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

There are O(d²) contiguous runs. For each, you need its digit product — how would you compute it most directly?

2Hint 2Explore hint

Two outer indices i ≤ j fix a run; multiply digits[i] through digits[j] in a fresh inner loop to get the product.

3Hint 3Explore hint

Collect every product. If you ever produce a value already collected, it isn't colorful. Re-multiplying each run is an extra O(d), making this O(d³).

A · Core idea

Why it's the natural first attempt. The definition is 'product of every contiguous run is distinct', so the literal translation fixes a run and computes its product directly.

The bridge to optimal. Carry the running product across the inner loop instead of recomputing it. That single change drops the cube to a square.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 326

Array state

i=0

3, 32→6, 326→36

i ↓

[0]

[1]

[2]

Current pointerResolved stateNot processed

Final resultNO

C · Code with teaching comments

solution.javaJava

Brute Force — Recompute Each Run's Product — reference

3 teaching notes

1
public String colorful(int n) {
2
    String digits = Integer.toString(n);
3
    Set<Long> seen = new HashSet<>();
4
    for (int i = 0; i < digits.length(); i++) {
5
        for (int j = i; j < digits.length(); j++) {
6
            long product = 1;
7
            // Innermost loop re-multiplies the whole run — the redundant O(d) factor.
8
            for (int k = i; k <= j; k++) {
9
                // Convert the digit char to its int value before multiplying.
10
                product *= digits.charAt(k) - '0';
11
            }
12
            // Set.add returns false if the product was already present → collision.
13
            if (!seen.add(product)) {
14
                return "NO";
15
            }
16
        }
17
    }
18
    return "YES";
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(d³) timeO(d²) spaceOpen the invariant and proofExplore the proof

The product of digits[i..j] equals the product of digits[i..j-1] times digits[j]. Recomputing from i every time throws that away — keeping a running product is the whole optimisation.

ComplexityO(d³) time, O(d²) space — O(d²) runs, and recomputing each product walks up to O(d) digits → O(d³) time. The set of products holds up to d(d+1)/2 values → O(d²) space.

E · Edge cases and pitfalls3Recomputing each run's product from scratch — an extra O(d) factor.Explore edge cases

Pitfalls

Recomputing each run's product from scratch — an extra O(d) factor.
Forgetting single-digit runs, which catch repeated digits immediately.
Using int that overflows for long digit runs — products grow fast; prefer long / Python big ints.

03.2

Approach 2 of 2 · Optimal

Incremental Product with a Hash Set (Optimal)

TimeO(d²)SpaceO(d²)

The answer they want — frame it as 'extend the running product by one digit and dedupe in a set'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Don't recompute digits[i..j] each time. As j advances, how does the product change?

2Hint 2Explore hint

Fix the start i, set product = 1, and for each j from i onward multiply product by digits[j] once.

3Hint 3Explore hint

Check the running product against the set before inserting; the first repeat means not colorful, so return immediately.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 3245

Array state

i=0, j=0

product = 3

i ↓j ↓

[0]

[1]

[2]

[3]

Current pointerResolved stateNot processed

Final resultYES

C · Code with teaching comments

solution.javaJava

Incremental Product with a Hash Set (Optimal) — optimal

4 teaching notes

1
public String colorful(int n) {
2
    String digits = Integer.toString(n);
3
    Set<Long> seen = new HashSet<>();
4
    for (int i = 0; i < digits.length(); i++) {
5
        // Reset the running product for each new start index i; long avoids overflow.
6
        long product = 1;
7
        for (int j = i; j < digits.length(); j++) {
8
            // Extend the run by one digit — a single multiply, not a recompute.
9
            product *= digits.charAt(j) - '0';
10
            // add returns false on a duplicate → the number isn't colorful.
11
            if (!seen.add(product)) {
12
                // First collision settles the answer; stop early.
13
                return "NO";
14
            }
15
        }
16
    }
17
    return "YES";
18
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.18 lines

D · Why it works and complexityO(d²) timeO(d²) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls7n = 5 — Single digit → one product {5} → trivially distinct → "YES".Explore edge cases

Edge cases handled

n = 5Single digit → one product {5} → trivially distinct → "YES".
n = 11Products 1, 1, 1 → the value 1 repeats on the second single digit → "NO".
n = 263Products 2, 6, 3, 12, 18, 36 — all distinct → "YES" (contrast with 326).
n = 10Products 1, 0, 0 → 0 repeats (single '0' and run '1·0') → "NO".

Pitfalls

Resetting product inside the wrong loop — it must reset for each new start index i.
Using a 32-bit int that overflows on long digit runs — use long or big integers.
Forgetting that 0 and repeated 1s are frequent, instant collision sources.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Recomputing the product every run

The product of digits[i..j] is just digits[i..j-1] times one more digit. A third loop to re-multiply is pure redundancy and makes it O(d³).

Explore the code comparison

Don't write this

for j in range(i, len(digits)):
    product = 1
    for k in range(i, j + 1):
        product *= int(digits[k])

Write this instead

product = 1
for j in range(i, len(digits)):
    product *= int(digits[j])

Resetting the running product in the wrong place

product must start at 1 for each new start index i. Resetting it inside the j-loop discards the running value; never resetting carries products across unrelated runs.

Explore the code comparison

Don't write this

for (int i = 0; i < digits.length(); i++) {
    for (int j = i; j < digits.length(); j++) {
        long product = 1;
        product *= digits.charAt(j) - '0';
    }
}

Write this instead

for (int i = 0; i < digits.length(); i++) {
    long product = 1;
    for (int j = i; j < digits.length(); j++) {
        product *= digits.charAt(j) - '0';
    }
}

Integer overflow on long digit runs

Products of many digits can exceed 32-bit range. Use a 64-bit long (Java) or Python's arbitrary-precision ints to keep comparisons correct.

Explore the code comparison

Don't write this

Set<Integer> seen = new HashSet<>();
int product = 1;

Write this instead

Set<Long> seen = new HashSet<>();
long product = 1;

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

All contiguous-subarray products must be unique (hash set)

Code pattern to memorize

digits = str(n)
seen = set()
for i in range(len(digits)):
    p = 1
    for j in range(i, len(digits)):
        p *= int(digits[j])
        if p in seen: return "NO"
        seen.add(p)
return "YES"

Rules to remember

1Work on the digits, not the integer value — split the number into its decimal digits first.
2Consider every CONTIGUOUS run (substring of digits), not arbitrary subsets.
3Build the product of digits[i..j] incrementally: extend the previous product by one more digit — never recompute from scratch.
4Use a hash set of products; a single repeat means not colorful.
5Single digits count too — 1, 1 (two 1s anywhere) collide instantly, and so do 1·x = x clashes.

Use this pattern when

Need every contiguous-subarray aggregate (product/sum/xor) to be unique
Uniqueness check over O(n²) sub-ranges with O(1) membership
Small input where O(n²) is comfortably fast
You can extend an aggregate by one element instead of recomputing

Choose another pattern when

Aggregates over NON-contiguous subsets → 2ⁿ combinations, different problem
Only need the COUNT of distinct products, not a yes/no → still a set, but no early exit
Sums instead of products with huge ranges → watch overflow, prefer running sums
Need the actual colliding ranges → store product → range, not just the product

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Distinct Subarray Sums
Coming soon
Same range-enumeration skeleton, but carry a running SUM and dedupe in a set.
Subarrays with Equal Product (count variant)
Coming soon
Instead of yes/no, count how many runs share a product — keep counts in the map.
Subarray Product Less Than K
Coming soon
Running product over a sliding window — related product-of-contiguous idea.
Maximum Product Subarray
Coming soon
Carry running products (track min too for negatives) across the array.

Same pattern

←

Triple Sum

Continue · Next problem

Reverse Shuffle Merge