#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 performing the intersection between \(A\) and \(B\). Then, 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. [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]

Shopkeepers often round up the change during a purchase so that the change to be given can be a single bill, making it convenient for both the shopkeeper and the customer. For example, a customer has paid a \(200\) sesterzio bill for a purchase of \(104\) sesterzi. If the customer then gives an additional \(4\) sesterzi, then the cashier will give an exact \(100\) sesterzio bill in change, instead of several bills and coins if the change is \(96\) sesterzi. [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 The brute force approach is easy: just run two nested loops and for each value \( x \) find if it exists a value equals to \( target - x \). This solution is quadratic. Efficient solutions are based either on sorting or additional storage (e.g. frequency table, hash maps). A sort-based solution Suppose we sort the prices \( p \) in ascending order. Consider the sum \( p[0] + p[n-1] \) where \( n \) is the number of available prices. [Read More]