#constrained

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 We can see, intuitively, that the number of people a person \(p\) has bribed corresponds to the number of people on her right with value less than \(p\). For instance: 1 1 2 3 5 4 In this case, \(5\) has bribed \(4\) and took her position. Another example: 1 2 1 5 3 4 We have three bribes: \(2\) has bribed \(1\) \(5\) has bribed \(4\) \(5\) has bribed \(3\) This problem is equivalent to calculating the number of inversions of the array, that is the number of elements that are out of the natural order of a sequence. [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]

Preamble This is a typical challenge where the environment we have to work in is constrained and we have to find a solution under some conditions. Same story when we are not allowed to allocate extra space, or when some basic operation is disabled (e.g. for loop). Why “constrained” challenges make perfect sense Although such challenges could seem senseless, they are instead very useful to improve our ability to adapt. In the real life this skill is generally very important. [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]