Select Page

Minimize operations to make all the elements of given Subarrays distinct

Kashish Kumar
Published: October 22, 2022

Given an arr[] of positive integers and start[] and end[] arrays of length L, Which contains the start and end indexes of L number of non-intersecting sub-arrays as a start[i] and end[i]  for all (1 ≤ i ≤ L). An operation is defined as below: 

  • Select an ordered continuous or non – continuous part of the sub-array and then add an integer let’s say A to all of the elements of the chosen part.

Then, the task is to output the minimum number of given operations required to make all the elements of all given non – intersecting sub-arrays distinct.

Note: If more than one sub-arrays contains the same element, It doesn’t matter. Just each sub-array should contain distinct elements in itself.

Examples:

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.

Approach: Implement the idea below to solve the problem

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.

Concept of approach:

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.

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.  

Below is the code to implement the approach:

Java

  

import java.io.*;

import java.lang.*;

import java.util.*;

  

class GFG {

    

    public static void main(String args[])

    {

  

        

        int[] arr = { 2, 2, 2, 2, 2, 3, 3, 3, 3, 3 };

  

        

        

        int[] start = { 1, 6 };

  

        

        

        int[] end = { 5, 10 };

  

        

        

        int min_operations = 0;

  

        

        

        for (int i = 0; i < start.length; i++) {

  

            

            int start_index = start[i];

  

            

            int end_index = end[i];

  

            

            

            HashMap<Integer, Integer> map = new HashMap<>();

  

            

            

            for (int j = start_index - 1; j < end_index;

                 j++) {

  

                

                

                map.put(arr[j], map.get(arr[j]) == null

                                    ? 1

                                    : map.get(arr[j]) + 1);

            }

  

            

            

            int max_frequency = 0;

  

            

            for (Map.Entry<Integer, Integer> set :

                 map.entrySet()) {

  

                

                

                max_frequency

                    = set.getValue() > max_frequency

                          ? set.getValue()

                          : max_frequency;

            }

  

            

            

            while (max_frequency > 1) {

  

                

                max_frequency

                    = max_frequency % 2 == 0

                          ? max_frequency / 2

                          : (max_frequency + 1) / 2;

  

                

                

                min_operations++;

            }

        }

  

        

        

        System.out.println(min_operations);

    }

}

Time Complexity: O(N)
Auxiliary Space: O(N) 

Source: www.geeksforgeeks.org