#prefix sum

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 are given an array of integers A and you will be asked to answer some queries. Each query is in the form: 1 i j And you have to return the paity (Odd/Even) of sum of absolute values from A[i] to A[j], that is: 1 A[i] + A[i+1] + ... + A[j] Input Format First Line of Input contains N and Q separated by space. Next Line contains N space separated integers. [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]

Given an array of \( n \) integers where \( n > 1 \), \( nums \), print an array \( output \) such that \( output[i] \) is equal to the product of all the elements of \( nums \) except \( nums[i] \).

Solve the problem in \( O(N) \) without using division.

[Read More]

Solutions This problem looks like a classical puzzle: merging overlapping intervals. A naive approach is \(O(N^2)\) and consists in checking each route with the others. In case they overlap, remove the other route from the array and merge both into the first one. The crucial condition to check if two routes overlap is (assuming route1 precedes route2): 1 route1.end >= route2.begin For example: 1 2 3 1 5 3 6 10 32 1 5 overlaps with 3 6, indeed 5 >= 3. [Read More]

Warning: HackerRank has recently changed the constraints of this problem but it did not update the challenge itself. Now they allow zeros to be part of the input. In particular this can cause empty sub-arrays to be a valid solution. For example this was not valid input before the update: 1 2 0 0 0 Now it is. A solution is the position 0 since the left sub-array is empty. [Read More]

Solutions A good strategy consists in selling one share only if that increases someday in the future. The best time to sell it corresponds to highest price reached after the day we buy the stock. For instance: 1 2 5 100 The best strategy is: at day 1 we buy the stock and we pay 2 at day 2 we buy the stock and we pay 5 (we don’t sell the stock bought before yet) at day 3 we sell both the stocks by earning 100-2 + 100-5 = 193 In other words, the best strategy consists in buying every stock at price \(p_i\) only if in the future the stock price \(p_i\) is surpassed. [Read More]

Solutions The naive solution involves storing each number into the buffer and calculating the product when requested: 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 37 38 39 class NaiveStreamingQualityAnalyzer { public: void add(int num) { stream.push_back(num); } int get(int k) { int product = 1; for (auto i = ssize(stream)-k; i < ssize(stream); ++i) { product *= stream[i]; } return product; } private: std::vector<int> stream; }; int main() { int n, i, j; cin >> n; NaiveStreamingQualityAnalyzer stream; while (n--) { cin >> i >> j; if (i == 1) { stream. [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]

To solve the problem we can easily observe that swapping the first c with the last p minimizes the tastiness. The answer is \(0\) when either: there are not p there are not c the last p is before the first c For example: 1 pppccc Instead, if neither of the conditions above occur, we swap the first occurrence of c with the last occurrence of p and we proceed with computing the tastiness. [Read More]