PROBLEM LINK:
Author: Shivangi Gupta
Tester: Triveni Mahatha
Editorialist: Adarsh Kumar
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)