CODEWITHSUNDEEP
arraysalgorithmintsequencepermutation
user3805652
user3805652

Reputation: 67

Minimum number of moves required to get a permutation of a int of array?

You have a sequence of d[0] , d[1], d[2] , d[3] ,..,d[n]. In each move you are allowed to increase any d[i] by 1 or 2 or 5 i:0 to n .What is the minimum number of moves required to transform the sequence to permutation of [1,2,3,..,n] if it's possible else return -1. 1<=n<=1000

My approach is sort the given array in ascending array than count it by adding 1 or 2 or 5 . But it fails in many cases .Some of my classmates did this in exam using this method but they read question wrong so read question carefully .

e.g. [1,1,3,2,1] than answer is 4 since We can get [1,2,5,4,3 ] by adding 0,1,2,2,2 respectively so answer is 4 .

[1,2,3,4,1] => [1,1,2,3,4] we will get 4 using sorting method [0,1,1,1,1] but answer is 2 since we can add [2+2] in 1 to get [1,2,3,4,5] .

similarly

[1,2,3,1] =>[1,1,2,3] to [1,2,3,4] required 3 transformation but answer is 2 since by adding [1+2] to 1 we can get [1,2,3,4].

Another method can be used as but i don't have any proof for correctness .

Algorithm
    input "n" is number of element , array "a" which contains input element 
    initialize cnt = 0 ;
    initialize boolarray[n] ={0};
    1. for i=0...n  boolarray[a[i]]=1;
    2. put all  element in sorted order whose boolarray[a[i]]=0 for i=0...n
    3. Now make boolarray[a[i]]=1; for i=0..n and count
      how many additions are required  .
    4. return count ;

According to me this question will be result in 0 or more always since any number can be produced using 1 , 2 and 5 except this case when any d[i] i=0..n is greater than number of Inputs . 

How to solve this correctly ?

Any answer and suggestions are welcome .

Upvotes: 2

Views: 1452

Answers (2)

Vikram Bhat
Vikram Bhat

Reputation: 6246

Your problem can be converted in weighted bipartite matching problem :-

  1. first part p1 of graph are the current array numbers as nodes.
  2. second part p2 of graph are numbers 1 to n.
  3. There is edge between node of p1 to node p2 if we can add 1,2,5 to it to make node in p2.
  4. weighted bipartite matching can be solved using the hungarian algorithm

Edit :-

If you are evaluating minimum number of move then you can use unweighted bipartite matching . You can use hopcroft-karp algorithm which runs in O(n^1.5) in your case as number of edges E = O(n) in the graph.

Upvotes: 1

Absurd-Mind
Absurd-Mind

Reputation: 7994

Create an array count which contains the count of how often we have a specific number in our base array

input    1 1 3 2 1
count    3 1 1 0 0

now walk over this array and calculate the steps

sum = 0

for i: 1..n
    while count[i] > 1                   // as long as we have spare numbers

        missing = -1                     // find the biggest empty spot which is bigger than the number at i
        for x: n..i+1                    // look for the biggest missing
            if count[x] > 0 continue     // this one is not missing
            missing = x
            break;

        if missing == -1 return -1       // no empty spot found

        sum += calcCost(i, missing)
        count[i]--
        count[missing]++

 return sum

calcCost must be greedy

Upvotes: 0

Related Questions