Write a program that takes a sorted integer array, shuffles all the elements in such a way that for every
i there must exist a
j such that, one of the following is satisfied:
a[i] < a[j] < a[i+1] a[i] > a[j] > a[i+1]
j are within the bounds of array.
If there are not many distinct elements, you must show an error.
Input: 1, 2 Output: Error Input: 1, 2, 3, 4, 5, 6, 7 Output: 7, 1, 4, 2, 5, 3, 6 Input: 1, 2, 2, 4, 5, 6, 7 Output: 1, 4, 6, 2, 5, 2, 7 Input: 1, 2, 2, 3 Output: Error Input: 1, 5, 7, 7, 11 Output: Error
There may be more than one possible correctly shuffled arrays. You just have to solve for 1 correct solution.
Input array can have repeated elements, this requirement makes the solution tricky, otherwise a sort and skip would have worked.
Being able to have duplicates in input also makes it different from The Strange Unsorting Machine for Nefarious Purposes . And a correct solution is much trickier than the that.
The output must be of same size as input array and all elements from the input array must exist at some position in the output array.
How to take input: The program must take input either through console input or a simple delimited text file.
How to output: The program must output to the console.
What to output: Program must output both the input and the output array in following format
Input: 1, 2, 3, 4, 5, 6, 7 Output: 7, 1, 4, 2, 5, 3, 6
If input cannot be shuffled as required, the output should look like
Input: 1, 2, 3 Output: Error
Shortest code (byte count) wins.
BONUS 1: Deduct 10 points from your count if your solution can work on unsorted inputs.
BONUS 2: Deduct 20 points from your count if your solution can find more than 1 (not all) solutions for the same input. To qualify for this bonus, your additional solution must not be just a reversed output of the other solution.