Write an algorithm to return an array such that every number k from 1..n is occurring exactly twice and is k distance apart from its replica

Question

This question was asked in an interview.

For a given integer n >= 3 return an array of size 2n such that every number k from 1 to n is occurring exactly twice and every number and its repetition is separated by a distance equal to the number.

Function signature:

int* buildArray(int n)

For example, for n = 3:

3, 1, 2, 1, 3, 2

Number 2: 1st position 3 and 2nd position 6, so distance 6 - 3 - 1 = 2.
Number 3: First 3 at position 1 and 2nd 3 at position 5, so distance 5 - 1 - 1 = 3.

For n = 4:

4, 1, 3, 1, 2, 4, 3, 2

Answer 1

This is an exact cover problem, which you can solve with Algorithm X. (And it's a nicer, simpler example than Sudoku.) You have the following constraints:

• each number must be used exaclty twice and
• each slot in the array can only be occupied by one number

For your problem with n = 3, you get the following matrix:

     [0] [1] [2] [3] [4] [5]  1   2   3
     --- --- --- --- --- --- --- --- ---
#0    X       X               X
#1        X       X           X
#2            X       X       X
#3                X       X   X

#4    X           X               X
#5        X           X           X
#6            X           X       X

#7    X               X               X
#8        X               X           X          

The columns [x] mean that slot x is used; plain x means that the digit x has been placed. The rows #0 to #3 describe the possible placements of ones, #4 to #6 the placements of twos and #7 and #8 the twi possibilities to place the threes. This will yield the two (mirrored) solutions:

2 3 1 2 1 3     (#2 + #4 + #8)
3 1 2 1 3 2     (#1 + #6 + #7)

Not all n yield solutions, there are no solutions for 5 and 6, for example.

Answer 2

It's a Langford's problem/sequence.

There is a topic about the same problem on SO with implementation already. Langford sequence implementation Haskell or C