Solve the same problem with an O(n²) method and an O(n) method, and compare the work each one does.
What to build
A program that looks for two numbers with a given sum in a sorted list, in two different ways.
Requirements
- Method 1 tries the pairs
i < jin order, withiand thenjincreasing, adding 1 to its counter for every pair tried, and stops at the first pair with the right sum. - Method 2 keeps
lo = 0andhi = n - 1. Whilelo < hi, it adds 1 to its counter and checks the sum of the two numbers. It stops if the sum is right, movesloright if the sum is too small, and moveshileft if the sum is too large. - Print whether a pair exists, then the two counters.
Input
The first line has n and the target S. The second line has the n numbers in increasing order.
Output
One line: yes or no, then the counter of method 1, then the counter of method 2.
Constraints
1 ≤ n ≤ 100, and each number and S are from -10000 to 10000.
Example
Input:
5 10
1 3 4 6 9
Output:
yes 4 1
Why it works
Each step of method 2 rules out one number for good, so it does at most n − 1 steps. Method 1 may try all n(n − 1) / 2 pairs. Sorted data is what makes the faster method possible.
Examples
5 10 1 3 4 6 9
yes 4 1
4 20 2 4 7 8
no 6 3
Hints
Hint 1
For the slow method, use two loops and stop both as soon as a pair is found.
Hint 2
For the fast method, start one index at each end. If the sum is too small, move the left one right. If it is too large, move the right one left.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, s, a[100];
scanf("%d %d", &n, &s);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int found = 0, slow = 0, fast = 0;
for (int i = 0; i < n && !found; i++) {
for (int j = i + 1; j < n; j++) {
slow++;
if (a[i] + a[j] == s) {
found = 1;
break;
}
}
}
int lo = 0, hi = n - 1;
while (lo < hi) {
fast++;
int sum = a[lo] + a[hi];
if (sum == s) break;
if (sum < s) lo++;
else hi--;
}
printf("%s %d %d\n", found ? "yes" : "no", slow, fast);
return 0;
}