Katkat
Back

Count ordered pairs that concatenate to target

Capital OneSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

This question evaluates a candidate's ability to manipulate string and numeric representations, perform efficient counting, and leverage associative data structures to identify matching concatenations.

Given a list of integers numbers and an integer target, count the number of ordered pairs (i, j) with i != j such that concatenating numbers[i] followed by numbers[j] (in base-10) produces exactly target.

More precisely, treat each integer as its usual base-10 string without extra leading zeros (e.g., 12 -> "12"). Count pairs where:

str(numbers[i]) + str(numbers[j]) == str(target).

Return the total count.

Example

  • numbers = [1, 212, 12, 12], target = 1212

Valid ordered pairs:

  • (0, 1): "1" + "212" = "1212"
  • (2, 3): "12" + "12" = "1212"
  • (3, 2): "12" + "12" = "1212"

Return 3.

Assumptions / Constraints

  • Assume all integers are non-negative.
  • 1 ≤ len(numbers) ≤ 2e5 (you should aim for better than O(n^2) if possible).
  • Values fit in 32-bit signed integers.