# Scala algorithm: Count pairs of a given expected sum

Published

## Algorithm goal

In a set of items, could the number of pairs that sum up to a particular number. For example, if you have a list of (1, 2, -1), then the number of pairs that sum to 1 would be only 1, ie (2, -1). If you had a list of (1, 2, -1, 3, 4), then to sum to 3, the number of pairs is 2: (1, 2) and (-1, 4), and no others. But if you have (1, 1, 1, 1) and the target sum is 2, then you have 6 pairings (1st with 3 others, 2nd with 2 others, 3rd with 1 other).

## Test cases in Scala

``````assert(countPairsSummingTo(List.empty, ofSum = 2) == 0)
assert(countPairsSummingTo(List(1), ofSum = 1) == 0)
assert(countPairsSummingTo(List(1, 1), ofSum = 1) == 0)
assert(countPairsSummingTo(List(1, 1), ofSum = 2) == 1)
assert(countPairsSummingTo(List(1, 1, 1), ofSum = 3) == 0)
assert(countPairsSummingTo(List(1, 1, 1, 1), ofSum = 2) == 6)
assert(countPairsSummingTo(List(1, 2, -1), ofSum = 1) == 1)
assert(countPairsSummingTo(List(1, 2, -1, 3, 4), ofSum = 3) == 2)
``````

## Algorithm in Scala

10 lines of Scala (compatible versions 2.13 & 3.0), showing how concise Scala can be!

## Explanation

This is a counting problem. The most natural thing to do is to consider what we can do after grouping all the unique elements, as for each of those elements, we would have a particular count of occurrences.

Once we do that, we can get the target number to check in this unique count-map by looking up `ofSum - n` and then summing all these counts. (this is © from www.scala-algorithms.com)

Lastly, we divide this by 2 to reduce the duplicates (because when iterating, we cover every pairing twice).

## Scala concepts & Hints

1. ### View

The `.view` syntax creates a structure that mirrors another structure, until "forced" by an eager operation like .toList, .foreach, .forall, .count.

# Scala Algorithms: The most comprehensive library of algorithms in standard pure-functional Scala

## How our 100 algorithms look

1. A description/goal of the algorithm.
2. An explanation with both Scala and logical parts.
3. A proof or a derivation, where appropriate.
4. Links to Scala concepts used in this specific algorithm, also unit-tested.
5. An implementation in pure-functional immutable Scala, with efficiency in mind (for most algorithms, this is for paid subscribers only).
6. Unit tests, with a button to run them immediately in our in-browser IDE.

### Study our 100 Scala Algorithms: 6 fully free, 100 published & 0 upcoming

Fully unit-tested, with explanations and relevant concepts; new algorithms published about once a week.

### Explore the 22 most useful Scala concepts

To save you going through various tutorials, we cherry-picked the most useful Scala concepts in a consistent form.

## Subscribe to Scala Algorithms

Maximize your Scala with disciplined and consistently unit-tested solutions to 100+ algorithms.

Use it from improving your day-to-day data structures and Scala; all the way to interviewing.