# Minimum flips in a Binary array such that XOR of consecutive subarrays of size K have diffe… Given a binary array arr[]
of length N
, the task is to find the minimum flips required in the array such that XOR of a consecutive sub-arrays of size K have different parity.

#### Examples:

Input:arr[] = {0, 1, 0, 1, 1}, K = 2

Output:2

Explanation:

For the above given array XOR of consective sub-array of size 2 is: {(0, 1): 1, (1, 0): 1, (0, 1): 1, (1, 1): 0}

There are two flips required which can be done on the following indices:

Index 0:It is required to flip the bit of the 0 th
index, such that XOR of first sub-array remains 1.

Index 1:It is required to flip the bit of 1 st
index, such that XOR of second sub-array becomes 0.

Input:arr[]={0, 0, 1, 1, 0, 0}, K = 3

Output:1

Explanation:

For the above given array XOR of consective sub-array of size 2 is: {(0, 0, 1): 1, (0, 1, 1): 0, (1, 1, 0): 0, (1, 0, 0): 1}

There is one flip required which can be done on the following indices:

Index 4:It is required to flip the bit of the 4 th
index, such that XOR of third sub-array becomes 1 and XOR of fourth subarray becomes 0.

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach:To make the differentparity of consecutive subarrays, the total array is dependent upon the first subarray of size K. That is every next subarray of size K should be the negation of the previous subarray.

For Example:For an array of size 4, such that consecutive subarray of size 2 have different parity:

```Let the first subarray of size 2 be {1, 1}
Then the next subarray can be {0, 0}
Consecutive subarrays of size 2 in this array:
{(1, 1): 0, (1, 0): 1, (0, 0): 0}```

Below is the implementation of the above approach:

## Java

filter_none

edit

close

play_arrow

brightness_4

code

`// Java implementation to find the minimum flips`
`// required such that alternate subarrays`
`// have different parity`
` `
`import`
`java.util.*;`
` `
`class`
`Count_Flips {`
`  `
`  `
`// Function to find the minimum`
`  `
`// flips required in binary array`
`  `
`public`
`static`
`int`
`count_flips(`
`  `
`int`
`a[],`
`int`
`n,`
`int`
`k){`
`  `
`  `
`// Boolean value to indicate`
`  `
`// odd or even value of 1's`
`  `
`boolean`
`set =`
`false`
`;`
`  `
`int`
`ans =`
`0`
`, `
`  `
`min_diff = Integer.MAX_VALUE;`
`  `
`  `
`// Loop to iterate over `
`  `
`// the subarrays of size K`
`  `
`for`
`(`
`int`
`i =`
`0`
`; i < k; i++) {`
`  `
`  `
`// curr_index is used to iterate`
`  `
`// over all the subarrays`
`  `
`int`
`curr_index = i, segment =`
`0`
`, `
`  `
`count_zero =`
`0`
`, count_one =`
`0`
`;`
`  `
`  `
`// Loop to iterate over the array`
`  `
`// at the jump of K to `
`  `
`// consider every parity`
`  `
`while`
`(curr_index < n) {`
`  `
`  `
`// Condition to check if the `
`  `
`// subarray is at even position`
`  `
`if`
`(segment %`
`2`
`==`
`0`
`) {`
`  `
`  `
`// The value needs to be `
`  `
`// same as the first subarray`
`  `
`if`
`(a[curr_index] ==`
`1`
`)`
`  `
`count_zero++;`
`  `
`else`
`  `
`count_one++;`
`  `
`}`
`  `
`else`
`{`
`  `
`// The value needs to be `
`  `
`// opposite of the first subarray`
`  `
`if`
`(a[curr_index] ==`
`0`
`)`
`  `
`count_zero++;`
`  `
`else`
`  `
`count_one++;`
`  `
`}`
`  `
`curr_index = curr_index + k;`
`  `
`segment++;`
`  `
`}`
`  `
`ans += Math.min(count_one, count_zero);`
`  `
`if`
`(count_one < count_zero)`
`  `
`set = !set;`
`  `
`// Update the minimum difference`
`  `
`min_diff = Math.min(min_diff, `
`  `
`Math.abs(count_zero - count_one));`
`  `
`}`
`  `
`// Condition to check if the 1s`
`  `
`// in the subarray is odd`
`  `
`if`
`(set)`
`  `
`return`
`ans;`
`  `
`else`
`  `
`return`
`ans + min_diff;`
`  `
`}`
`  `
`  `
`// Driver Code`
`  `
`public`
`static`
`void`
`main(String[] args)`
`  `
`{`
`  `
`int`
`n =`
`6`
`, k =`
`3`
`;`
`  `
`int`
`a[] = {`
`0`
`,`
`0`
`,`
`1`
`,`
`1`
`,`
`0`
`,`
`0`
`};`
`  `
`System.out.println(count_flips(a, n, k));`
`  `
`}`
`}`

chevron_right

filter_none

## C++

filter_none

edit

close

play_arrow

brightness_4

code

