Arrays

# Minimize cost to reach the end of given Binary Array using jump of K length after performing given operations

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:Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.  To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.In case you wish to attend live classes with experts, please refer DSA Live Classes for Working Professionals and Competitive Programming Live for Students.Input: arr[] = {0, 0, 0, 1, 1, 0, 0, 1, 1, 1}, P = 6, K = 2, X = 1, Y = 2Output: 1Explanation: 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 = 1Output: 4Approach: 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++#include using namespace std;  int minimumCost(int arr[], int N,                int P, int K, int X,                int Y){        P = P – 1;              vector zeros(N, 0);              for (int i = 0; i < N; i++) {                  if (arr[i] == 0) {            zeros[i]++;        }    }            for (int i = N - K - 1; i >= 0; i–) {        zeros[i] += zeros[i + K];    }          int cost = INT_MAX;              for (int i = P; i < N; i++) {        cost = min(cost,                   ((i - P) * Y)                       + (zeros[i] * X));    }          return cost;}  int 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