#frequency table

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]

Warning: HackerRank has recently changed the constraints of the problem by allowing duplicates. This change invalidated a couple of our solutions. This is discussed in the post. Solutions We found many solutions to this challenge. Naive solution 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 bool isBeautiful(int i, int j, int k, int d, const vector<int>& arr) { int a = arr[j] - arr[i]; int b = arr[k] - arr[j]; return a == b && a == d; } int beautifulTriplets(int d, vector<int> arr) { int n = arr. [Read More]

Solutions We need to check if any row, columns or sub-grid contains duplicates. We can use an array of booleans (or a frequency array) for each type of component to check. Here is the idea: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int main() { bool row[9][9]{}, column[9][9]{}, grid[3][3][9]{}; int N, r, c, v; cin >> N; for (int i = 0; i < N; ++i) { cin >> r >> c >> v; r--; c--; v--; if (row[r][v] || column[c][v] || grid[r / 3][c / 3][v]) { cout << "WRONG INPUT"; return 0; } row[r][v] = column[c][v] = grid[r / 3][c / 3][v] = true; } cout << "OK"; } Basically, we read a coordinate and we check if it has been already allocated in any of the component. [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]

Given an unsorted array of \( n-1 \) elements, it is missing exactly one element from the sequence of \( 1 \) to \( n\). Find the missing element. Input Format An integer \( n \) followed by \( n-1 \) space separated numeric values. Constraints \( 1<n<10^6 \) Output Format The missing value. Solutions This is an example of problems that we call manifold at Coding Gym, since they give us room to find several alternative solutions. [Read More]

Solutions This problem is an application of the classical running median problem with a complication: the sliding window. The running median consists in calculating the median of all the subarrays from 0 to N. For example: 1 2 3 4 5 6 7 10 1 5 7 9 3 [10] -> 10 [10 1] -> (10+1)/2 [10 1 5] -> 5 [10 1 5 7] -> (5+7)/2 [10 1 5 7 9] -> 7 [10 1 5 7 9 3] -> (5+7)/2 The typical solution to this problem involves two (differently ordered) heaps that maintain the two halves of the input arranged in a way that is convenient to retrieve the maximum of the former and the minimum of the latter. [Read More]

Solutions Warning: the problem I/O might result slow. For some languages (e.g. C++), it’s better off reading the whole input first. This problem requires some additional storage to be solved efficiently. Using only one hash map is not enough because of operation of type 3. The idea is to use a hash map to store the frequencies of each element (query type 1 and 2) and also an additional hash map “histogram”, that is an inverse map from frequency to elements having such a frequency. [Read More]

Solutions A palindrome string is one which has every char appearing in pairs except, eventually, one in the middle. So we can just count all the occurrences and check if the string has only one (or zero) odd occurrence. A C++ Solution: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 #include <iostream> #include <algorithm> #include <string> using namespace std; int main() { int occ[26] = {}; string s; cin>>s; for (auto i : s) ++occ[i-'a']; const auto odd = count_if(begin(occ), end(occ), [](int i { return i%2! [Read More]

Solutions For each possible character, we can check if it’s present in all rocks. A Python solution by Yuri Valentini. 1 2 3 4 5 6 7 8 9 10 11 import sys from functools import reduce n = int(input().strip()) rock = [] rock_i = 0 for rock_i in range(n): rock_t = str(input().strip()) rock.append(frozenset(rock_t)) inters = reduce((lambda a,b: a & b), rock) print(len(inters)) Another one: 1 print(len(set.intersection(*[set(input()) for _ in range(int(input()))]))) Another one in C#: [Read More]

Solutions This problem can be solved by considering a few things: if a ladybug’s color is unique in the set, the ladybug will never be happy (the solution is “NO”) if 1) does not occur and if there is at least one empty cell, then the solution is always “YES” since it’s always possible to rearrange the ladybugs in the best position if 2) does not occur then the solution is “YES” only if all the ladybugs are already happy (because they cannot be moved) The first two properties are easy to check by using a frequency table (can be implemented with a map/dictionary or with a statically-sized array, since the number of letters is known - \(|A-Z|\)|). [Read More]