#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]

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]

Given a decimal number N between 1 and 4999, find its corresponding Roman numeral. Roman numerals are formed by the combination of these letters: 1 2 3 4 5 6 7 I=1 V=5 X=10 L=50 C=100 D=500 M=1000 Rules to combine letters: A letter repeats its value that many times (XXX = 30, CC = 200, etc.). A letter can only be repeated three times (except M). If one or more letters are placed after another letter of greater value, add that amount (VI = 6 (5+1)). [Read More]

The school term starts soon, and the students need to be sorted into their respective sections. There are \( n \) students numbered \( 1 \) to \( n \), and \( m \) sections numbered \( 1 \) to \( m \). Section needs to have exactly \( a_i \) students. To simplify the process, the school has decided to assign students to sections in increasing student number, which means the first \( a_1 \) students will be assigned section \( 1 \), the next \( a_2 \) students will be assigned section \( 2 \), and so on. [Read More]