Max Min

Solutions The problem reduces to choosing K consecutive numbers in a sorted list for which the value of D is minimum. Which can be easily done by sorting the given number and calculating D for each group of K consecutive number. Here is a possible C++ Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include <iterator> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <climits> using namespace std; int main() { int N, K; cin >> N >> K; vector<int> v(N); copy_n(istream_iterator<int>(cin), N, begin(v)); sort(begin(v), end(v)); auto tail = 0; auto head = K-1; auto unfairness = INT_MAX; while (head<N) { unfairness = min(unfairness, v[head]-v[tail]); tail++; head++; } cout << unfairness; } This results in a combination of zip | map | reduce patterns that in C++ can be written in terms of inner_product: [Read More]

Minimum Absolute Difference in an Array

Solutions The brute force solution consists in calculating the absolute difference of each pair and reducing to the minimum value. This takes $$O(N^2)$$. We can find better solution, instead, by making a simple observation: the closest two numbers, the lowest their difference. It’s just like calculating the distance between points on the same axis. Indeed, the formula to calculate the distance between two points $$x1, x2$$ on the same axis is simply $$|x1-x2|$$. [Read More]