## Electronics Shop

Solutions A simple solution consists in running two nested for loops to calculate the possible costs. Although this solution is $$O(n \cdot m)$$, it’s acceptable since the input is small: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 int s, n, m; cin >> s >> n >> m; vector<int> k(n); copy_n(istream_iterator<int>(cin), n, begin(k)); vector<int> u(m); copy_n(istream_iterator<int>(cin), m, begin(u)); auto cost = -1; for(auto i : k) { for (auto j : u) { if (i+j<=s) cost = max(cost, i+j); } } cout << cost; Linq-based solution, with cartesian product (by fabrizio_sanmar1): [Read More]

## Find the Maximum Difference

You are given a sequence of integers S, your task is to find a pair i,j of indices with i<j that maximizes the difference S[j]-S[i]. Note that what makes this challenge more interesting is the requirement of order, that i < j (without it you simply need to find the maximum and minimum element of S). You have to output the value of the maximum difference. Input Format An integer N followed by N space separated integers S[i] on a new line. [Read More]

## Ice Cream Parlor

Solutions The brute force approach is easy: just run two nested loops and for each value $$x$$ find if it exists a value equals to $$target - x$$. This solution is quadratic. Efficient solutions are based either on sorting or additional storage (e.g. frequency table, hash maps). A sort-based solution Suppose we sort the prices $$p$$ in ascending order. Consider the sum $$p[0] + p[n-1]$$ where $$n$$ is the number of available prices. [Read More]

Given an array of integers A sorted in non-decreasing order, return an array of the squares of each number, also in sorted non-decreasing order, in linear time. Input Format The first line contains N, the length of the array. The second line contains N space-separated integers, the elements of the array. Constraints $$1 \leq N \leq 10^6$$ $$-10^3 \leq A[i] \leq 10^3$$ Output Format Print the array of the squares of each number, also in sorted non-decreasing order. [Read More]