How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Chime.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Chime during technical interviews.

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: This question evaluates proficiency in string parsing, combinatorial reasoning, frequency analysis, and algorithmic problem solving for reconstructing a missing integer from concatenated or permuted digit sequences.

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.

Input: (13, '123456789111213')

Expected Output:

Explanation: After 9, the next expected number is 10, but the string continues with 11.

Input: (1, '')

Expected Output:

Explanation: Edge case: the only number in the range is missing, so the string is empty.

Solution

def solution(n, s):
    pos = 0

    for num in range(1, n + 1):
        token = str(num)
        if s[pos:pos + len(token)] == token:
            pos += len(token)
        else:
            return num

    return -1

Time complexity: O(n), because each number from 1 to n is checked once and each has at most 2 digits.. Space complexity: O(1).

Hints

Walk through the numbers from 1 to n while keeping a pointer into s.
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.

Input: (13, '911182763145321')

Expected Output:

Explanation: Compared with all digits from 1..13, the missing multiset is one '1' and one '0', which corresponds to 10.

Input: (12, '2101987654321')

Expected Output:

Explanation: The missing digit multiset is two '1' characters, so the missing number is 11.

Solution

def solution(n, s):
    def digit_count(value):
        counts = [0] * 10
        for ch in str(value):
            counts[ord(ch) - ord('0')] += 1
        return counts

    total = [0] * 10
    for num in range(1, n + 1):
        for ch in str(num):
            total[ord(ch) - ord('0')] += 1

    seen = [0] * 10
    for ch in s:
        seen[ord(ch) - ord('0')] += 1

    missing_counts = [total[d] - seen[d] for d in range(10)]

    for num in range(1, n + 1):
        if digit_count(num) == missing_counts:
            return num

    return -1

Time complexity: O(n + |s|), since each number from 1 to n has at most 2 digits and the string is scanned once.. Space complexity: O(1), because only fixed-size digit-frequency arrays of length 10 are used..

Hints

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

Quick Overview

This question evaluates proficiency in string parsing, combinatorial reasoning, frequency analysis, and algorithmic problem solving for reconstructing a missing integer from concatenated or permuted digit sequences.