综合编程

Minimum flips in a Binary array such that XOR of consecutive subarrays of size K have diffe…

微信扫一扫,分享到朋友圈

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

link

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

link

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

link

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

Recommended Posts:

据称在iOS 14代码中发现了无刘海的iPhone 12

上一篇

余承东携手表新品亮相P40/Pro发布会,华为Watch GT2新色、GT2e吸睛

下一篇

你也可能喜欢

评论已经被关闭。

插入图片

热门栏目

Minimum flips in a Binary array such that XOR of consecutive subarrays of size K have diffe…

长按储存图像,分享给朋友