#frequency table

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). Brute force solution 1 2 3 4 5 6 7 8 9 10 fn solve(m: usize, flavors: &[usize]) -> (usize, usize) { for (i, x) in flavors. [Read More]

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]

Solutions The brute force solution has a quadratic time complexity and involves iterating through each value while checking if it forms a matching pair. For example: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int N; cin >> N; vector<int> cards(N); copy_n(istream_iterator<int>(cin), N, begin(cards)); auto res = std::numeric_limits<int>::max(); for(auto i=0; i<N; ++i) { for(auto j=i+1; j<N; ++j) { if(cards[i] == cards[j]) { res = min(res, j-i+1); } } } cout << (res == std::numeric_limits<int>::max() ? [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]

Solutions The solutions revolve around finding the frequency of the card values. In addition, checking flush requires us to verify all the suits are equal. This check can be done in advance or while counting the frequency of each card. Afterwards, mapping the card frequency to the score is straighforward: find the maximum frequency and that will give the score: 1 is “High Card” 2 is “Pair”, 3, 4 and 5 are “Three of a Kind”). [Read More]

Solutions This problem is very easy but, as we’ll see in a minute, it can be solved in a very clever way. The easiest approach uses extra space, a frequency table. The core of the algorithm in C++: 1 2 3 4 5 6 7 8 9 10 11 12 13 int N; cin >> N; vector<int> A(2*N); copy_n(istream_iterator<int>(cin), 2*N, begin(A)); vector<int> freq(1'000'000 + 1); for (auto i : A) { freq[i]++; if (freq[i] > 1) { cout << i; break; } } This solution is linear. [Read More]

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]

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.filter { listLetters.first().second != it. [Read More]

MegaBytus is a young and promising wizard who loves programming and computers. The master GigaBytus gave him a task: crafting a spell to rearrange the digits of a number such that the number obtained is the smallest possible. MegaBytus needs your help to find a way to verify that his spell works. Then you have to write a program that, given an integral number, will find the smallest number obtained by rearranging its digits. [Read More]

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]