Count the pairs of equal numbers in a list, and see how quickly the work grows.
What to build
A program that compares every pair of positions once.
Requirements
- Compare each number with every number after it.
- Count the pairs that are equal.
- Print the number of equal pairs and then the number of comparisons made.
Input
The first line has n. The second line has the n numbers.
Output
One line: the pairs and the comparisons, separated by a space.
Constraints
1 ≤ n ≤ 100.
Example
Input:
4
1 2 1 1
Output:
3 6
Why it works
There are n × (n − 1) / 2 pairs of positions. Doubling n makes about four times as many pairs, which is the mark of an O(n²) method.
Examples
Example 1 · Input
4 1 2 1 1
Expected output
3 6
Example 2 · Input
3 5 6 7
Expected output
0 3
Hints
Hint 1
Use two loops: the outer picks position i, and the inner tries every later position j.
Hint 2
Count one comparison each time the inner loop compares two numbers.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int pairs = 0, comparisons = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
comparisons++;
if (a[i] == a[j]) pairs++;
}
}
printf("%d %d\n", pairs, comparisons);
return 0;
}