InterviewDB Experience

Numbers That Belong: Find All Integers in a Range Satisfying a Digit Rule

phone
Sign in to bookmark

Interview Experience

Problem

Given integers lo, hi, and a digit rule,

return all integers in [lo, hi] (inclusive) that satisfy the rule. The rule: a number "belongs" if the sum of its digits is divisible by k.

python
def numbers_that_belong(lo: int, hi: int, k: int) -> list[int]:
    pass


**Input**:  lo=1, hi=30, k=5
Output: [5, 10, 14, 19, 23, 28]
# Digit sums: 5->5, 10->1... wait, 1+0=1, not 5.
# 5->5 (div by 5), 14->5 (div by 5), 19->10 (div by 5), 23->5, 28->10
# Let me recheck: 10->1, skip. 15->6, skip. 5->5 yes, 14->5 yes, 19->10 yes, 23->5 yes, 28->10 yes.

**Output**: [5, 14, 19, 23, 28]

**Input**:  lo=10, hi=20, k=3
Output: [12, 15, 18, 21]  # 21 > 20, so [12, 15, 18]
# 12->3, 15->6, 18->9 all div by 3.

Follow-ups

  1. For very large ranges (lo=1, hi=10^18), brute force is too slow. How does digit DP solve this?
  2. Describe the digit DP state: dp[position][current_digit_sum_mod_k][is_tight].
  3. How do you handle the count vs. enumeration distinction at large scale?
  4. Extend to a rule where the product of digits (ignoring zeros) must be divisible by k.

Full Details

Problem

Given integers lo, hi, and a digit rule,

return all integers in [lo, hi] (inclusive) that satisfy the rule. The rule: a number "belongs" if the sum of its digits is divisible by k.

python
def numbers_that_belong(lo: int, hi: int, k: int) -> list[int]:
    pass


**Input**:  lo=1, hi=30, k=5
Output: [5, 10, 14, 19, 23, 28]
# Digit sums: 5->5, 10->1... wait, 1+0=1, not 5.
# 5->5 (div by 5), 14->5 (div by 5), 19->10 (div by 5), 23->5, 28->10
# Let me recheck: 10->1, skip. 15->6, skip. 5->5 yes, 14->5 yes, 19->10 yes, 23->5 yes, 28->10 yes.

**Output**: [5, 14, 19, 23, 28]

**Input**:  lo=10, hi=20, k=3
Output: [12, 15, 18, 21]  # 21 > 20, so [12, 15, 18]
# 12->3, 15->6, 18->9 all div by 3.

Follow-ups

  1. For very large ranges (lo=1, hi=10^18), brute force is too slow. How does digit DP solve this?
  2. Describe the digit DP state: dp[position][current_digit_sum_mod_k][is_tight].
  3. How do you handle the count vs. enumeration distinction at large scale?
  4. Extend to a rule where the product of digits (ignoring zeros) must be divisible by k.
Free preview. Unlock all Squarespace questions →

About This Question

This is a candidate experience report from a squarespace interview during the phone round.

It covers the following topics: Coding, Phone, Dynamic Programming .

Topics

Coding Phone Dynamic Programming

More Squarespace Interview Questions

1p3a Squarespace Software Engineer Tech Screen Range Intersection Coding Question LeetCode #88 Merge Sorted Array InterviewDB Menu Filters: Return Dishes Matching Multiple Dietary Constraints LeetCode #1893 Check if All the Integers in a Range Are Covered InterviewDB Slideshow Frontend: Build an Auto-Advancing Image Carousel Component
← All Squarespace questions Squarespace Software Engineer Questions → All Arrays Questions →