## Birthday Chocolate

Solutions The solution to this problem when d=1 can be used to solve Picking Numbers as well. A linear solution consists in: computing the prefix sum of the input array keeping a window of size m counting how many times the window bounds differ by d Here is a solution in C++: 1 2 3 4 5 6 7 8 9 10 11 12 13 int n, d, m; cin >> n; vector<int> v(n+1); copy_n(istream_iterator<int>(cin), n, next(begin(v))); cin >> d >> m; partial_sum(begin(v), end(v), begin(v)); auto cnt = 0; for (auto i=0; i<=n-m; ++i) { cnt += v[i+m] - v[i] == d; } cout << cnt; The loop can be replaced with zip | map | reduce combination of patterns: [Read More]

## Equal Stacks

Solutions C++ Solution very pretty much independent from the number of the stacks (just change numberOfStacks): 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 const int numberOfStacks = 3; array<int, numberOfStacks> n{}; for (auto& i : n) cin >> i; array<vector<int>, numberOfStacks> stacks; array<int, numberOfStacks> heights{}; for (auto i=0; i<n. [Read More]

## Exam Plan

Solutions Since we want to maximize the number of chapters, we just sort the array and pick the first chapters which sum is less than or equal to $$t$$. Here is a C++ implementation: 1 2 3 4 5 6 7 8 9 10 11 12 13 int n, t; cin >> n >> t; vector<int> v(n); copy_n(istream_iterator<int>(cin), n, begin(v)); sort(begin(v), end(v)); auto cnt = 0; for (auto i=0; i<n; ++i) { if (t-v[i] < 0) break; t -= v[i]; cnt++; } cout << cnt; The solution is $$O(N \cdot logN)$$. [Read More]

## Flatland Space Stations

Solutions Quadratic solution This Python solution by Davide Peron calculates the difference for each combination of city/station, keeps the minimum for each city and then takes only the maximum. 1 2 def flatlandSpaceStations(n, c): return max(min(abs(city - sta) for sta in c) for city in range(n)) Linear solution The problem can be solved linearly. Assume $$arr[i]=1$$ if the $$i^th$$ city has a space station, $$0$$ otherwise. Now calculate $$c[i]$$ which denotes the distance to the nearest space station on the left. [Read More]

## Number of Subordinates

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]

## Odd or Even Sum

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. [Read More]

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

## Product of Array Except Self

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.

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