The Lazy Squares

An easy Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
easy
Seniority
L4

Problem

You're building a fixture of perfect squares whose decimal form contains a particular digit, and because those squares are scattered you can't tell in advance how far you'll have to look. Given a digit digit (0 through 9) and a positive integer count, return the first count such squares in increasing order, so squares_with_digit(2, 3) gives [25, 121, 225].

A sequence that never fully reveals itself.

Example

Input:

digit = 2, count = 3

Output:

[25,121,225]

Worked solution and explanation

What this is really about

Strip the digit-hunting costume and this is an unbounded search with a quota. The qualifying squares are sparse: for digit 2 the first one is 25 (the fifth square) and the third is 225 (the fifteenth square), so there is no range you can write down in advance. The reflex answer, a comprehension over range(1, count + 1), silently collects the wrong squares. For (2, 3) it only inspects 1, 4, 9 and hands back an empty list. The real skill is producing squares one at a time from an endless source and pulling until the quota is filled, then stopping. Materialize the source too early over a guessed range and you get too few results; run it open-ended with no stop and it never returns.

Break down the requirements

Step 1: Produce squares without a fixed ceiling

You do not know how many integers you must square before count of them qualify, so the producer has to be open-ended: square 1, 2, 3, and onward on demand rather than over a precomputed range. Any finite range is a guess, and sparse digits blow straight past it.

Step 2: Filter by digit membership

Test membership on the rendered number: str(digit) in str(square). This is a substring check on the decimal text, not arithmetic on the value, which is exactly why the qualifiers do not follow a tidy pattern you could bound ahead of time.

Step 3: Collect and stop at the quota

Append each qualifier and stop the instant you hold count of them. This is the boundary that makes the whole thing terminate: the source is infinite, the result is finite, and the quota is the only stop condition.

The trap in code

Fixed range (wrong)
[i * i for i in range(1, count + 1) if str(digit) in str(i * i)]. For (2, 3) this inspects only 1, 4, 9 and returns []. It assumes the count-th qualifier lives among the first count squares, which sparse digits violate.
Open-ended search (correct)
Generate 1, 4, 9, 16, 25, and onward with no ceiling, and stop once three of them contain the digit. Same predicate, but the search length is driven by the data instead of guessed.

The solution

An endless producer, stopped at the quota boundary
def squares_with_digit(digit, count):
    def squares():
        i = 1
        while True:
            yield i * i
            i += 1

    target = str(digit)
    found = []
    for square in squares():
        if target in str(square):
            found.append(square)
            if len(found) == count:
                break
    return found

Common follow-up questions