Given an array arr[] of size N, the task is to find the minimum number of operations required to make all the array elements equal by following operation:
- Pick any number between 1 to N.
- Choose an element from the array,
- Replace all the consecutive equal elements with the picked number.
Example:
Input: arr[] = {1, 2, 5, 2, 1}, N = 5
Output: 2
Explanation: Following are the operations required to make all the elements in arr[] equal.
{1, 2, 2, 2, 1}, pick 2 and replace it with all consecutive 5s.
{1, 1, 1, 1, 1}, pick 1 and replace it with all consecutive 2s.
Therefore, Number of operations required = 2, which is minimum possible.Input: arr[] = {4, 4, 7, 4, 7, 7, 3, 3}, N = 7
Output: 3
Approach: This problem can be solved by using Dynamic Programming. The idea is to think of the order of vanishing elements within subinterval to the extreme. Within subinterval [l, r] there is the first time when the element at position r will vanish. And, at that point in time, there will be subinterval [i, r] of vanished elements. Those [i, r] were deleted in the fewest steps. Otherwise, we can reduce the number of steps. Also, in the previous step, the element at position r was existing. So, there are two possible cases:
- Segment [i, r-1] was deleted already ⇢ means that a single element is deleted at position r, but this means we can first delete [l, r-1] segment instead, and then delete the single element at position r.
- Segment [i+1, r-1] was deleted already ⇢ means that two elements are deleted at once: at positions r, and i. They have to be same elements.
Remove all consecutive duplicates in the initial array.
Using the above idea, construct a 2D dp array where, dp[l][r] is equal to, number of steps needed to delete all elements within the range [l, r]. Then, the answer is (dp[0][n-1] – 1) ( in 0-based indexing), which is nothing but, deleting whole array minus one step.
- The base case for our dp[][] is dp[i][i] = 1. (It take one step to delete an array of size 1)
- for l < r, dp[l][r] will be initially set to dp[l][r-1] + 1.
- for each element at position i with same value as element at position r, update dp[l][r] if dp[l][i-1] + dp[i, r] is less than current value of dp[l][r].
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the minimum number of// operations required to make all the// array elements equalint minOperations(vector<int> arr, int N){ vector<int> p(N + 1, -1); int j = 0; for (int i = 1; i < N; ++i) { if (arr[i] != arr[j]) { ++j; arr[j] = arr[i]; } } N = j + 1; arr.resize(N); vector<vector<int> > dp(N, vector<int>(N)); vector<int> b(N, -1); for (int j = 0; j < N; ++j) { dp[j][j] = 1; b[j] = p[arr[j]]; p[arr[j]] = j; for (int i = j - 1; i >= 0; --i) { int d = dp[i][j - 1] + 1; for (int k = b[j]; k > i; k = b[k]) { d = min(d, dp[i][k - 1] + dp[k][j]); } if (arr[i] == arr[j]) { d = min(d, dp[i + 1][j]); } dp[i][j] = d; } } // Return the answer return dp[0][N - 1] - 1;}// Driver Codeint main(){ vector<int> arr = { 1, 2, 5, 2, 1 }; int N = arr.size(); cout << minOperations(arr, N); return 0;} |
Java
// Java code for the above approachimport java.util.*;class GFG{ // Function to find the minimum number of // operations required to make all the // array elements equal static int minOperations(int[] arr, int N) { int p[] = new int[N + 1]; Arrays.fill(p, -1); int j = 0; for (int i = 1; i < N; ++i) { if (arr[i] != arr[j]) { ++j; arr[j] = arr[i]; } } N = j + 1; int[][] dp = new int[N][N]; int[] b = new int[N]; Arrays.fill(b, -1); for (j = 0; j < N; ++j) { dp[j][j] = 1; b[j] = p[arr[j]]; p[arr[j]] = j; for (int i = j - 1; i >= 0; --i) { int d = dp[i][j - 1] + 1; for (int k = b[j]; k > i; k = b[k]) { d = Math.min(d, dp[i][k - 1] + dp[k][j]); } if (arr[i] == arr[j]) { d = Math.min(d, dp[i + 1][j]); } dp[i][j] = d; } } // Return the answer return dp[0][N - 1] - 1; } // Driver Code public static void main(String[] args) { int[] arr = { 1, 2, 5, 2, 1 }; int N = arr.length; System.out.println(minOperations(arr, N)); }}// This code is contributed by Potta Lokesh |
Python3
# python program for the above approach# Function to find the minimum number of# operations required to make all the# array elements equaldef minOperations(arr, N): p = [-1 for _ in range(N + 1)] j = 0 for i in range(1, N): if (arr[i] != arr[j]): j += 1 arr[j] = arr[i] N = j + 1 arr = arr[:N] dp = [[0 for _ in range(N)] for _ in range(N)] b = [-1 for _ in range(N)] for j in range(0, N): dp[j][j] = 1 b[j] = p[arr[j]] p[arr[j]] = j for i in range(j-1, -1, -1): d = dp[i][j - 1] + 1 k = b[j] while k > i: d = min(d, dp[i][k - 1] + dp[k][j]) k = b[k] if (arr[i] == arr[j]): d = min(d, dp[i + 1][j]) dp[i][j] = d # Return the answer return dp[0][N - 1] - 1# Driver Codeif __name__ == "__main__": arr = [1, 2, 5, 2, 1] N = len(arr) print(minOperations(arr, N)) # This code is contributed by rakeshsahni |
C#
// C# code for the above approachusing System;using System.Collections;class GFG{ // Function to find the minimum number of // operations required to make all the // array elements equal static int minOperations(int[] arr, int N) { int[] p = new int[N + 1]; Array.Fill(p, -1); int j = 0; for (int i = 1; i < N; ++i) { if (arr[i] != arr[j]) { ++j; arr[j] = arr[i]; } } N = j + 1; int[,] dp = new int[N, N]; int[] b = new int[N]; Array.Fill(b, -1); for (j = 0; j < N; ++j) { dp[j, j] = 1; b[j] = p[arr[j]]; p[arr[j]] = j; for (int i = j - 1; i >= 0; --i) { int d = dp[i, j - 1] + 1; for (int k = b[j]; k > i; k = b[k]) { d = Math.Min(d, dp[i, k - 1] + dp[k, j]); } if (arr[i] == arr[j]) { d = Math.Min(d, dp[i + 1, j]); } dp[i, j] = d; } } // Return the answer return dp[0, N - 1] - 1; } // Driver Code public static void Main() { int[] arr = { 1, 2, 5, 2, 1 }; int N = arr.Length; Console.Write(minOperations(arr, N)); }}// This code is contributed by gfgking |
Javascript
<script>// Javascript program for the above approach// Function to find the minimum number of// operations required to make all the// array elements equalfunction minOperations(arr, N) { let p = new Array(N + 1).fill(-1); let j = 0; for (let i = 1; i < N; ++i) { if (arr[i] != arr[j]) { ++j; arr[j] = arr[i]; } } N = j + 1; arr.slice(0, N); let dp = new Array(N).fill(0).map(() => new Array(N)) let b = new Array(N).fill(-1); for (let j = 0; j < N; ++j) { dp[j][j] = 1; b[j] = p[arr[j]]; p[arr[j]] = j; for (let i = j - 1; i >= 0; --i) { let d = dp[i][j - 1] + 1; for (let k = b[j]; k > i; k = b[k]) { d = Math.min(d, dp[i][k - 1] + dp[k][j]); } if (arr[i] == arr[j]) { d = Math.min(d, dp[i + 1][j]); } dp[i][j] = d; } } // Return the answer return dp[0][N - 1] - 1;}// Driver Codelet arr = [1, 2, 5, 2, 1];let N = arr.length;document.write(minOperations(arr, N));// This code is contributed by gfgking.</script> |
2
Time Complexity: O(N3)
Auxiliary Space: O(N2)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
