Quick Overview

A coding interview question on locating a digit position within concatenated integers to find a missing number. Covers the string-parsing and combinatorial approach with a complete worked solution.

Find missing number from concatenated digits

Company: Chime

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

Given an integer n (1 ≤ n ≤ 99) and a digit string s formed by concatenating the decimal representations of the integers 1..n except for one missing number k, write a function to return k. Part A: s preserves the natural order (e.g., n=5, s="1234" → k= 5). Part B: s’s characters are arbitrarily permuted (e.g., n=13, s could be a shuffle of the digits of all numbers 1..13 except k). Numbers have no delimiters; 1–9 are one digit, 10–99 are two digits. Explain your approach and time/space complexity.

Quick Answer: A coding interview question on locating a digit position within concatenated integers to find a missing number. Covers the string-parsing and combinatorial approach with a complete worked solution.

Part 1: Find Missing Number in Ordered Concatenation

You are given an integer n and a digit string s. The string was formed by concatenating the decimal representations of all integers from 1 to n in natural order, except that exactly one number k is missing. Return the missing number k. Because the original order is preserved, the digits in s still appear exactly as 1, 2, 3, ..., n would appear, with one whole number skipped. Examples: - n = 5, s = "1234" -> 5 - n = 5, s = "1345" -> 2

Constraints

  • 1 <= n <= 99
  • s contains only digits
  • s is formed by concatenating the numbers 1..n in increasing order with exactly one number removed
  • Numbers 1-9 contribute one digit each; numbers 10-99 contribute two digits each
  • s may be an empty string when n = 1

Examples

Input: (5, '1234')

Expected Output:

Explanation: The sequence should be 12345. The final number 5 is missing.

Input: (5, '1345')

Expected Output:

Explanation: The digits jump from 1 to 3, so 2 is missing.

Hints

  1. Walk through the numbers from 1 to n while keeping a pointer into s.
  2. At the first number whose string representation does not match the next characters of s, that number is the answer.

Part 2: Find Missing Number from Shuffled Concatenated Digits

You are given an integer n and a digit string s. Start with the decimal representations of all integers from 1 to n, remove exactly one number k, concatenate the rest, and then arbitrarily shuffle all remaining characters. Return the missing number k. Since the digits are shuffled, the original order is lost. You must determine the missing number using only the multiset of digits. Important: some ranges could be ambiguous if two different numbers use the same digits (for example, 12 and 21). For this problem, test cases guarantee that exactly one missing number is consistent with the given digit counts.

Constraints

  • 1 <= n <= 99
  • s contains only digits
  • s is a permutation of the digits from concatenating 1..n with exactly one whole number removed
  • Numbers 1-9 contribute one digit each; numbers 10-99 contribute two digits each
  • Test cases guarantee that exactly one value k in [1, n] matches the missing digit multiset
  • s may be an empty string when n = 1

Examples

Input: (1, '')

Expected Output:

Explanation: Edge case: the only number is missing, so no digits remain.

Input: (9, '98765321')

Expected Output:

Explanation: The shuffled digits contain every digit from 1 to 9 except 4.

Hints

  1. Count how many times each digit 0-9 appears in all numbers from 1 to n, then subtract the counts seen in s.
  2. The remaining digit-frequency pattern must match the digits of the missing number.

Loading coding console...