Given two integer arrays arr[] and cost[] of size N, the task is to make all adjacent elements distinct at minimum cost. cost[i] denotes the cost to increment ith element by 1.
Examples:
Input: arr[] = {2, 2, 3}, cost[] = {4, 1, 5}
Output: 2
Explanation:
The second element has minimum increment cost. Hence, increase the cost of the second element twice.
Therefore the resultant array: {2, 4, 3}
Input: arr[] = {1, 2, 3}, cost[] = {7, 8, 3}
Output: 0
Approach:
- We can observe that there an element might need to be increased maximum twice.
- This problem can be solved using Dynamic Programming.
- Create a DP-table dp[][], where rows represent the elements, and columns represent the increment.
- dp[i][j] is the minimum cost required to make ith element distinct from its adjacent elements using j increments.
- The value of dp[i][j] can be calculated as:
dp[i][j] = j * cost[i] + (minimum from previous element if both elements are different)
Below is the implementation of the above approach
C++
// C++ program to find the// minimum cost required to make// all adjacent elements distinct#include <bits/stdc++.h>using namespace std;// Function that prints minimum cost requiredvoid minimumCost(int arr[], int cost[], int N){ // Dp-table vector<vector<int> > dp(N, vector<int>(3)); // Base case // Not increasing the first element dp[0][0] = 0; // Increasing the first element by 1 dp[0][1] = cost[0]; // Increasing the first element by 2 dp[0][2] = cost[0] * 2; for (int i = 1; i < N; i++) { for (int j = 0; j < 3; j++) { int minimum = 1e6; // Condition if current element // is not equal to previous // non-increased element if (j + arr[i] != arr[i - 1]) minimum = min(minimum, dp[i - 1][0]); // Condition if current element // is not equal to previous element // after being increased by 1 if (j + arr[i] != arr[i - 1] + 1) minimum = min(minimum, dp[i - 1][1]); // Condition if current element // is not equal to previous element // after being increased by 2 if (j + arr[i] != arr[i - 1] + 2) minimum = min(minimum, dp[i - 1][2]); // Take the minimum from all cases dp[i][j] = j * cost[i] + minimum; } } int ans = 1e6; // Finding the minimum cost for (int i = 0; i < 3; i++) ans = min(ans, dp[N - 1][i]); // Printing the minimum cost // required to make all adjacent // elements distinct cout << ans << "\n";}// Driver Codeint main(){ int arr[] = { 1, 1, 2, 2, 3, 4 }; int cost[] = { 3, 2, 5, 4, 2, 1 }; int N = sizeof(arr) / sizeof(arr[0]); minimumCost(arr, cost, N); return 0;} |
Java
// Java program to find the minimum // cost required to make all // adjacent elements distinctimport java.util.*;class GFG{// Function that prints minimum cost requiredstatic void minimumCost(int arr[], int cost[], int N){ // Dp-table int [][]dp = new int[N][3]; // Base case // Not increasing the first element dp[0][0] = 0; // Increasing the first element by 1 dp[0][1] = cost[0]; // Increasing the first element by 2 dp[0][2] = cost[0] * 2; for(int i = 1; i < N; i++) { for(int j = 0; j < 3; j++) { int minimum = (int) 1e6; // Condition if current element // is not equal to previous // non-increased element if (j + arr[i] != arr[i - 1]) minimum = Math.min(minimum, dp[i - 1][0]); // Condition if current element // is not equal to previous element // after being increased by 1 if (j + arr[i] != arr[i - 1] + 1) minimum = Math.min(minimum, dp[i - 1][1]); // Condition if current element // is not equal to previous element // after being increased by 2 if (j + arr[i] != arr[i - 1] + 2) minimum = Math.min(minimum, dp[i - 1][2]); // Take the minimum from all cases dp[i][j] = j * cost[i] + minimum; } } int ans = (int) 1e6; // Finding the minimum cost for(int i = 0; i < 3; i++) ans = Math.min(ans, dp[N - 1][i]); // Printing the minimum cost // required to make all adjacent // elements distinct System.out.print(ans + "\n");}// Driver Codepublic static void main(String[] args){ int arr[] = { 1, 1, 2, 2, 3, 4 }; int cost[] = { 3, 2, 5, 4, 2, 1 }; int N = arr.length; minimumCost(arr, cost, N);}}// This code is contributed by 29AjayKumar |
Python3
# Python3 program to find the# minimum cost required to make# all adjacent elements distinct# Function that prints minimum cost requireddef minimumCost(arr, cost, N): # Dp-table dp = [[0 for i in range(3)] for i in range(N)] # Base case # Not increasing the first element dp[0][0] = 0 # Increasing the first element by 1 dp[0][1] = cost[0] # Increasing the first element by 2 dp[0][2] = cost[0] * 2 for i in range(1, N): for j in range(3): minimum = 1e6 # Condition if current element # is not equal to previous # non-increased element if (j + arr[i] != arr[i - 1]): minimum = min(minimum, dp[i - 1][0]) # Condition if current element # is not equal to previous element # after being increased by 1 if (j + arr[i] != arr[i - 1] + 1): minimum = min(minimum, dp[i - 1][1]) # Condition if current element # is not equal to previous element # after being increased by 2 if (j + arr[i] != arr[i - 1] + 2): minimum = min(minimum, dp[i - 1][2]) # Take the minimum from all cases dp[i][j] = j * cost[i] + minimum ans = 1e6 # Finding the minimum cost for i in range(3): ans = min(ans, dp[N - 1][i]) # Printing the minimum cost # required to make all adjacent # elements distinct print(ans)# Driver Codeif __name__ == '__main__': arr = [ 1, 1, 2, 2, 3, 4 ] cost = [ 3, 2, 5, 4, 2, 1 ] N = len(arr) minimumCost(arr, cost, N)# This code is contributed by mohit kumar 29 |
C#
// C# program to find the minimum // cost required to make all // adjacent elements distinctusing System;class GFG{// Function that prints minimum cost requiredstatic void minimumCost(int []arr, int []cost, int N){ // Dp-table int [,]dp = new int[N, 3]; // Base case // Not increasing the first element dp[0, 0] = 0; // Increasing the first element by 1 dp[0, 1] = cost[0]; // Increasing the first element by 2 dp[0, 2] = cost[0] * 2; for(int i = 1; i < N; i++) { for(int j = 0; j < 3; j++) { int minimum = (int) 1e6; // Condition if current element // is not equal to previous // non-increased element if (j + arr[i] != arr[i - 1]) minimum = Math.Min(minimum, dp[i - 1, 0]); // Condition if current element // is not equal to previous element // after being increased by 1 if (j + arr[i] != arr[i - 1] + 1) minimum = Math.Min(minimum, dp[i - 1, 1]); // Condition if current element // is not equal to previous element // after being increased by 2 if (j + arr[i] != arr[i - 1] + 2) minimum = Math.Min(minimum, dp[i - 1, 2]); // Take the minimum from all cases dp[i, j] = j * cost[i] + minimum; } } int ans = (int) 1e6; // Finding the minimum cost for(int i = 0; i < 3; i++) ans = Math.Min(ans, dp[N - 1, i]); // Printing the minimum cost // required to make all adjacent // elements distinct Console.Write(ans + "\n");}// Driver Codepublic static void Main(String[] args){ int []arr = { 1, 1, 2, 2, 3, 4 }; int []cost = { 3, 2, 5, 4, 2, 1 }; int N = arr.Length; minimumCost(arr, cost, N);}}// This code is contributed by 29AjayKumar |
Javascript
<script>// Javascript program to find the minimum // cost required to make all // adjacent elements distinct // Function that prints minimum cost required function minimumCost(arr , cost , N) { // Dp-table var dp = Array(N).fill().map(()=>Array(3).fill(0)); // Base case // Not increasing the first element dp[0][0] = 0; // Increasing the first element by 1 dp[0][1] = cost[0]; // Increasing the first element by 2 dp[0][2] = cost[0] * 2; for (i = 1; i < N; i++) { for (j = 0; j < 3; j++) { var minimum = parseInt( 1e6); // Condition if current element // is not equal to previous // non-increased element if (j + arr[i] != arr[i - 1]) minimum = Math.min(minimum, dp[i - 1][0]); // Condition if current element // is not equal to previous element // after being increased by 1 if (j + arr[i] != arr[i - 1] + 1) minimum = Math.min(minimum, dp[i - 1][1]); // Condition if current element // is not equal to previous element // after being increased by 2 if (j + arr[i] != arr[i - 1] + 2) minimum = Math.min(minimum, dp[i - 1][2]); // Take the minimum from all cases dp[i][j] = j * cost[i] + minimum; } } var ans = parseInt( 1e6); // Finding the minimum cost for (i = 0; i < 3; i++) ans = Math.min(ans, dp[N - 1][i]); // Printing the minimum cost // required to make all adjacent // elements distinct document.write(ans + "\n"); } // Driver Code var arr = [ 1, 1, 2, 2, 3, 4 ]; var cost = [ 3, 2, 5, 4, 2, 1 ]; var N = arr.length; minimumCost(arr, cost, N);// This code contributed by gauravrajput1 </script> |
Output:
7
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
