ETH_Informatik/Informatik_I/Exercise_9/Task_4

Task 4: [Hidden tests][Exam 2019.02 RW] Number Pairs with Sum

• Number of pairs with given sum
• Task
• Input & Output
  • Example:
• Hidden test cases
  • Persistent input
• Solution

Number of pairs with given sum

In this exercise, you are going to use iterators to count the number of pairs in a vector which sum up to a given value.

More formally, given a vector \(v\) of length \(n\) and a value \(s\), we are interested in the number of pairs \(i\),\(j\) for which the following conditions hold:

1. \(0 leq i < j < n\)
2. \(v\[i\] + v\[j\] = s\)

Task

The function pairs_with_sum declared in pair_sum.h computes the number of pairs which sum up to a given value. Your task is implementing this function in pair_sum.cpp.

Input & Output

The program first reads a list of integers (separated by spaces) from std::cin. The first integer specifies the value \(s\). The other integers specify the vector \(s\).

The program then calls the function pairs_with_sum(s, v.begin(), v.end()) to compute the number of pairs that sum up to \(s\).

Finally, the result is printed to the console.

Example:

• sum = 8, vector = 1 7 2 6 6
• pairs with sum(1,7), (2,6), (2,6)
• \(Rightarrow\) number pairs = 3.

8 1 7 2 6 6
number of pairs with sum 8: 3

Note: This was a task in the 2019.02 RW exam but has since been adapted slightly: better input handling (no need to press CTRL+D/CTRL+Z to end vector), description, file structure, and master solution.

Note: You can safely assume that the sum of two values in the vector does not cause an overflow.

Hidden test cases

This exercise has some hidden test cases. You will see whether these tests passed or failed, but you will not see the test input or the expected output.

Persistent input

To help you in testing your code, you can enter your custom test input in input.txt. When running the program, you can let CodeExpert read the input from the file.

Write some program input in input.txt. Run the program as usual. Type f (no spaces) in the terminal window and press Enter. The program will use the contents of input.txt as input. Using this feature is entirely optional and does not affect your score.

Solution

#include "pair_sum.h"
#include <climits>

// PRE:  for any two indices i and j, v[i] + v[j] ≤ INT_MAX
// POST: returns the number of indices (i,j), i<j of a vector v
//       that corresponds to the given iterator range such that
//       v[i] + v[j] == sum.
int pairs_with_sum(int sum, iterator begin, iterator end) {
  int count = 0;
  int size = end - begin;

  for (int i = 0; i < size; ++i) {
    for (int j = i + 1; j < size; ++j) {
      iterator cur_begin = begin + i;
      iterator cur_end = begin + j;
      if (*cur_begin + *cur_end == sum)
  ++count;
    }
  }

  return count;

---

Made by JirR02 in Switzerland 🇨🇭