CODEWITHSUNDEEP
algorithmsorting
user6464950
user6464950

Reputation:

Sort a given array whose elements range from 1 to n , in which one element is missing and one is repeated

I have to sort this array in O(n) time and O(1) space.

I know how to sort an array in O(n) but that doesn't work with missing and repeated numbers. If I find the repeated and missing numbers first (It can be done in O(n)) and then sort , that seems costly.

static void sort(int[] arr)
{
    for(int i=0;i<arr.length;i++)
    {
        if(i>=arr.length)
            break;
        if(arr[i]-1 == i)
            continue;
        else
        {
        while(arr[i]-1 != i)
        {
            int temp = arr[arr[i]-1];
            arr[arr[i]-1] = arr[i];
            arr[i] = temp;
        }
        }
    }
}

Upvotes: 0

Views: 154

Answers (3)

Can Nguyen
Can Nguyen

Reputation: 1470

void sort() {
  for (int i = 1; i <= N; ++i) {
    while (a[i] != a[a[i]]) {
      std::swap(a[i], a[a[i]]);
    }
  }

  for (int i = 1; i <= N; ++i) {
    if (a[i] == i) continue;
    for (int j = a[i] - 1; j >= i; --j) a[j] = j + 1;
    for (int j = a[i] + 1; j <= i; ++j) a[j] = j - 1;
    break;
  }
}

Explanation: Let's denote m the missing number and d the duplicated number

  • Please note in the while loop, the break condition is a[i] != a[a[i]] which covers both a[i] == i and a[i] is a duplicate.
  • After the first for, every non-duplicate number i is encountered 1-2 time and moved into the i-th position of the array at most 1 time.
  • The first-found number d is moved to d-th position, at most 1 time

  • The second d is moved around at most N-1 times and ends up in m-th position because every other i-th slot is occupied by number i

  • The second outer for locate the first i where a[i] != i. The only i satisfies that is i = m

  • The 2 inner fors handle 2 cases where m < d and m > d respectively

Full implementation at http://ideone.com/VDuLka

Upvotes: 0

gudok
gudok

Reputation: 4179

First, you need to find missing and repeated numbers. You do this by solving following system of equations:

equation

Left sums are computed simultaneously by making one pass over array. Right sums are even simpler -- you may use formulas for arithmetic progression to avoid looping. So, now you have system of two equations with two unknowns: missing number m and repeated number r. Solve it.

Next, you "sort" array by filling it with numbers 1 to n left to right, omitting m and duplicating r. Thus, overall algorithm requires only two passes over array.

Upvotes: 1

rcgldr
rcgldr

Reputation: 28921

After

            int temp = arr[arr[i]-1];

add a check for duplicate in the loop:

            if((temp-1) == i){  // found duplicate
                ...
            } else {
                arr[arr[i]-1] = arr[i];
                arr[i] = temp;
            }

See if you can figure out the rest of the code.

Upvotes: 0

Related Questions