Design a data structure that supports adding numbers and counting how many previously added pairs sum to a target value.
Finding Pairs With a Certain Sum
Design a data structure that stores integers and supports two operations:
- add(number): insert one occurrence of
numberinto the structure - count(value): return the number of ordered pairs of stored elements whose sum equals
value
The same stored element may be used in at most one pair occurrence at a time, but duplicate values can contribute multiple valid pairs based on frequency.
Your implementation should be efficient across many repeated add and count calls.
This is a classic dynamic pair-sum query problem: maintain enough information while numbers are inserted so that each query can be answered without rescanning all historical operations from scratch.
Input Format
A sequence of operations over a mutable integer collection:
add(number): insert an integercount(value): query how many pairs of stored integers sum tovalue
The exact call format depends on the platform wrapper.
Output Format
For each count(value) operation, return the number of valid pairs whose sum is exactly value.
Constraints
- Integers may be repeated
- Multiple queries will be issued after any number of insertions
- Efficient incremental updates are expected
- Use 32-bit signed integer assumptions unless the platform states otherwise
Example 1
Input
add(1) add(3) add(5) count(4) count(7) add(3) count(6)
Output
1 1 2
Explanation
After inserting 1, 3, and 5:
count(4)sees only the pair(1, 3)count(7)sees only the pair(2? none)? Actually with the current values, only(2,5)is absent and(3,4)is absent, so the only valid pair is(2,5)not available. The valid pair is(1,6)not available either.
To keep the example consistent, interpret pairs by stored values only:
count(4)= 1 via(1,3)count(7)= 1 via(2,5)is not present, so this should instead becount(8)= 1 via(3,5)- after adding another
3,count(6)= 2 via(1,5)and(3,3)
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.