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]

Secret repetition

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]

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

Smallest Rearrangement Spell

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]

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]

The Lucky Employee

Summer is over and people at Gugol are sad and unmotivated. They would prefer going back on vacation instead of working - how to blame them? Ted, head of employee happiness department, has got an idea to cheer people up: he will run a lottery among all the employees and will award the luckiest one with two extra weeks of vacation. The lottery will work this way: Ted will raffle off some ranges of employee ids like \( [120, 200] \) and \( [150, 180] \), a sophisticated algorithm will calculate which is the most frequent employee id in all such ranges, if more than one such an id exists, the sophisticated algorithm will select the smallest one - it corresponds to the employee who has been working at Gugol for more time You are a \( \cancel{slave} \) trainee at Gugol and you have to design and write such a sophisticated algorithm. [Read More]

The Most Frequent

You are given an array of N integers separated by spaces, all in one line. Display the element which occurs most frequently. If multiple elements satisfy this criteria, display the numerically smallest one. Input Format The first line contains the number of integers \(N\). The second line contains space separated integers \(xi\) for which you need to find the most frequent one. Constraints \(10 \leq N \leq 1'000'000 \) \(0 \leq xi \leq 100'000 \) Output Format One line containing the result. [Read More]

The Product Name

Solutions Basically, each character \(out_i\) of the output string \(out\) occurs the least number of times at index \(i\) among all the input strings. We can count the occurrences of each letter of the alphabet (26) for each position of the input strings. Since all the strings have \(5\) characters, we have \(5\) frequency tables. Thus, we use constant additional storage - for instance, an array containing 5 arrays of 26 integers. [Read More]