Given an array [a1b2c3d4] convert to [abcd1234]

Question

Constraints :

1. O(1) space
2. O(n) Time

It is not a homework question just a interesting question I came across.

Here are some solutions I could think of but nothing that does it in given constraints.

Method 1

*With O(n) memory *

• Divide the array in two parts recursively. ( keep dividing till the size <=2 for each sub problem )
• Sort each sub problem with array first and numbers at end.
• Merge the sub problem arrays

Method 2

In O(n log n) time

• Sort the array based Lexicographical order it becomes 1234abcd
• Reverse both halves of array 4321dcba
• Reverse the whole string abcd1234

Method 3

If range of numbers was defined

Also if the case was that numbers are in a specific range then I can initialize a int say track= 0; And set the appropriate bit when I come across a number in array eg (1 << a[2] ) . 1. Swap alphabets to first half of array 2. Mark numbers in track variable 3. later use track to fill in second half of array.

Method 4 We can use Method 3 with HashMap if we want to remove the constraint of range of integers but then it will need more memory.

Cannot think of a better way to solve the generic problem in O(1) time and O(n) space.

Generic Problem here refers to:

Given a sequence x1y1x2y2x3y3....xnyn where x1 , x2 are alphabets x1 < x2 <.... < xn and y1y2...yn are integers . y1 < y2 <.... < yn Arrange the output as x1x2...xny1y2...yn

Any suggestions ?

Answer 1

What is n? Assuming that n is the size of the input:

This is called the convolution of a list. In essence, you have to convert a list of pairs (a,1),(b,2),(c,3),(d,4) to a pair of lists (a,b,c,d),(1,2,3,4). It's the same operation as the transpose of a matrix.

Anyway, you have to think of the structure as a k-dimensional array, where k = lg n. The convolution of the array is what you get when you "move" the value at an index i to index i bitwise rotated. In this case, we want to rotate the indices rightward 1 bit. This means that the convolution is a permutation with a maximum cycle length of k. The trick is then selecting one index from each cycle – this will always include 0 and n-1.

EDIT: Actually, what you probably want is to decompose the permutation into a product of transpositions. Then, all you need to do is swaps.

Answer 2

Solution:

1. First (index 0) and last (index n-1) do not move.
2. Total number of moves is (n - 2)

3. Even number elements in the source are alphabets. They move into the first half.

   target = j/2 // n is even

4. Odd number elements in the source are numbers, and they move into the second half.

   target = n/2 + floor(j/2)

5. Starting from 1th element, move that to its target location.

6. Move what you find in the target location to its destination and so on until a loop is formed. Note 1: Sometimes, the loop does not include all the elements in the list, so, continue with j + 2 Note 2: Sometimes, at the end of one loop, the desired solution will be achieved, but if we continue, the array will get scrambled again. To fix this, count the number of movements that happened, and cut when it reached n - 2.

You can try running the code, clone and edit here Online Java Compiler IDE

---

int maxShifts = n - 2; // This is required to fix going around and messing up.
int shifts = 0;

for (int i = 1; i < n && shifts < maxShifts; i+=2) {
  int source = i;
  char itemToMove = array[source];
  do {
    int target;
    if (source % 2 == 0) {
      target = source / 2; // Even index is an alphabet
    } else {
      target = n/2 + source/2; // Odd index is a digit, that goes in the second half
    }
    char tmp = array[target];
    array[target] = itemToMove;
    itemToMove = tmp;

    shifts++;
    source = target;

  } while (i != source /*&& shifts < maxShifts*/); // Full cycle reached

}

Answer 3

The cycle leader algorithm mentioned by @coder works. Just make sure to split the array into sizes of (3^n + 1). Apply cycle leader algorithm and then merge these.

Answer 4

Here is my algorithm in O(n).

void cycle_leader(int *arr, int n) {

for (int i = 1; i < n / 2; i+= 2)
{
    int j = i;
    int save;
    int tmp = arr[i];

    do{
        if (j & 1) //odd index element
            j = n / 2 + j / 2;
        else
            j = j / 2;

        save = arr[j];
        arr[j] = tmp;
        tmp = save;
    } while(j != i);
}

}