# 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

### View

The

`.view`

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