Given an array A of size N, having each element either 0 or 1 and an integer K. Find the minimum number of elements that need to be flipped, such that no sub-array of size greater than or equal to K has an arithmetic mean of 1.
Examples:
Input: N = 5, A = {1, 1, 1, 1, 1}, K = 5
Output: 1
Explanation: Initially, mean of only sub-array of size 5 is (1+1+1+1+1)/5 = 1. So, flip the first element (i.e. make it 0). The array now becomes {0, 1, 1, 1, 1}, whose mean is less than 1. So, we needed just 1 flip to satisfy the required condition.
Note that {1, 1, 1, 1, 0} also satisfies required condition. Other arrays are also possible.Input: N = 4, A = {1, 1, 0, 1}, K = 2
Output: 1
Explanation: flip the first 1 (i.e. element at 0 index), to that resultant array becomes {0, 1, 0, 1} in which no sub-array of size 2 of more has a mean 1.
Note that {1, 0, 0, 1} is also a possible array satisfying required condition.
Approach: This problem can be easily solved by using the Greedy technique.
The observation is that a binary array of size K has an arithmetic mean equal to 1 only if all the K elements in it are equal to 1. Also, if all of the sub-arrays of size K have meant less than 1, then all sub-arrays of size greater than K would also have meant less than 1. So, the following approach can be used to solve the problem-
- Start traversing the given array.
- maintain the current count of consecutive ones till the current index in a variable, say “count”.
- If the current element is 1, we increment the count by 1, else we make it 0, as the consecutive 1s ending on ith index becomes 0.
- If the count becomes equal to K, that means there are K consecutive 1s ending on the current index, so we increment the answer by 1 (that implies the current index would be made 0 )and again make the count variable 0.
Below is the implementation of the above approach:
C++
// C++ program to find Minimum flips to// Make mean of all k size// Sub-arrays less than 1#include <bits/stdc++.h>using namespace std;// Function to calculate// Minimum flips to make// Mean of all k size// Subarrays less than 1int minimumFlips(int N, int A[], int K){ // Initializing answer by 0 // That stores the number of flips int answer = 0; // Initializing count variable by 0 // That stores the number of consecutive 1s int count = 0; // iterating through the array for (int i = 0; i < N; i++) { if (A[i] == 1) { // If current element is 1, // We increment count by 1 count++; // if count of consecutive 1s // Reaches k, we increment the answer // as the mean of the subarray from // i-k to ith element becomes 1 if (count == K) { answer++; count = 0; } } // else if current element is // 0, we make count 0 else { count = 0; } } // returning the required answer return answer;}// Driver Codeint main(){ int N = 5, K = 5; int A[] = { 1, 1, 1, 1, 1 }; int minimum_flips = minimumFlips(N, A, K); cout << minimum_flips;} |
Java
// Java program to find Minimum flips to// Make mean of all k size// Sub-arrays less than 1import java.io.*;class GFG { // Function to calculate // Minimum flips to make // Mean of all k size // Subarrays less than 1 static int minimumFlips(int N, int A[], int K) { // Initializing answer by 0 // That stores the number of flips int answer = 0; // Initializing count variable by 0 // That stores the number of consecutive 1s int count = 0; // iterating through the array for (int i = 0; i < N; i++) { if (A[i] == 1) { // If current element is 1, // We increment count by 1 count++; // if count of consecutive 1s // Reaches k, we increment the answer // as the mean of the subarray from // i-k to ith element becomes 1 if (count == K) { answer++; count = 0; } } // else if current element is // 0, we make count 0 else { count = 0; } } // returning the required answer return answer; } // Driver Code public static void main (String[] args) { int N = 5, K = 5; int A[] = { 1, 1, 1, 1, 1 }; int minimum_flips = minimumFlips(N, A, K); System.out.println( minimum_flips); }}// This code is contributed by hrithikgarg03188. |
Python
# Python program to find Minimum flips to# Make mean of all k size# Sub-arrays less than 1# Function to calculate# Minimum flips to make# Mean of all k size# Subarrays less than 1def minimumFlips(N, A, K): # Initializing answer by 0 # That stores the number of flips answer = 0 # Initializing count variable by 0 # That stores the number of consecutive 1s count = 0 # iterating through the array for i in range(0, N): if (A[i] == 1): # If current element is 1, # We increment count by 1 count += 1 # if count of consecutive 1s # Reaches k, we increment the answer # as the mean of the subarray from # i-k to ith element becomes 1 if (count == K): answer += 1 count = 0 # else if current element is # 0, we make count 0 else: count = 0 # returning the required answer return answer# Driver CodeN = 5K = 5A = [ 1, 1, 1, 1, 1 ]minimum_flips = minimumFlips(N, A, K)print(minimum_flips)# This code is contributed by Samim Hossain Mondal. |
C#
// C# program to find Minimum flips to// Make mean of all k size// Sub-arrays less than 1using System;class GFG { // Function to calculate // Minimum flips to make // Mean of all k size // Subarrays less than 1 static int minimumFlips(int N, int[] A, int K) { // Initializing answer by 0 // That stores the number of flips int answer = 0; // Initializing count variable by 0 // That stores the number of consecutive 1s int count = 0; // iterating through the array for (int i = 0; i < N; i++) { if (A[i] == 1) { // If current element is 1, // We increment count by 1 count++; // if count of consecutive 1s // Reaches k, we increment the answer // as the mean of the subarray from // i-k to ith element becomes 1 if (count == K) { answer++; count = 0; } } // else if current element is // 0, we make count 0 else { count = 0; } } // returning the required answer return answer; } // Driver Code public static void Main(string[] args) { int N = 5, K = 5; int[] A = { 1, 1, 1, 1, 1 }; int minimum_flips = minimumFlips(N, A, K); Console.WriteLine(minimum_flips); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript code for the above approach // Function to calculate // Minimum flips to make // Mean of all k size // Subarrays less than 1 function minimumFlips(N, A, K) { // Initializing answer by 0 // That stores the number of flips let answer = 0; // Initializing count variable by 0 // That stores the number of consecutive 1s let count = 0; // iterating through the array for (let i = 0; i < N; i++) { if (A[i] == 1) { // If current element is 1, // We increment count by 1 count++; // if count of consecutive 1s // Reaches k, we increment the answer // as the mean of the subarray from // i-k to ith element becomes 1 if (count == K) { answer++; count = 0; } } // else if current element is // 0, we make count 0 else { count = 0; } } // returning the required answer return answer; } // Driver Code let N = 5, K = 5; let A = [1, 1, 1, 1, 1]; let minimum_flips = minimumFlips(N, A, K); document.write(minimum_flips); // This code is contributed by Potta Lokesh </script> |
Output
1
Time Complexity: O(N)
Auxiliary Space: O(1)
Another Approach:
- Define the function minimumFlips that takes in an integer N, an integer array A of size N, and an integer K as input parameters and returns an integer as the output.
- Initialize two variables answer and sum to 0.
- Traverse through the first K-1 elements of the array and add their values to sum.
- Traverse through the remaining elements of the array from K to N-1.
- Add the current element to sum.
- Check if the arithmetic mean of the K consecutive elements starting from the current element is greater than or equal to 1.
- If it is, increment answer by 1 and decrement sum by 1 (as we need to flip the current element to 0).
- Check if the index i-K+1 is greater than or equal to 0 (to ensure that we do not access out of bounds elements).
- If it is, subtract the value of the element at index i-K+1 from sum.
- Return the value of answer as the output.
C++
#include<bits/stdc++.h>using namespace std;int minimumFlips(int N, int A[], int K) { int answer = 0, sum = 0; for(int i = 0; i < K - 1; i++) { sum += A[i]; } for(int i = K - 1; i < N; i++) { sum += A[i]; if((double)sum/K >= 1) { answer++; sum--; } if(i - K + 1 >= 0) { sum -= A[i - K + 1]; } } return answer;}int main() { int N = 5, K = 5; int A[] = { 1, 1, 1, 1, 1 }; int minimum_flips = minimumFlips(N, A, K); cout << minimum_flips << endl; return 0;} |
Java
import java.util.*;public class Main { public static int minimumFlips(int N, int A[], int K) { int answer = 0, sum = 0; for (int i = 0; i < K - 1; i++) { sum += A[i]; } for (int i = K - 1; i < N; i++) { sum += A[i]; if ((double) sum / K >= 1) { answer++; sum--; } if (i - K + 1 >= 0) { sum -= A[i - K + 1]; } } return answer; } public static void main(String[] args) { int N = 5, K = 5; int[] A = {1, 1, 1, 1, 1}; int minimum_flips = minimumFlips(N, A, K); System.out.println(minimum_flips); }} |
Python
def minimumFlips(N, A, K): answer = 0 sum_val = 0 for i in range(K - 1): sum_val += A[i] for i in range(K - 1, N): sum_val += A[i] if sum_val / K >= 1: answer += 1 sum_val -= 1 if i - K + 1 >= 0: sum_val -= A[i - K + 1] return answerN = 5K = 5A = [1, 1, 1, 1, 1]minimum_flips = minimumFlips(N, A, K)print(minimum_flips) |
C#
using System;public class MainClass{ public static int MinimumFlips(int N, int[] A, int K) { int answer = 0; int sum = 0; // Calculate the initial sum of the first K-1 elements for (int i = 0; i < K - 1; i++) { sum += A[i]; } // Iterate through the array for (int i = K - 1; i < N; i++) { sum += A[i]; // Check if the average of the current K elements is greater than or equal to 1 if ((double)sum / K >= 1) { answer++; sum--; } // Remove the contribution of the first element in the sliding window if (i - K + 1 >= 0) { sum -= A[i - K + 1]; } } return answer; } public static void Main(string[] args) { int N = 5; int K = 5; int[] A = { 1, 1, 1, 1, 1 }; int minimumFlips = MinimumFlips(N, A, K); Console.WriteLine(minimumFlips); }} |
Javascript
function minimumFlips(N, A, K) { let answer = 0, sum = 0; for(let i = 0; i < K - 1; i++) { sum += A[i]; } for(let i = K - 1; i < N; i++) { sum += A[i]; if(sum/K >= 1) { answer++; sum--; } if(i - K + 1 >= 0) { sum -= A[i - K + 1]; } } return answer;}let N = 5, K = 5;let A = [ 1, 1, 1, 1, 1 ];let minimum_flips = minimumFlips(N, A, K);console.log(minimum_flips); |
Output
1
Time complexity: O(n)
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!
Share your thoughts in the comments