Given a binary array arr[] (containing only 0s and 1s) and an integer K. The task is to find the minimum number of moves to make the array K-periodic.
An array is said to be K-periodic if the sub-arrays [1 to K], [k+1 to 2K], [2k+1 to 3K], … are all exactly same.
In a single move any 1 can be changed to a 0 or any 0 can be changed into a 1.
Examples:
Input: arr[] = {1, 1, 0, 0, 1, 1}, K = 2
Output: 2
The new array can be {1, 1, 1, 1, 1, 1}Input: arr[] = {1, 0, 0, 0, 1, 0}, K = 2
Output: 1
The new array can be {1, 0, 1, 0, 1, 0}
Approach: For an array to be K-periodic. Consider indices i where i % K = X. All these indices must have the same value. So either the 1s can be converted to 0s or vice-versa. In order to reduce the number of moves, we choose the conversion which is minimum.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the minimum moves required int minMoves( int n, int a[], int k) { int ct1[k] = { 0 }, ct0[k] = { 0 }, moves = 0; // Count the number of 1s and 2s // at each X such that i % K = X for ( int i = 0; i < n; i++) if (a[i] == 1) ct1[i % k]++; else ct0[i % k]++; // Choose the minimum elements to change for ( int i = 0; i < k; i++) moves += min(ct1[i], ct0[i]); // Return the minimum moves required return moves; } // Driver code int main() { int k = 2; int a[] = { 1, 0, 0, 0, 1, 0 }; int n = sizeof (a) / sizeof (a[0]); cout << minMoves(n, a, k); return 0; } |
Java
// Java implementation of the approach import java.io.*; class GFG { // Function to return the minimum // moves required static int minMoves( int n, int a[], int k) { int ct1[] = new int [k]; int ct0[] = new int [k]; int moves = 0 ; // Count the number of 1s and 2s // at each X such that i % K = X for ( int i = 0 ; i < n; i++) if (a[i] == 1 ) ct1[i % k]++; else ct0[i % k]++; // Choose the minimum elements to change for ( int i = 0 ; i < k; i++) moves += Math.min(ct1[i], ct0[i]); // Return the minimum moves required return moves; } // Driver code public static void main (String[] args) { int k = 2 ; int a[] = { 1 , 0 , 0 , 0 , 1 , 0 }; int n = a.length; System.out.println(minMoves(n, a, k)); } } // This is code contributed by inder_verma |
Python3
# Python3 implementation of the approach # Function to return the minimum # moves required def minMoves(n, a, k): ct1 = [ 0 for i in range (k)] ct0 = [ 0 for i in range (k)] moves = 0 # Count the number of 1s and 2s # at each X such that i % K = X for i in range (n): if (a[i] = = 1 ): ct1[i % k] + = 1 else : ct0[i % k] + = 1 # Choose the minimum elements to change for i in range (k): moves + = min (ct1[i], ct0[i]) # Return the minimum moves required return moves # Driver code if __name__ = = '__main__' : k = 2 a = [ 1 , 0 , 0 , 0 , 1 , 0 ] n = len (a) print (minMoves(n, a, k)) # This code is contributed by # Surendra_Gangwar |
C#
// C# implementation of the approach using System; class GFG { // Function to return the minimum // moves required static int minMoves( int n, int [] a, int k) { int [] ct1 = new int [k]; int [] ct0 = new int [k]; int moves = 0; // Count the number of 1s and 2s // at each X such that i % K = X for ( int i = 0; i < n; i++) if (a[i] == 1) ct1[i % k]++; else ct0[i % k]++; // Choose the minimum elements to change for ( int i = 0; i < k; i++) moves += Math.Min(ct1[i], ct0[i]); // Return the minimum moves required return moves; } // Driver code public static void Main () { int k = 2; int [] a = { 1, 0, 0, 0, 1, 0 }; int n = a.Length; Console.WriteLine(minMoves(n, a, k)); } } // This is code contributed by Code_Mech |
PHP
<?php // PHP implementation of the approach // Function to return the minimum // moves required function minMoves( $n , $a , $k ) { $ct1 = array (); $ct0 = array (); $moves = 0; // Count the number of 1s and 2s // at each X such that i % K = X for ( $i = 0; $i < $n ; $i ++) if ( $a [ $i ] == 1) $ct1 [ $i % $k ]++; else $ct0 [ $i % $k ]++; // Choose the minimum elements to change for ( $i = 0; $i < $k ; $i ++) $moves += min( $ct1 [ $i ], $ct0 [ $i ]); // Return the minimum moves required return $moves ; } // Driver code $k = 2; $a = array (1, 0, 0, 0, 1, 0); $n = sizeof( $a ); echo (minMoves( $n , $a , $k )); // This is code contributed by Code_Mech. |
Javascript
<script> // Javascript implementation of the approach // Function to return the minimum moves required function minMoves(n, a, k) { let ct1 = new Uint8Array(k), ct0 = new Uint8Array(k), moves = 0; // Count the number of 1s and 2s // at each X such that i % K = X for (let i = 0; i < n; i++) if (a[i] == 1) ct1[i % k]++; else ct0[i % k]++; // Choose the minimum elements to change for (let i = 0; i < k; i++) moves += Math.min(ct1[i], ct0[i]); // Return the minimum moves required return moves; } // Driver code let k = 2; let a = [ 1, 0, 0, 0, 1, 0 ]; let n = a.length; document.write(minMoves(n, a, k)); // This code is contributed by Mayank Tyagi </script> |
1
Time Complexity: O(n + k), where n is the size of the given array and k is the given input.
Auxiliary Space: O(k), where k is the given input.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!