The Problem

We need to find invalid product IDs in a database. The IDs are numeric, but "invalid" ones are formed by repeating digit patterns. We are given ranges of IDs to check.

Summary

Part 1: Repeated Exactly Twice

An ID is invalid if it is composed of a pattern repeated exactly twice.

• 1212 (pattern 12 × 2) → Invalid

• 123123 (pattern 123 × 2) → Invalid

• 123124 → Valid

I initially thought this would be complex, maybe involving string searching or regex. But then I realized for Part 1, since it's exactly twice, the string must be split perfectly in half!
[first half] === [second half]

So I quickly implemented that to validate the idea. I'm passing the logic to transform each number in a range to `str` but here it is the logic:

const half = str.length / 2;
if (str.slice(0, half) === str.slice(half)) {
    // Found one!
}

Part 2: Repeated At Least Twice

The definition expands: an ID is invalid if it is a pattern repeated at least twice (2, 3, 4... times).

• 121212 (pattern 12 × 3) → Invalid

• 111111 (pattern 1 × 6) → Invalid

This required refactoring because the simple "split in half" trick doesn't work for 3 or 5 repetitions.

The Refactored Solution

To handle both parts elegantly, we generalize the check. Instead of just checking length / 2, we check all valid "sub-pattern" lengths.

why len % patternLen?

We only need to check pattern lengths that divide the total length evenly. If you have a 6-digit ID, you can't form it by repeating a 4-digit pattern (4 + 4 = 8).

• ID: 123456 (Length 6)

• Try Pattern Length 2: 6 % 2 === 0 ✅ (Could be 3 repeats)

• Try Pattern Length 4: 6 % 4 !== 0 ❌ (Cannot divide evenly)

This saves us from checking impossible pattern sizes.

why len / patternLen?

Once we know a pattern length fits, this tells us how many times it must repeat to fill the string.

• ID: 121212 (Length 6)

• Pattern: 12 (Length 2)

• Repetitions: 6 / 2 = 3

We then construct the expected string: '12'.repeat(3) and compare it to the original ID.

// General solution for both parts
function isInvalidId(num: number, maxRepetitions: number | undefined): boolean {
	const str = num.toString();
	const len = str.length;

	for (let patternLen = 1; patternLen <= len / 2; patternLen++) {
		if (len % patternLen !== 0) continue;

		const repetitions = len / patternLen;

		if (maxRepetitions !== undefined && repetitions !== maxRepetitions)
			continue;

		const pattern = str.slice(0, patternLen);
		if (pattern.repeat(repetitions) === str) {
			return true;
		}
	}

	return false;
}

Bonus: The Mathematical Approach 🧮

While the string-based solution was already working nicely, something was still bothering me... I was sure I could solve this in a purely mathematical way. And also, let's be honest, the performance of the first solution was just erhm...

1. The "Magic" Multipliers (Precomputation)

The key insight is realizing that repeating a number pattern is just arithmetic.

Take the number 121212. It looks like the pattern 12 repeated 3 times. Mathematically, we can decompose it like this:

That 10101 is a multiplier that depends only on:

1. The Pattern Length (2 digits)

2. The Repetition Count (3 times)

If we pre-calculate these multipliers for all possible lengths and repetitions, we can check if a number is valid just by doing ID % multiplier === 0.

We build a lookup table PATTERN_MULTIPLIERS[length][repetitions] at startup:

const POWERS_OF_10 = [1, 10, 100, ...]; // Precomputed powers

// Fill the table
for (let len = 1; len <= MAX_PATTERN_LENGTH; len++) {
    // How many times can a pattern of 'len' fit in our max digits?
    const maxReps = Math.floor(MAX_DIGITS / len);
    
    for (let reps = 2; reps <= maxReps; reps++) {
        let multiplier = 0;
        // Build the multiplier (e.g., 10101)
        for (let i = 0; i < reps; i++) {
            multiplier += POWERS_OF_10[len * i];
        }
        PATTERN_MULTIPLIERS[len][reps] = multiplier;
    }
}

2. Bitwise Optimization?? (>> 1)

You might spot this line in the check function:

const maxPatternLength = totalDigits >> 1;

What is >> 1? It's the Bitwise Right Shift operator. Shifting binary digits right by 1 position is mathematically equivalent to integer division by 2 (dropping the remainder).

• 6 (binary 110) >> 1 → 3 (binary 011)

• 5 (binary 101) >> 1 → 2 (binary 010)

Why divide by 2?
By definition, a "repeating pattern" must appear at least twice. Therefore, a single pattern instance cannot be longer than half the total digits.

• If ID has 6 digits, the pattern can be at most 3 digits long (123123).

• A 4-digit pattern (1234) would need 8 digits to repeat twice (12341234).

Using >> 1 is just a tiny bit faster 🏎️ and cooler 🤓 than Math.floor(totalDigits / 2).

3. The Check

Now checking an ID becomes purely numeric. We verify if the ID is divisible by any valid multiplier for its length.

function isRepeatingPattern(num: number, exactRepetitions: number | undefined): boolean {
    const totalDigits = countDigits(num);
    // Optimization: Pattern can't be longer than half the number
    const maxPatternLength = totalDigits >> 1;

    for (let len = 1; len <= maxPatternLength; len++) {
        // Optimization: Pattern length must divide total length evenly
        if (totalDigits % len !== 0) continue;

        const repetitions = totalDigits / len;
        if (exactRepetitions && repetitions !== exactRepetitions) continue;

        // Retrieve our precomputed magic number
        const multiplier = PATTERN_MULTIPLIERS[len][repetitions];

        // The Mathematical Check
        if (num % multiplier === 0) {
            const pattern = num / multiplier;

            // Edge case check:
            // If pattern is '12', we expect num to be '1212...'.
            // But 'num / multiplier' might technically result in '02' or '120' 
            // if we aren't careful (though with exact division here, it's safer).
            // We just ensure the resulting pattern actually fits in 'len' digits.
            const minVal = POWERS_OF_10[len - 1];
            const maxVal = POWERS_OF_10[len];

            if (pattern >= minVal && pattern < maxVal) {
                return true;
            }
        }
    }
    return false;
}

Performance Comparison

The mathematical approach is drastically faster because it avoids all string allocations and parsing, relying solely on CPU-friendly integer arithmetic.