Count ordered pairs that concatenate to target

Q: Count ordered pairs that concatenate to target

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.

Count ordered pairs that concatenate to target

Overview

Example

Assumptions / Constraints

Comments (0)