Минимизируйте операции, чтобы сделать все элементы заданных подмассивов различными

Дан arr[] положительных целых чисел и массивы start[] и end[] длины L , которые содержат начальный и конечный индексы L числа непересекающихся подмассивов в качестве start[i] и end[i] для все (1 ≤ i ≤ L) . Операция определяется следующим образом:

• Выберите упорядоченную непрерывную или непрерывную часть подмассива, а затем добавьте целое число, скажем, A ко всем элементам выбранной части.

Затем задача состоит в том, чтобы вывести минимальное количество заданных операций, необходимых для того, чтобы сделать все элементы всех заданных непересекающихся подмассивов различными.

Примечание. Если один и тот же элемент содержится более чем в одном подмассиве, это не имеет значения. Просто каждый подмассив должен содержать в себе отдельные элементы.

Примеры:

Input: arr[] = {2, 2, 1, 2, 3}, start[] = {1, 3}, end[] = {2, 5}               
Output: 1
Explanation: First sub-array : [start[1], end[1]] = {2, 2}.
Second sub-array : [start[3], end[5]] = {1, 2, 3}.
In First sub-array chose sub-sequence from index 1 to 1 as {2} and plus any integer random integer let say 1.Then, First sub-array = {3, 2}. Now, both sub-array contains distinct elements in itself. Total number of required operation are 1.

Input: arr[] = {1, 2, 3, 3, 4, 5}, start[] = {1, 4}, end[] = {3, 6}
Output: 0
Explanation: It can be verified that sub-arrays {1, 2, 3} and {3, 4, 5} both are distinct in itself. Therefore, total number of required operations are 0.

Подход: реализуйте приведенную ниже идею, чтобы решить проблему.

Making all the elements distinct in a sub-array by given operation only depends upon the maximum frequency in an sub-array, If we converted high frequent element in distinct form then rest of the frequencies less than max frequency can be make distinct simultaneously. For more clarity see the  concept of approach.Obtain the maximum frequency in each sub-array and apply the algorithm provided below.

Концепция подхода:

Suppose our sub-array A[] is = {2, 2, 2, 2, 2, 2, 2, 2, 2, 2}. Highest frequency is 10 here.

First operation: Chose ordered sub-sequence from index 6 to 10 and add any integer let say 1 to all elements in sub-sequence. Then,   A[] = {2, 2, 2, 2, 2, 3, 3, 3, 3, 3}. Highest frequency is 5 till here. 

Second Operation: Chose ordered sub-sequence from index 3 to 5 and 8 to 10 add any integer let say 2 to all elements in sub-sequence. Then,  A[] = {2, 2, 4, 4, 4, 3, 3, 5, 5, 5}. Highest frequency is 3 till here.

Third Operation: Chose ordered sub-sequence from index 4 to 5 and 9 to 10 add any integer let say 3 to all elements in sub-sequence. Then,  A[] = {2, 2, 4, 7, 7, 3, 3, 5, 8, 8}

Fourth Operation: Chose ordered sub-sequence of indices : {1, 4, 6, 9}  add any integer let say 10 to all elements in sub-sequence. Then,  A[] = {12, 2, 4, 17, 7, 13, 3, 5, 18, 8}

Thus, Only four operation are required to convert into distinct elements. At second operation we can see the both 2 and 3 element has 5 frequency and we successfully convert them into distinct elements. This gives us idea that If we try to make max frequent element distinct, Then rest of the elements having frequency less than or equal to max frequency can be converted into distinct simultaneously.    

In above example, It can be clearly seen that, At each operation we are converting the exactly half of the elements, If value of max_frequency is even at that current operation otherwise we are converting (max_frequency+1)/2 elements as well as we are reducing the value of max_frequency in the same manner.Thus we can conclude the below provided algorithm to solve the problem.

Алгоритм решения задачи:

      1. Create a variable let’s say min_operations to store total number of minimum operations required for all              sub-arrays.

      2. For Each given sub-array follow the steps below:

•  Count frequency of each element and store them in Hash-Map.
• Traverse the Hash-Map to obtain maximum frequency in a variable let’s say max_frequency.
• Create and initialize counter variable to zero.
• Apply the below algorithm for obtaining minimum number of operations required.   

            while(max_frequency > 1)
              {
                      if (isEven(max_frequency))
                       {
                             max_frequency/=2;
                        }
                      else
                       {
                             max_frequency = (max_frequency+1)/2;
                       }
                      counter++;
             }

• On completing the loop add value of counter variable in min_operations.

      3. After apply above algorithm on each given sub-array print the value of min_operations.  

Ниже приведен код для реализации подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(N)