#Binary Search

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 This problem has two main solutions. The first fully exploits the structure of the constraints, the second is more general. Tradeoffs of both: we remove all the duplicates. In a different context this could be forbidden and then we would have to use extra space or another logic; we don’t really change the score table. Instead, in a real game it’s very likely that we need to update the current scores (e. [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]

The jedi apprentice Bin Logar is studying new lightsaber attack schemas for his year-end examination. In particular, he has found a secret technique to easily win duels when the battle takes place on uplands and small hills. Bin is working out hard but his technique is still too slow because Bin needs to determine the maximum height of the battleground more quickly. For this reason you decide to help him. [Read More]

Consider an array of integers A = [a1, a2, …, aN]. We can perform two types of queries on A: 1 k: For query type 1, find and print an integer denoting the index of the kth zero in array A on a new line; if no such index exists (i.e., there is no zero), print NO instead. p x: For query type 2, replace the element positioned at index p with integer x (i. [Read More]

Alan has finally reached the final round of interviews at Gugol. He is one step from catching the job he loves and he has to impress the interviewer with a killer answer to the last question. The problem looks like very easy: given an array where all elements appear even number of times except one. All repeating occurrences of elements appear in pairs and these pairs are not adjacent (there cannot be more than two consecutive occurrences of any element). [Read More]

Solutions The naive solution is quadratic and it’s too slow for a few test cases. We show it here, for completeness: 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 <iterator> #include <climits> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); auto minLoss = INT_MAX; for (auto i=0; i<n; ++i) { for (auto j=i+1; j<n; ++j) { if (v[i] > v[j]) { minLoss = min(minLoss, v[i] - v[j]); } } } cout << minLoss; } Rust naive solution: [Read More]

Given two unsorted arrays arr1 and arr2 - possibly containing duplicates - for each element in arr1 print the number of elements less than or equal to it in array arr2. Input Format The first line contains an integer N. Two lines follow: the first array: N space-separated elements the second array: N space-separated elements Constraints N and M are at most 100'000 Each array element is at least 0 and at most 100'000. [Read More]

You will be given an array of integers and a target value. Determine the number of pairs of array elements that have a difference equal to a target value.

[Read More]

Solutions The linear solution is simple: just count the frequencies of both negative and positive integers. However, the optimal solution is more interesting: leveraging the sorted nature of the array, we can exploit binary search. Here’s where a crucial detail comes into play: 0 is neither positive nor negative. Consequently, searching for 0 presents us with an opportunity to swiftly determine the count of positive and negative integers. In essence, we need to recall two fundamental concepts regarding binary searches: [Read More]