-5

I have an array, say

{2, 3, 2, 3, 3}

I can swap exactly 2 items, e.g.

{2, 3, 2, 3, 3} => {3, 3, 2, 2, 3} 
 ^        ^
 swap these

How many different arrays can I produce this way? For the example above, the answer is 7, these arrays are:

{2, 3, 2, 3, 3} // swap 2nd and 4th
{2, 2, 3, 3, 3} // swap 2nd and 3rd
{2, 3, 3, 2, 3} // swap 3rd and 4th
{2, 3, 3, 3, 2} // swap 3rd and 5th 
{3, 2, 2, 3, 3} // swap 1st and 2nd
{3, 3, 2, 2, 3} // swap 1st and 4th
{3, 3, 2, 3, 2} // swap 1st and 5th

If I have {5, 5} array (note, this is degenerated case), the answer is 1: the only possibility is {5, 5} after swapping 5s.

How to start this task? I am thinking about nested for loops, but I was told that I should do this in O(NLog(N)) time.

This is my method signature:

public int process(List<Long> arr) {

}
Dmitry Bychenko
  • 180,369
  • 20
  • 160
  • 215
learner
  • 6,062
  • 14
  • 79
  • 139

1 Answers1

2

You can solve the problem in O(n) time. Let me explain the algorithm, and you'll implement it in Java.

Count each item occurence, organize them in a map. Here we have

  map = {
    {2, 2},  // number 2 appears 2 times
    {3, 3},  // number 3 appears 3 times
  }

If any number appears 2 or more times, start summation from 1 otherwise from 0.

  Here we have number 2 appears 2 times, so we should start from 1

  sum = 1;

Then we loop over array and update both map and sum:

  v = array[i];
  sum += array.length - i - map[v];  
  map[v] -= 1;

Let's have a look what's going on:

  i : v :       sum :            map
  -----------------------------------
  0 : 2 : 1 + 3 = 4 : {{2, 1} {3, 3}}
  1 : 3 : 4 + 1 = 5 : {{2, 1} {3, 2}}
  2 : 2 : 5 + 2 = 7 : {{2, 0} {3, 2}}
  3 : 3 : 7 + 0 = 7 : {{2, 0} {3, 1}}
  4 : 3 : 7 + 0 = 7 : {{2, 0} {3, 0}}

Finally, return the sum.

Edit: Brief logics explanation:

If we have two or more equal items, then we can swap them and have the array unchanged. This is a special solution so we start summing from 1 in this case.

Now let's count all the swaps which change the array. Note, that when swapping we sould not count a swap twice:

 ... a ... b ...
     ^     ^
    swap(a, b) == swap(b, a)

To prevent this double count let operate with swap(a, b) only (b to the right of a). How many swap (array[i], ...) do we have?

 swap(array[i], array[i + 1])
 swap(array[i], array[i + 2])
 ...
 swap(array[i], array[length - 1])

we have length - 1 - i swaps. However, we should subtract the number of items to the right of array[i] which are equal to array[i] (swapping equal items doesn't produce a new array). With a help of map we can easily subtract the required number:

 map[array[i]] -= 1; // array[i] is not to the right of itself
 sum += length - 1 - i - map[array[i]]
Dmitry Bychenko
  • 180,369
  • 20
  • 160
  • 215