#sort

Consider an array of numeric strings where each string is a positive number with anywhere from \( 1 \) to \( 10^6 \) digits. Sort the array’s elements in non-decreasing, or ascending order of their integer values and print each element of the sorted array on a new line. See Big Sorting on HackerRank. Solutions We may be tempted to use arbitrary precision arithmetic - e.g. Big Integers. This is not needed and it’s possibly slow to convert from/to the decimal number system. [Read More]

Solutions Sorting the sequence is the key to solve this challenge. Here is a C++ Solution based on zip | map | reduce pattern: 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 <numeric>using namespace std; int main() { int N; cin >> N; vector<int> v; v.reserve(N); copy_n(istream_iterator<int>(cin), N, back_inserter(v)); sort(begin(v), end(v)); auto minDiff = inner_product(next(begin(v)), end(v), begin(v), numeric_limits<int>::max(), [](int curr, int nxt){ return min(curr, nxt); }, minus<>{} ); equal(begin(v), end(v)-1, begin(v)+1, [=](int l, int r){ if (abs(r-l) == minDiff) cout << l << " " << r << " "; return true; }); } Here is a Javascript solution by Simone Busoli: [Read More]

Solutions This problem falls into the greedy category. A hotel can accomodate all customers in a distance of \(-k\) and \(+k\). We should find the smallest amount of intervals of length \(2k\) that cover all the positions of the customers. First of all, we sort the positions of the customers. We iterate over all the sorted positions and, at each step, we calculate the difference between adjacent positions. We keep track of the interval by incrementing a running sum of the such differences. [Read More]

Solutions This is a simple greedy algorithm. Naming \(t_i\) the time of order \(i\) and \(d_i\) the time needed to complete order \(i\), we sort all the orders by \(t_i + d_i\) and by \(i\). The idea implemented in C++: 1 2 3 4 5 6 7 8 9 10 int N, ti, di; cin >> N; vector<pair<int, int>> orders(N); for (auto i=1; i<=N; ++i) { cin >> ti >> di; orders[i-1] = {ti+di, i}; } sort(begin(orders), end(orders)); for (const auto& o : orders) cout << o. [Read More]

Solutions Since we need to maximize the number of toys, we can sort the array in incresing order of price and pick them as long as the budget is available. A solution in C++: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include <iterator>#include <vector>#include <iostream>#include <algorithm>using namespace std; int main() { int n, k; cin >> n >> k; vector<int> prices(n); copy_n(istream_iterator<int>(cin), n, begin(prices)); sort(begin(prices), end(prices)); auto toys = 0, cost=0; for (auto i=0u; i<prices. [Read More]

Solutions The problem reduces to chosing 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]

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]

Solutions The naive solution is quadratic and it’s too slow for a few test cases. We show it here, for completeness: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include <iterator>#include <climits>#include <vector>#include <iostream>#include <algorithm>using namespace std; int main() { int n; cin >> n; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); auto minLoss = INT_MAX; for (auto i=0; i<n; ++i) { for (auto j=i+1; j<n; ++j) { if (v[i] > v[j]) { minLoss = min(minLoss, v[i] - v[j]); } } } cout << minLoss; } Set-based solution We need to amortize the internal loop. [Read More]

Solutions Sorting A C++ solution based on sorting and a sliding window made of two increasing pointers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include <numeric>#include <array>#include <vector>#include <iostream>#include <algorithm>#include <iterator>using namespace std; int main() { int n; cin >> n; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); sort(begin(v), end(v)); auto selected = 0; auto tail = begin(v); auto head = next(tail); while (head ! [Read More]

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order, in linear time. Input Format The first line contains N, the length of the array. The second line contains N space-separated integers, the elements of the array. Constraints \(1 \leq N \leq 10^6\) \(-10^3 \leq A[i] \leq 10^3\) Output Format Print the array of the squares of each number, also in sorted non-decreasing order. [Read More]