Facebook Hackercup 2016- Boomerang constellations problem solution

This problem is from the recently concluded Facebook Hackercup 2016 Qualification round. You can take a look at the problem statement in this link.

I am giving the abridged problem statement here. Given a set of coordinates in a 2D-plane, We have to find out the total number of pairs of lines with equal length and also share one end point.

For example, let us take the points {(0,0), (0,1), (1,0)}, there is one pair of lines, with a distance of 1. The line between (0,0),  (0,1) and the line between (0,0), (1,0).

The simplest way to solve this problem is this. Take a point (x,y) and try to calculate the distance to every other point. Maintain a map of distance to the number of other end points with that distance. This is O(n2 log n) solution.

Here is the C++ code for the same.

Counting pairs in array

Given an array A of distinct numbers, how to count the number of pairs (i,j) such that
A[i] < A[j]

For example, let us consider A = [2, 1, 3]
the pairs are (1,2), (1,3), (2,3). So there are 3 pairs.
Similarly for A = [10, 6, 9, 2], there are 6 pairs

This problem was originally appeared in Codechef.

One straight forward solution is to loop through all possible pairs and count them.
But this has O(n2) time complexity.
We actually don’t need to count all the pairs because the elements are distinct.
Suppose we arrange the elements in sorted order

A = [1, 2, 3]
then the pairs are (1, 2), (1,3), (2,3)
A = [2, 6, 9, 10]
the pairs are (2, 6), (2,9), (2,10), (6, 9), (6, 10), (9,10)

If there are n elements in an array, there will be n*(n-1) pairs. Since the all the elements are unique, half of them satisfies the given property.

So the answer will be n*(n-1)/2

Finding the number in a shuffled array

Given an array [1, 2, 3,…N], we apply a series of reversal operations on different range of indices [L,R].
How to find out the position of a number after these operations are applied?

For example consider an array of 5 numbers [1, 2, 3, 4, 5] and the number 2.

Reverse elements between 1, and 3, the array becomes [3, 2, 1, 4, 5]
Reverse elements between 3, and 5, the array becomes [3, 2, 5, 4, 1]
Reverse elements between 2, and 5, the array becomes [3, 1, 4, 5, 2]

So the final position of 2 is 5.

This problem was originally appeared in Codechef.

If we want to track just one number, we need not perform reversal operations everytime. This process takes O(n^2) time in worst case.

As we perform the reversal operations, we just need to track what is the new position of target number.

How do we track the position?
Consider the positions L = left, R= right, C = current and the distance between L and C is X,
After we reverse the elements between L, R, C will be placed x steps before R

C – L = R – X
X = R + L – C
The new position of C will be (R+L-C)
The position of C will not be altered if we are reversing the part which includes C.

Here is the C++ code for the same which runs in O(n) time.

Odd number out

Given an array of numbers which contains all even numbers except one, or all add numbers except one.
How do you find the different number?

For example consider the array [1, 2, 3, 5, 9], 2 is the different number.
Similarly in the array [10, 6, 7, 24, 36], 7 is the different number.

This problem was originally appeared on Codeforces.

This is a simple implementation problem, which can be solved in one iteration.
When we are reading numbers, just keep track of the following information.

  • first even index
  • first odd index
  • even number count

At the end, check if the even number count is 1, If it is, then print first even index, otherwise print first odd index.
Here is the C++ code for this.

Number of ways to make coin change

Given some amount N, and a set of denominations, how do you find the number of ways to make change for N? Let us assume that there is infinite supply of coins for each denomination.

For example, if we have to make change for 4, and the given denominations are {1, 2, 3}, the possibilities are {1, 1, 1, 1}, {1, 1, 2}, {1, 3}, {2, 2}. So there are 4 possibilities in total.

Let us try to solve this problem using recursion. Let N be the amount for which we have to make change, and D is the set of denominations. Assume we have a method Count which takes in the parameter amount N, and the index of current denomination, we can have pseudo code like this

Count(N, index)

  • Base case#1: If N < 0 or index < 0 return 0. There is no way to make change for negative numbers or if there are no denominations
  • Base case#2: If N == 0, return 1. There is only one possibility to make change for 0 amount, selecting none.
  • Otherwise return Count(N, index-1) + Count( N-D[index], index ). Either ignore the current denomination (First term), or take the current denomination(second term) and recurse accordingly.

