PanPey's blog

By PanPey, history, 5 weeks ago, In English

Given a positive integer N and an array A of size N such that 1 <= Ai <= N. Our aim is to find whether it can be made permutable. i.e each number from 1 to N appears in A exactly once. We perform an operation to do so. In an operation, we can choose any integer and increase its value. Find the minimum number of changes to make the array permutable and print it. If the array is already permutable print 0, -1 if it's not possible.

Consider 3 test cases. First-line contains N. Next line contains an array of size N.

Sample Input
 3 
 4
 1 3 3 4
 5
 1 2 3 5 4
 5
 2 3 2 1 3

Sample Output
 -1
 0
 2 
 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Check if there exists i for every 1 <= i <= n in the array. If it is present then continue, else you will have to make this i using the previous number whose frequency is more than 1. It is pretty intuitive why this will be the optimal solution.

»
5 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

not sure though....1st sort the array...And then make last element n,previous element n-1,....maybe this will need minimum operation....but if you find that sorted array[i]>i (1 based indexing) you will print -1..

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes that would lead to minimum number of operations. Actually any sequence of moves with numbers having frequency greater than 1 will lead to minimum number of moves because the operation is only increasing it by 1.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

These noobies can't even solve basic questions

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I said it before, and I'll say it again. You're not even a noobie, you're unrated. Get a rating before you try and push people down.