Beautiful Pairs

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]

Beautiful Triplets

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]

Game of Thrones

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]

Gemstones

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. [Read More]

Happy Ladybugs

Solutions This problem can be solved by considering a few things: 1) if a ladybug’s color is unique in the set, the ladybug will never be happy (the solution is “NO”); 2) 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; 3) if 2) does not occur then the solution is “YES” only if all the ladybugs are already happy (because they cannot be moved) [Read More]

Making Anagrams

Solutions Two strings are anagrams of one another if they share the same characters and each character has the same frequency in both strings. Thus, we can easily solve this problem with a frequency table. Basically, we can add 1 for each character in a and subtract 1 for each character in b. Those characters with non-zero frequency must be deleted and then added to the total count. Here is an implementation in C++: [Read More]

Picking Numbers

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]

Sherlock and Pairs

Solutions Sort C++ solution using sorting (\(O(N \cdot logN)\): 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int T, N; cin >> T; while (T--) { cin >> N; vector<int> nums; nums.reserve(N); copy_n(istream_iterator<int>(cin), N, back_inserter(nums)); sort(begin(nums), end(nums)); auto it = begin(nums); unsigned long long pairs = 0; while (it != end(nums)) { auto ub = find_if(it, end(nums), [&](int i){ return i! [Read More]

Sherlock and the Valid String

Solutions **Warning: ** HackerRank does not fully cover this challenge with tests. You can write a solution which passes all the tests but not this test case: 1 aaavvbbb That should be NO. An example of code that passes all the tests but the one above: 1 2 3 4 5 6 fun isValid(s: String): String { val listLetters = s.groupingBy { it }.eachCount().toList() val dif = listLetters. [Read More]

String Construction

Solutions Intuition: we only pay the number of distinct letters in s. The rest can be copied. Thus, the solution consists in simply counting the number of distinct characters in s. Haskell Just use Set to count unique characters. 1 2 3 4 5 6 7 8 9 import qualified Data.Set as Set import Data.List (intercalate) calculateCost = length . Set.fromList main = do _ <- getLine contents <- getContents putStrLn . [Read More]