#prefix sum

Solutions This easy challenge has, actually, an interesting generalization. The problem can be quickly solved by noting that the number of elements to select is one less (4) than the length of the input array (5). So we can just sum all the numbers and subtract the result to the max and to the min of the array. The domain is subject to overflow so we have to use a 64-bit integer: [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 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]

Solutions The brute-force approach to solve this problems involves generating all the possible substrings of the input number. This requires \(O(N^2)\) time, which becomes too expensive in the worst case when the input size can be as large as \(2 \cdot 10^5\). To find an efficient solution, let’s consider the input 8314. All the possible substrings are listed below: 1 2 3 4 8 3 83 1 31 831 4 14 314 8314 Each line contains all the substrings ending with the corresponding digit. [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]