PROBLEM LINK:Div1, Div2 DIFFICULTY:Easy PREREQUISITES:Sorting PROBLEM:You are given an array with $N$ elements. In one operation you can replace $A[i]$ by $A[i]+A[j]$ where $j \neq i$. Find minimum number of operations required to make each element of array pairwise distinct. EXPLANATION:Lets keep a track on the current maximum of the array. If we add maximum to any element already present in the array, it will give us a new maximum as well as new element that was not present in the array before. We can do this process for all the elements that are repeating. Hence total no. of operation required = $N$  (total unique elements already present in the array). You can prove this using contradiction if you want to. Main problem here reduces to finding total number of unique elements present in the array. This task can be solved using sorting and linear traversal of the array. Time Complexity:$O(N.logN)$ AUTHOR'S AND TESTER'S SOLUTIONS
This question is marked "community wiki".
asked 10 Mar '18, 06:13

It is showing access denied when trying to view setters/testers solution. answered 13 Mar '18, 15:13

hello, I had my solution for this problem up and running in the practice section with various test cases being successful, But still it gave SIGSGEV while submitting..Don't know how to improve..where it was running successfully in other online ides. here is my solution https://www.codechef.com/viewsolution/17767577 I know (I have mistakenly put a line which can lead to WA) , But even after removing that I keep getting that SIGSGEV Error. I don't see any wrong in the algorithm(as it ran successfully under various test cases in various online IDEs)..What modification can be done in the code to avoid the SIGSGEV Error?? answered 13 Mar '18, 21:52
yes , thats why I used the array size 10^9 once but, it is giving TLE @azad123
(13 Mar '18, 23:04)

You are getting error due to this line vs[(a[j])]+=1 as the value of a[j] can be up to 10^9 and the size of vs array is max+100 which is smaller than 10^9. Also you can create maximum array of 10^6 only So you can not solve it by using this method.You need to sort the elements first and then count the number of duplicates. answered 13 Mar '18, 22:49

well this is the thing you can traverse only up to 10^6 in 1 sec. answered 13 Mar '18, 23:08

I solved it using C++
Theorem: The Number of minimum moves = number of extra color i.e. Total colors # of distinct colors. Proof: We can get a new color by adding a repeated color with the highest color. This way its just O(N). link My Solution answered 21 Mar '18, 16:47

simply, we can find the number of unique elements using a set. for those who are using this through array traversal this is definitely going to give NZEC or SIGSEGV as the range is 10^9. check out this solution: https://www.codechef.com/viewsolution/19804820 answered 22 Aug '18, 00:11
