#sort

Solutions 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 25 26 27 28 #include <set>#include <cstdio>#include <vector>#include <iostream>#include <algorithm>using namespace std; int main() { int T; cin >> T; string s; while (T--) { cin >> s; if (s.size() % 2) { cout << -1 << endl; continue; } multiset<char> inters; const auto splitIt = begin(s)+(s. [Read More]

Solutions For each element in \(A\), we have to find the same element in \(B\). This is basically like finding the intersection between \(A\) and \(B\). Thenn, since we have to change one element in \(B\) in any case: if the intersection is just \(A\), we return A.size() - 1 otherwise, we return inters.size() + 1 Here is the idea in C++: 1 2 3 4 5 6 7 8 9 10 int beautifulPairs(vector<int>& A, vector<int>& B) { sort(begin(A), end(A)); sort(begin(B), end(B)); vector<int> inters; set_intersection(begin(A), end(A), begin(B), end(B), back_inserter(inters)); if (inters. [Read More]

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 This problem requires to find the smallest permutation of the input string that is also bigger than the input string. This is a classical problem in Computer Science (in mathematics, in general) and often it’s referred as finding the “next permutation in lexicographic ordering”. The method consists in: find the largest index \( i \) such that \( a[i] < a[i + 1] \). If no such index exists, the permutation is the last permutation; find the largest index \( j \) greater than \( i \) such that a[i] < a[j]; swap the value of \( a[i] \) with that of \( a[j] \); reverse the sequence from \( a[i + 1] \) up to and including the final element of the sequence. [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 The naive solution to this problem consists in sorting the array in ascending order, subtracting the minimum value from all the sticks and printing the count of non-zero sticks. We can do better and avoid updating the stick lengths at every step (that makes the solution quadratic). One way consists in visiting each element only once: 1 2 3 4 5 6 7 8 9 10 11 12 int N; cin >> N; vector<int> sticks(N); copy(istream_iterator<int>(cin), istream_iterator<int>(), begin(sticks)); sort(begin(sticks), end(sticks)); auto it = begin(sticks); while (it ! [Read More]

Solutions Since we want to maximize the number of chapters, we just sort the array and pick the first chapters which sum is less than or equal to \( t \). Here is a C++ implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 int n, t; cin >> n >> t; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); sort(begin(v), end(v)); auto cnt = 0; for (auto i=0; i<n; ++i) { if (t-v[i] < 0) break; t -= v[i]; cnt++; } cout << cnt; The solution is \( O(N \cdot logN) \). [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]