`// C++ implementation to find the`
`// minimum flips required such that`
`// alternate subarrays have `
`// different parity`
` `
`#include <iostream>`
`#include <limits.h>`
`using`
`namespace`
`std;`
` `
`  `
`// Function to find the minimum`
`// flips required in binary array`
`int`
`count_flips(`
`int`
`a[],`
`int`
`n,`
`int`
`k)`
`{`
`  `
`// Boolean value to indicate`
`  `
`// odd or even value of 1's`
`  `
`bool`
`set =`
`false`
`;`
`  `
`int`
`ans = 0, min_diff = INT_MAX;`
`  `
`  `
`// Loop to iterate over `
`  `
`// the subarrays of size K`
`  `
`for`
`(`
`int`
`i = 0; i < k; i++) {`
`  `
`  `
`// curr_index is used to iterate`
`  `
`// over all the subarrays`
`  `
`int`
`curr_index = i, segment = 0, `
`  `
`count_zero = 0, count_one = 0;`
`  `
`  `
`// Loop to iterate over the array`
`  `
`// at the jump of K to `
`  `
`// consider every parity `
`  `
`while`
`(curr_index < n) {`
` `
`  `
`// Condition to check if the `
`  `
`// subarray is at even position`
`  `
`if`
`(segment % 2 == 0) {`
` `
`  `
`// The value needs to be `
`  `
`// same as the first subarray`
`  `
`if`
`(a[curr_index] == 1)`
`  `
`count_zero++;`
`  `
`else`
`  `
`count_one++;`
`  `
`}`
`  `
`else`
`{`
`  `
`// The value needs to be `
`  `
`// opposite of the first subarray`
`  `
`if`
`(a[curr_index] == 0)`
`  `
`count_zero++;`
`  `
`else`
`  `
`count_one++;`
`  `
`}`
`  `
`curr_index = curr_index + k;`
`  `
`segment++;`
`  `
`}`
`  `
`ans += min(count_one, count_zero);`
`  `
`if`
`(count_one < count_zero)`
`  `
`set = !set;`
`  `
`// Update the minimum difference`
`  `
`min_diff = min(min_diff, `
`  `
`abs`
`(count_zero - count_one));`
`  `
`}`
` `
`  `
`// Condition to check if the 1s`
`  `
`// in the subarray is odd`
`  `
`if`
`(set)`
`  `
`return`
`ans;`
`  `
`else`
`  `
`return`
`ans + min_diff;`
`}`
` `
`// Driver Code`
`int`
`main()`
`{`
`  `
`int`
`n = 6, k = 3;`
`  `
`int`
`a[] = { 0, 0, 1, 1, 0, 0 };`
`  `
`cout << count_flips(a, n, k);`
`}`

chevron_right

filter_none

## Python

filter_none

edit

close

play_arrow

brightness_4

code

`# Python implementation to find the`
`# minimum flips required such that`
`# alternate subarrays have `
`# different parity`
` `
`# Function to find the minimum`
`# flips required in binary array`
`def`
`count_flips(a, n, k):`
`  `
`min_diff, ans,`
`set`
`=`
`n,`
`0`
`,`
`False`
`  `
`  `
`# Loop to iterate over `
`  `
`# the subarrays of size K`
`  `
`for`
`i`
`in`
`range`
`(k):`
`  `
`# curr_index is used to iterate`
`  `
`# over all the subarrays`
`  `
`curr_index, segment,`
`  `
`count_zero, count_one`
`=`
`  `
`i,`
`0`
`,`
`0`
`,`
`0`
`  `
`  `
`# Loop to iterate over the array`
`  `
`# at the jump of K to `
`  `
`# consider every parity`
`  `
`while`
`curr_index < n:`
`  `
`  `
`# Condition to check if the `
`  `
`# subarray is at even position`
`  `
`if`
`segment`
`%`
`2`
`=`
`=`
`0`
`:`
`  `
`# The value needs to be `
`  `
`# same as the first subarray`
`  `
`if`
`a[curr_index]`
`=`
`=`
`1`
`:`
`  `
`count_zero`
`+`
`=`
`1`
`  `
`else`
`:`
`  `
`count_one`
`+`
`=`
`1`
`  `
`else`
`:`
`  `
`# The value needs to be `
`  `
`# opposite of the first subarray`
`  `
`if`
`a[curr_index]`
`=`
`=`
`0`
`:`
`  `
`count_zero`
`+`
`=`
`1`
`  `
`else`
`:`
`  `
`count_one`
`+`
`=`
`1`
`  `
`curr_index`
`+`
`=`
`k`
`  `
`segment`
`+`
`=`
`1`
`  `
`ans`
`+`
`=`
`min`
`(count_zero, count_one)`
`  `
`if`
`count_one<count_zero:`
`  `
`set`
`=`
`not`
`set`
`  `
`min_diff`
`=`
`min`
`(min_diff,`
`  `
`abs`
`(count_zero`
`-`
`count_one))`
`  `
`# Condition to check if the 1s`
`  `
`# in the subarray is odd`
`  `
`if`
`set`
`:`
`  `
`return`
`ans`
`  `
`else`
`:`
`  `
`return`
`ans`
`+`
`min_diff`
` `
`# Driver Code`
`if`
`__name__`
`=`
`=`
`"__main__"`
`:`
`  `
`n, k`
`=`
`6`
`,`
`3`
`  `
`a`
`=`
`[`
`0`
`,`
`0`
`,`
`1`
`,`
`1`
`,`
`0`
`,`
`0`
`]`
`  `
`print`
`(count_flips(a, n, k))`

chevron_right

filter_none

Output:

#### Performance Analysis:

• Time Complexity:
As in the above approach, There is only one loop which takes O(N) time in worst case. Hence the Time Complexity will be O(N)
.
• Auxiliary Space Complexity:
As in the above approach, There is no extra space used. Hence the auxiliary space complexity will be O(1)
.

My Personal Notes

arrow_drop_up • ### Socket Programming HOWTO — Python 3.8.2 documentation

#### 热门栏目 