Interesting problem, multiple solutions

I came across a rather interesting problem: “Find a permutation of numbers 1 through N such that average of any two numbers in the permutation does not occur between them”. I found this problem particularly interesting because it lends itself to several different solutions.

Note that if the average is not an integer, then it clearly cannot occur between two numbers in the permutation. Let’s make the problem concrete with a few examples:

For N = 3, [1,3,2], [2,1,3], [2,3,1], [3,1,2] are all solution permutations, but [1,2,3] is not because 2 occurs between 1 and 3.

For N = 4, [1,3,2,4] is a solution permutation but [1,4,2,3] is not because 2 occurs between 1 and 3.

So how do we solve this problem? Let’s first look at a failed attempt before we move on to the solution.

Insight: If average of every two numbers always occurs before those two numbers themselves in the permutation, then such a permutation would be a solution to the problem.

This insight might lead us to this conclusion: If we build a balanced binary search tree over numbers 1 through N and print its pre-order traversal, it would be a solution to the problem because every middle number (potentially an average) would appear before smaller and larger numbers (which could potentially have that middle number as average) than it in the permutation.

Another insight is that since the numbers are already sorted, we don’t have to actually create a balanced BST to print its pre-order traversal. We can follow a simple divide-and-conquer approach: print the middle element and then recurse, first on the left half and then on the right half.

Solution permutation with BST pre-order traversal

Solution permutation with BST pre-order traversal

We could implement this approach as follows:

Time complexity: O(N)
Space complexity: O(log N)
– stack space

However, this solution is wrong. For each subtree in the balanced BST, we are printing root before any other number in its subtree. The assumption here is that only those numbers which occur in the subtree could potentially have an average equal to the root. This assumption is wrong because a number much smaller than the root of a subtree and a number much greater than it (both not lying in its subtree) could have an average equal to it. For example, the permutation generated by this approach for N = 10 has 7 between 4 and 10.

Let’s look at another approach.

Key Insight: If we separate even and odd numbers, then they will have no interaction w.r.t. the average because their average (average of one even and one odd number) wouldn’t be an integer. We can apply this approach recursively if we consider numbers as being at even and odd positions instead of the numbers themselves being even and odd. Thus we are able to divide the problem into two independent subproblems.

Solution permutation with divide and conquer

Solution permutation with divide and conquer

It is not too difficult to prove the correctness of this approach. Let’s move on to how it can be implemented.

Naive approach:

  1. Store numbers 1 through N in an array
  2. At each level, shuffle the numbers in the subarray such that all numbers at odd positions lie before the numbers at even positions
  3. If the subarray contains only 1 number, print it otherwise go to step 4
  4. Recurse, first on the left half (numbers originally at odd positions) and then on the right half (numbers originally at even positions)

Time Complexity: O(N log N)
Space Complexity: O(N)

More clever approach:

The bitwise representation of each number can tell us whether a number would be at an even position or an odd position at a certain level of recursion. For example, if the least significant bit is 1, the number lies at odd position at the first level of recursion. If the second least significant bit is 0, the number would lie at even position at the second level of recursion and so on. We can use this information to directly find out the position of numbers in the solution permutation.

If we reverse bits of each number and sort them in descending order, all numbers with 1 as the least significant bit will appear before all numbers with 0 as the least significant bit. Similarly, all numbers with 11 as the last two bits will appear before all numbers with 10 as the last two bits and so on.

This gives us the following approach:

  1. Reverse bits of all numbers
  2. Sort them
  3. Reverse bits and print numbers in order

One observation here is that there is no need to actually reverse the bits of a number to find its final position in the permutation. The sort function can take a comparator that defines this order.

Time Complexity: O(N log N)
Space Complexity: O(N)

Since there are only 32 bits in an integer and each bit takes values only 0 and 1, separating numbers with bit value 1 from those with bit value 0, for a single bit position, can be done in linear time. We can repeat this for each of 32 bits, to get a theoretical runtime of O(N). However, for all practical purposes (N < 1B), it will probably be slower than general sorting.

Optimal approach:

If we look closely at the divide-and-conquer approach of separating even and odd numbers, we begin to see a pattern in the numbers belonging to each subarray.

Solution permutation with a generative pattern

Solution permutation with a generative pattern

Here, assume that n can take all possible values from natural numbers such that the expressions have values in [1,N].

Time Complexity: O(N)
Space Complexity: O(log N)
– stack space

A similar generative pattern exists for the approach with bits and sorting, wherein we first recursively create all numbers with least significant bit 1 and then with 0. This approach would also have time complexity O(N) and space complexity O(log N).

6 thoughts on “Interesting problem, multiple solutions

  1. HI Kartik. Can you please write a post on how to calculate the time complexity .Its been a big confusion for me to understand O(N) kind of representations

    • Then we recurse. Once we’ve separated even and odd numbers, we are sure that there’s no interaction between the two halves. Then, we recurse on the two halves separating out numbers occurring at even and odd positions. Please look at the image with the second approach for clarification.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s