Since this recursive method solves the same problem multiple times, we can think of a dynamic programming solution for this problem. In dynamic programming, we solve the smaller sub problems first and use their results in solving bigger sub problems. We store the results in a table. Lets create a table[N+1][M] where N is the amount, and M is the denomination count.

  • table[0][j] = 1, Only one way to make 0.
  • table[i][0] = 1 if N is divisible by D[0], otherwise 0
  • table[i][j] = table[i][j-1] if D[j] > i
    = table[i][j-1] + table[i- D[j]][j]

Here is the Java code which implements the above approach.

Maximum Xor of two bit patterns

Given two numbers A, B, What is the maximum value of A' XOR B', where A', B' are obtained by permuting the binary representations of A, B respectively.

For example assume A = 3, B = 1 and they are represented in 4 bits. A = 0011, B = 0001 in binary. Suppose A' = 1100, B' = 0010, then we get the A' ^ B' = 1110 = 13. So 13 is the answer. For no other values of A’, B’, the XOR will be maximum.

Let us look at another example A = 3, B = 7, again represented using 4 bits. A' = 0011, B' = 1101 and A' ^ B' = 0011 ^ 1101 = 1110 = 14. So 14 is the answer.

This problem was originally appeared on Codechef. The problem has 3 inputs N (number of bits), A, B. How many 1s are possible in the result number?

Since 1^0 = 1 and 0^1 = 1, to get a 1 in the final result, We should have a

  • 1 bit in A, and 0 bit in B or
  • 0 bit in A, and 1 bit in B

So the total number 1s possible in the result is Minimum( 1s in A, 0s in B) + Minimum( 0s in A, 1s in B). The remaining bits are Zeros.

How should we arrange these bits to get the maximum value? All 1s should be pushed to left (Most significant bits). So the result will be of the form 1111…00

Here is the Java code which implements the above approach.

Finding the the number at a given position in even odd array

Given a number N, an array is created by first adding all the odd numbers, and then adding all the even numbers below N, How do we find the number at a given position K?

For example consider N = 10, the array is [1, 3, 5, 7, 9, 2, 4, 6, 8, 10], the number at position K = 3 is 5, similarly at K = 6, the number is 2 etc.

Let us look at a solution for this. First of all, we need not build the entire array for finding out a number at a given position. We can simply find a formula to calculate the number, as the array can be divided into two halves, and both of them are in arithmetic progression.

If the given index is in first half, 2*(pos-1)+1, otherwise 2*(pos-n/2) will give the required answer. Following is the C++ implementation.

This problem was originally appeared in Codeforces.

Maximum increasing sub array

Given an array of numbers, how to find the maximum length of increasing (non-decreasing) continuous sub-sequence?

For example consider the array [7, 9, 1, 3, 5, 8, 2], the maximum length is 4. Similarly for [23, 10, 18, 18, 6], it is 3.

This is a straight forward implementation problem (appeared on Codeforces). Following is an implementation of O(n) algorithm.

Check if an array has a sub-array with given sum

Given an array of numbers and a sum, how to check if there is any sub-array with the given sum.

For example consider an array A = [7, 2, 9, 1, 5], and the sum is 12, then we can find a sub-array [2, 9, 1] which sums up to 12. So the answer is Yes. If we want to check for sum 14, we can not find a sub-array with that sum.

A simple method is to check if a sum can be found for all possible sub-arrays. This solution takes O(n3) time.

A more efficient method is the sliding window method. We maintain two indices, one indicates the beginning of the window, and the other indicates the ending of the window.

While iterating through the elements, we increment the end-index as long as the current sum is less than or equal to the target. If we find the target sum, then we are done. If we exceed the target sum, we deduct the beginning elements from the current sum until it is less than or equal to target sum.

This approach takes O(n) time. Here is the C++ code.

Decreasing string

Given a number K, Find the shortest and smallest string  which has K positions in it, such that the character at that position is alphabetically greater than the character immediately after it. Only the lower case alphabets [a-z] are allowed.

For example consider K = 1

“ba” is the shortest and smallest string possible. There are other possibilities like “ca”, “bad”. But “ca” cannot be the answer because “ba” is alphabetically smaller than “ca”. Similarly “bad” cannot be the answer because it’s length is greater than “ba”.

This problem is from Codechef. If you want to solve it, follow the problem link.

Here is how we can solve the problem. Let us look at some of the answers.

K = 1, “ba”

K = 2, “cba”

K = 3, “dcba”…

If you observe the pattern, this is simply reverse order of alphabets. We can happily reverse the alphabets if K < 26. What happens if K = 26? The pattern repeats, and the repeating pattern should be added in the beginning.

So for K = 26, the answer is “bazyxwvutsrqponmlkjihgfedcba”.

Here is the Python implementation of this algorithm.