Given an array arr[] of size N, the task is to count the number of operations required to make all array elements equal by replacing the largest array element with the second-largest array element, which is strictly smaller than the largest array element.
Examples:
Input: arr[ ] = {1, 1, 2, 2, 3}
Output: 4
Explanation: A total of 4 operations are required to make all array elements equal.
Operation 1: Replace the largest element (= arr[4] = 3) with the next largest( = arr[2] = 2). The array arr[] modifies to {1, 1, 2, 2, 2}.
Operation 2: Replace the largest element (= arr[2] = 2) with the next largest( = arr[0] = 1). The array arr[] modifies to {1, 1, 1, 2, 2}
Operation 3: Replace the largest element (= arr[3] = 2) with the next largest( = arr[0] = 1). The array arr[] modifies to {1, 1, 1, 1, 2}
Operation 4: Replace the largest element (= arr[4] = 2) with the next largest( = arr[0] = 1). The array arr[] modifies to {1, 1, 1, 1, 1}Input: arr[ ] = {1, 1, 1}
Output: 0
Approach: Follow the steps below to solve the problem:
- Initialize a variable, say value_count = 0 and operation_count = 0.
- Sort the array arr[] in ascending order.
- Traverse the array arr[] and check if the current element is greater than the previous element. If found to be true, then increase value_count by 1.
- For each iteration, add value_count in operation_count.
- Finally, print the value of operation_count.
Below is the implementation of the above approach:
C++
// C++ program to Make all array elements// equal by perform certain operation#include <bits/stdc++.h>using namespace std;// Function to count number of operations// required to make all array elements equalint operation(int arr[], int n){ // Initialize the val_count // and operation_count by 0. int val_count = 0, operation_count = 0; // Sort the array in ascending order. sort(arr, arr + n); for (int i = 1; i < n; i++) { // Current element greater // than the previous element if (arr[i - 1] < arr[i]) { // If yes then update the // val_count by 1. val_count++; } // Add the value_count in operation_count. operation_count = operation_count + val_count; } // Return the operation_count return operation_count;}// Driver Codeint main(){ // Given Input int arr[] = { 1, 1, 2, 2, 3 }; int n = sizeof(arr) / sizeof(arr[0]); // Function Call cout << operation(arr, n); return 0;} |
Java
// Java program for the above approachimport java.util.Arrays;import java.io.*;class GFG { // Function to count number of operations // required to make all array elements equal static int operation(int arr[], int n) { // Initialize the val_count // and operation_count by 0. int val_count = 0, operation_count = 0; // Sort the array in ascending order. Arrays.sort(arr); for (int i = 1; i < n; i++) { // Current element greater // than the previous element if (arr[i - 1] < arr[i]) { // If yes then update the // val_count by 1. val_count++; } // Add the value_count in operation_count. operation_count = operation_count + val_count; } // Return the operation_count return operation_count; } // Driver Code public static void main (String[] args) { // Given Input int arr[] = { 1, 1, 2, 2, 3 }; int n = arr.length; // Function Call System.out.println( operation(arr, n)); }}// This code is contributed by Potta Lokesh |
Python3
# Python3 program to Make all array elements# equal by perform certain operation# Function to count number of operations# required to make all array elements equaldef operation(arr, n): # Initialize the val_count # and operation_count by 0. val_count = 0 operation_count = 0 # Sort the array in ascending order. arr.sort() for i in range(1, n): # Current element greater # than the previous element if arr[i-1] < arr[i]: # If yes then update the # val_count by 1. val_count += 1 # Add the value_count in operation_count. operation_count += val_count # Return the operation_count return operation_count# Driver codearr = [1, 1, 2, 2, 3]n = len(arr)print(operation(arr, n))# This code is contributed by Parth Manchanda |
C#
// C# program for the above approachusing System;public class GFG { // Function to count number of operations // required to make all array elements equal static int operation(int []arr, int n) { // Initialize the val_count // and operation_count by 0. int val_count = 0, operation_count = 0; // Sort the array in ascending order. Array.Sort(arr); for (int i = 1; i < n; i++) { // Current element greater // than the previous element if (arr[i - 1] < arr[i]) { // If yes then update the // val_count by 1. val_count++; } // Add the value_count in operation_count. operation_count = operation_count + val_count; } // Return the operation_count return operation_count; } // Driver Code public static void Main(String[] args) { // Given Input int []arr = { 1, 1, 2, 2, 3 }; int n = arr.Length; // Function Call Console.WriteLine( operation(arr, n)); }}// This code is contributed by Amit Katiyar |
Javascript
// Javascript program to Make all array elements// equal by perform certain operation// Function to count number of operations// required to make all array elements equalfunction operation(arr, n) { // Initialize the val_count // and operation_count by 0. let val_count = 0, operation_count = 0; // Sort the array in ascending order. arr.sort(); for (let i = 1; i < n; i++) { // Current element greater // than the previous element if (arr[i - 1] < arr[i]) { // If yes then update the // val_count by 1. val_count++; } // Add the value_count in operation_count. operation_count = operation_count + val_count; } // Return the operation_count return operation_count;}// Driver Code// Given Inputlet arr = [1, 1, 2, 2, 3];let n = arr.length;// Function Calldocument.write(operation(arr, n));// This code is contributed by gfgking. |
Output:
4
Time Complexity: O(NLogN)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
