Given a binary array arr[] of N integers and an integer P, the task is to find the minimum cost to reach the end of the array from Pth index using jumps of length K. A jump to index i is valid if arr[i] = 1. The array can be modified using the following operations:
- Replace an index having a value 0 to 1. The cost of this operation is X.
- Delete the integer at index P. The cost of this operation is Y.
Example:
Input: arr[] = {0, 0, 0, 1, 1, 0, 0, 1, 1, 1}, P = 6, K = 2, X = 1, Y = 2
Output: 1
Explanation: In 1st operation, replace the value at index 6 to 1. Hence, arr[] = {0, 0, 0, 1, 1, 1, 0, 1, 1, 1}. Initially, the current index = P = 6. Jump from P to P + K => from 6 => 8. Again jump to the next possible index i.e, 8 => 10, which is the end of the array.Input: arr[] = {0, 1, 0, 0, 0, 1, 0}, P = 4, K = 1, X = 2, Y = 1
Output: 4
Approach: The given problem can be solved based on the following observations:
- For a given P, check if indices P, P+K, P+2K… have their value as 1. If not, then replace them with 1 and maintain their count. Hence, the final cost = count * X.
- Upon applying the second operation i times, the starting index will become P+i. Hence the final cost = (i * Y) + (count * X).
Hence, the given problem can be solved by iterating over all possible values of i in the range [1, N-P) and calculating the cost at each step. It can be done by maintaining an array zeroes[], where zeroes[i] stores the frequency of 0’s at indices i, i+K, i+2K…
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 cost to// reach the end of the given arrayint minimumCost(int arr[], int N, int P, int K, int X, int Y){ // Convert P to 0-based indexing P = P - 1; // Vector to store the count of zeros // till the current index vector<int> zeros(N, 0); // Traverse the array and store the // count of zeros in vector for (int i = 0; i < N; i++) { // If element is 0 if (arr[i] == 0) { zeros[i]++; } } // Iterate in the range [N-K-1, 0] // and increment zeros[i] by zeros[i+K] for (int i = N - K - 1; i >= 0; i--) { zeros[i] += zeros[i + K]; } // Variable to store the min cost int cost = INT_MAX; // Loop to calculate the cost for all // values of i in range [P, N] for (int i = P; i < N; i++) { cost = min(cost, ((i - P) * Y) + (zeros[i] * X)); } // Return Answer return cost;}// Driver Codeint main(){ int arr[] = { 0, 1, 0, 0, 0, 1, 0 }; int P = 4; int K = 1; int X = 2; int Y = 1; int N = sizeof(arr) / sizeof(arr[0]); cout << minimumCost(arr, N, P, K, X, Y); return 0;} |
Java
// Java program for the above approachpublic class GFG { // Function to find the minimum cost to// reach the end of the given arraystatic int minimumCost(int arr[], int N, int P, int K, int X, int Y){ // Convert P to 0-based indexing P = P - 1; // Vector to store the count of zeros // till the current index int zeros[] = new int[N] ; // Traverse the array and store the // count of zeros in vector for (int i = 0; i < N; i++) { // If element is 0 if (arr[i] == 0) { zeros[i]++; } } // Iterate in the range [N-K-1, 0] // and increment zeros[i] by zeros[i+K] for (int i = N - K - 1; i >= 0; i--) { zeros[i] += zeros[i + K]; } // Variable to store the min cost int cost = Integer.MAX_VALUE; // Loop to calculate the cost for all // values of i in range [P, N] for (int i = P; i < N; i++) { cost = Math.min(cost, ((i - P) * Y) + (zeros[i] * X)); } // Return Answer return cost;} // Driver Code public static void main (String[] args) { int arr[] = { 0, 1, 0, 0, 0, 1, 0 }; int P = 4; int K = 1; int X = 2; int Y = 1; int N = arr.length; System.out.println(minimumCost(arr, N, P, K, X, Y)); }}// This code is contributed by AnkThon |
Python3
# Python3 program for the above approachimport sys# Function to find the minimum cost to# reach the end of the given arraydef minimumCost(arr, N, P, K, X, Y) : # Convert P to 0-based indexing P = P - 1; # Vector to store the count of zeros # till the current index zeros = [0] * N ; # Traverse the array and store the # count of zeros in vector for i in range(N) : # If element is 0 if (arr[i] == 0) : zeros[i] += 1; # Iterate in the range [N-K-1, 0] # and increment zeros[i] by zeros[i+K] for i in range( N - K - 1, -1, -1) : zeros[i] += zeros[i + K]; # Variable to store the min cost cost = sys.maxsize; # Loop to calculate the cost for all # values of i in range [P, N] for i in range(P, N) : cost = min(cost,((i - P) * Y) + (zeros[i] * X)); # Return Answer return cost;# Driver Codeif __name__ == "__main__" : arr = [ 0, 1, 0, 0, 0, 1, 0 ]; P = 4; K = 1; X = 2; Y = 1; N = len(arr); print(minimumCost(arr, N, P, K, X, Y)); # This code is contributed by AnkThon |
C#
// C# program for the above approachusing System;public class GFG{ // Function to find the minimum cost to // reach the end of the given array static int minimumCost(int[] arr, int N, int P, int K, int X, int Y) { // Convert P to 0-based indexing P = P - 1; // Vector to store the count of zeros // till the current index int[] zeros = new int[N]; // Traverse the array and store the // count of zeros in vector for (int i = 0; i < N; i++) { // If element is 0 if (arr[i] == 0) { zeros[i]++; } } // Iterate in the range [N-K-1, 0] // and increment zeros[i] by zeros[i+K] for (int i = N - K - 1; i >= 0; i--) { zeros[i] += zeros[i + K]; } // Variable to store the min cost int cost = int.MaxValue; // Loop to calculate the cost for all // values of i in range [P, N] for (int i = P; i < N; i++) { cost = Math.Min(cost, ((i - P) * Y) + (zeros[i] * X)); } // Return Answer return cost; } // Driver Code public static void Main() { int[] arr = { 0, 1, 0, 0, 0, 1, 0 }; int P = 4; int K = 1; int X = 2; int Y = 1; int N = arr.Length; Console.WriteLine(minimumCost(arr, N, P, K, X, Y)); }}// This code is contributed by _Saurabh_Jaiswal |
Javascript
<script> // Javascript program for the above approach// Function to find the minimum cost to// reach the end of the given arrayfunction minimumCost(arr, N, P, K, X, Y){ // Convert P to 0-based indexing P = P - 1; // Vector to store the count of zeros // till the current index var zeros = Array(N).fill(0); // Traverse the array and store the // count of zeros in vector for (var i = 0; i < N; i++) { // If element is 0 if (arr[i] == 0) { zeros[i]++; } } // Iterate in the range [N-K-1, 0] // and increment zeros[i] by zeros[i+K] for (var i = N - K - 1; i >= 0; i--) { zeros[i] += zeros[i + K]; } // Variable to store the min cost var cost = 1000000000; // Loop to calculate the cost for all // values of i in range [P, N] for (var i = P; i < N; i++) { cost = Math.min(cost, ((i - P) * Y) + (zeros[i] * X)); } // Return Answer return cost;}// Driver Codevar arr = [ 0, 1, 0, 0, 0, 1, 0 ];var P = 4;var K = 1;var X = 2;var Y = 1;var N = arr.length;document.write(minimumCost(arr, N, P, K, X, Y));// This code is contributed by rutvik_56.</script> |
Output
4
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!
