Dada una array arr[] de tamaño N y un entero positivo K , la tarea es verificar si la array se puede dividir en K subarreglos no superpuestos y no vacíos , de modo que Bitwise AND de todos los subarreglos sean iguales. Si se encuentra que es cierto, escriba «SÍ» . De lo contrario, escriba “NO” .
Ejemplos:
Entrada: arr[] = { 3, 2, 2, 6, 2 }, K = 3
Salida: SÍ
Explicación:
Dividir la array en K( = 3) subarreglos como { { 3, 2 }, { 2, 6 }, { 2 } }
Por lo tanto, la salida requerida es SÍ.Entrada: arr[] = { 4, 3, 5, 2 }, K = 3
Salida: NO
Enfoque ingenuo: el enfoque más simple para resolver este problema es dividir la array en K subarreglos de todas las formas posibles y de todas las formas posibles, verificar si Bitwise AND de todos los K subarreglos son iguales o no. Si se encuentra que es cierto para cualquier división, escriba «SÍ» . De lo contrario, escriba “NO” .
Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar el hecho de que si el i -ésimo bit de al menos un elemento del subarreglo es 0 , entonces el i-ésimo bit del AND bit a bit de ese subarreglo también es 0 . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos flag , para verificar si la array se puede dividir en K subarreglos de modo que Bitwise AND de todos los subarreglos sea igual.
- Inicialice una array 2D , digamos pref[][] , donde pref[i][j] almacena el recuento de elementos de array contiguos hasta el i -ésimo índice cuyo j -ésimo bit está establecido.
- Iterar sobre el rango [0, N – K] . Para cada j -ésimo bit del i -ésimo elemento , verifique las siguientes condiciones:
- Si el j -ésimo bit de todos los elementos de la array hasta el i -ésimo índice está establecido y el j -ésimo bit de al menos un elemento de la array después del i -ésimo índice no está establecido, entonces actualice flag = false .
- Si el j -ésimo bit de al menos uno de los elementos de la array hasta el i -ésimo índice no está establecido y el j -ésimo bit de todos los elementos de la array después del i -ésimo índice están establecidos, entonces actualizar indicador = falso
- Finalmente, verifique si la bandera es igual a verdadera o no. Si se encuentra que es cierto, escriba «SÍ» .
- De lo contrario, escriba “NO” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to implement
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Utility function to check if the array
// can be split into K subarrays whose
// bitwise AND are equal
bool equalPartitionUtil(int arr[], int N, int K)
{
// pref[i][j]: Stores count of contiguous
// array elements upto i-th index whose
// j-th bit is set
int pref[N][32];
// Initialize pref[][] array
memset(pref, 0, sizeof(pref));
// Fill the prefix array
for (int i = 0; i < N; i++) {
for (int j = 0; j < 32; j++) {
if (i) {
// Check if j-th bit set or not
int X = ((arr[i] & (1 << j)) > 0);
// Update pref[i][j]
pref[i][j] = pref[i - 1][j] + X;
}
else {
// Update pref[i][j]
pref[i][j] = ((arr[i] & (1 << j)) > 0);
}
}
}
// Iterate over the range[0, N - K]
for (int i = 0; i < N - K + 1; i++) {
bool flag = true;
for (int j = 0; j < 32; j++) {
// Get count of elements that have
// jth bit set
int cnt = pref[i][j];
// Check if first case is satisfied
if (cnt == i + 1
&& pref[N - 1][j] - pref[i][j] != N - i - 1)
flag = false;
// Check if second case is satisfied
if (cnt != i + 1
&& N - i - 1 - (pref[N - 1][j] - pref[i][j]) < K - 1)
flag = false;
}
if (flag)
return true;
}
return false;
}
// Function to check if the array
// can be split into K subarrays
// having equal value of bitwise AND
void equalPartition(int arr[], int N, int K)
{
if (equalPartitionUtil(arr, N, K))
cout << "YES";
else
cout << "NO";
}
// Driver code
int main()
{
// Given array
int arr[] = { 3, 2, 2, 6, 2 };
// Size of the array
int N = sizeof(arr) / sizeof(arr[0]);
// Given K
int K = 3;
// Function Call
equalPartition(arr, N, K);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG{
// Utility function to check if the array
// can be split into K subarrays whose
// bitwise AND are equal
static boolean equalPartitionUtil(int arr[],
int N, int K)
{
// pref[i][j]: Stores count of contiguous
// array elements upto i-th index whose
// j-th bit is set
int [][]pref = new int[N][32];
// Fill the prefix array
for(int i = 0; i < N; i++)
{
for(int j = 0; j < 32; j++)
{
if (i > 0)
{
// Check if j-th bit set or not
int X = ((arr[i] & (1 << j)) > 0) ? 1 : 0;
// Update pref[i][j]
pref[i][j] = pref[i - 1][j] + X;
}
else
{
// Update pref[i][j]
pref[i][j] = ((arr[i] & (1 << j)) > 0) ? 1 : 0;
}
}
}
// Iterate over the range[0, N - K]
for(int i = 0; i < N - K + 1; i++)
{
boolean flag = true;
for(int j = 0; j < 32; j++)
{
// Get count of elements that have
// jth bit set
int cnt = pref[i][j];
// Check if first case is satisfied
if (cnt == i + 1 && pref[N - 1][j] -
pref[i][j] != N - i - 1)
flag = false;
// Check if second case is satisfied
if (cnt != i + 1 && N - i - 1 - (
pref[N - 1][j] - pref[i][j]) < K - 1)
flag = false;
}
if (flag)
return true;
}
return false;
}
// Function to check if the array
// can be split into K subarrays
// having equal value of bitwise AND
static void equalPartition(int arr[], int N, int K)
{
if (equalPartitionUtil(arr, N, K))
System.out.print("YES");
else
System.out.print("NO");
}
// Driver code
public static void main(String[] args)
{
// Given array
int arr[] = { 3, 2, 2, 6, 2 };
// Size of the array
int N = arr.length;
// Given K
int K = 3;
// Function Call
equalPartition(arr, N, K);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program to implement
# the above approach
# Utility function to check if the array
# can be split into K subarrays whose
# bitwise AND are equal
def equalPartitionUtil(arr, N, K):
# pref[i][j]: Stores count of contiguous
# array elements upto i-th index whose
# j-th bit is set
pref = [[0 for x in range(32)]for y in range(N)]
# Fill the prefix array
for i in range(N):
for j in range(32):
if (i):
# Check if j-th bit set or not
X = ((arr[i] & (1 << j)) > 0)
# Update pref[i][j]
pref[i][j] = pref[i - 1][j] + X
else:
# Update pref[i][j]
pref[i][j] = ((arr[i] & (1 << j)) > 0)
# Iterate over the range[0, N - K]
for i in range(N - K + 1):
flag = True
for j in range(32):
# Get count of elements that have
# jth bit set
cnt = pref[i][j]
# Check if first case is satisfied
if (cnt == i + 1
and pref[N - 1][j] - pref[i][j] != N - i - 1):
flag = False
# Check if second case is satisfied
if (cnt != i + 1
and N - i - 1 - (pref[N - 1][j] - pref[i][j]) < K - 1):
flag = False
if (flag):
return True
return False
# Function to check if the array
# can be split into K subarrays
# having equal value of bitwise AND
def equalPartition(arr, N, K):
if (equalPartitionUtil(arr, N, K)):
print("YES")
else:
print("NO")
# Driver code
if __name__ == "__main__":
# Given array
arr = [3, 2, 2, 6, 2]
# Size of the array
N = len(arr)
# Given K
K = 3
# Function Call
equalPartition(arr, N, K)
# This code is contributed by chitranayal.
C#
// C# program to implement
// the above approach
using System;
class GFG{
// Utility function to check if the array
// can be split into K subarrays whose
// bitwise AND are equal
static bool equalPartitionUtil(int []arr,
int N, int K)
{
// pref[i,j]: Stores count of contiguous
// array elements upto i-th index whose
// j-th bit is set
int [,]pref = new int[N, 32];
// Fill the prefix array
for(int i = 0; i < N; i++)
{
for(int j = 0; j < 32; j++)
{
if (i > 0)
{
// Check if j-th bit set or not
int X = ((arr[i] & (1 << j)) > 0) ? 1 : 0;
// Update pref[i,j]
pref[i, j] = pref[i - 1, j] + X;
}
else
{
// Update pref[i,j]
pref[i, j] = ((arr[i] & (1 << j)) > 0) ? 1 : 0;
}
}
}
// Iterate over the range[0, N - K]
for(int i = 0; i < N - K + 1; i++)
{
bool flag = true;
for(int j = 0; j < 32; j++)
{
// Get count of elements that have
// jth bit set
int cnt = pref[i, j];
// Check if first case is satisfied
if (cnt == i + 1 && pref[N - 1, j] -
pref[i, j] != N - i - 1)
flag = false;
// Check if second case is satisfied
if (cnt != i + 1 && N - i - 1 - (
pref[N - 1, j] - pref[i, j]) < K - 1)
flag = false;
}
if (flag)
return true;
}
return false;
}
// Function to check if the array
// can be split into K subarrays
// having equal value of bitwise AND
static void equalPartition(int []arr, int N, int K)
{
if (equalPartitionUtil(arr, N, K))
Console.Write("YES");
else
Console.Write("NO");
}
// Driver code
public static void Main(String[] args)
{
// Given array
int []arr = { 3, 2, 2, 6, 2 };
// Size of the array
int N = arr.Length;
// Given K
int K = 3;
// Function Call
equalPartition(arr, N, K);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program to implement
// the above approach
// Utility function to check if the array
// can be split into K subarrays whose
// bitwise AND are equal
function equalPartitionUtil(arr, N, K)
{
// pref[i][j]: Stores count of contiguous
// array elements upto i-th index whose
// j-th bit is set
var pref = Array.from(Array(N), ()=> Array(32).fill(0));
// Fill the prefix array
for (var i = 0; i < N; i++) {
for (var j = 0; j < 32; j++) {
if (i) {
// Check if j-th bit set or not
var X = ((arr[i] & (1 << j)) > 0);
// Update pref[i][j]
pref[i][j] = pref[i - 1][j] + X;
}
else {
// Update pref[i][j]
pref[i][j] = ((arr[i] & (1 << j)) > 0);
}
}
}
// Iterate over the range[0, N - K]
for (var i = 0; i < N - K + 1; i++) {
var flag = true;
for (var j = 0; j < 32; j++) {
// Get count of elements that have
// jth bit set
var cnt = pref[i][j];
// Check if first case is satisfied
if (cnt == i + 1
&& pref[N - 1][j] - pref[i][j] != N - i - 1)
flag = false;
// Check if second case is satisfied
if (cnt != i + 1
&& N - i - 1 - (pref[N - 1][j] - pref[i][j]) < K - 1)
flag = false;
}
if (flag)
return true;
}
return false;
}
// Function to check if the array
// can be split into K subarrays
// having equal value of bitwise AND
function equalPartition(arr, N, K)
{
if (equalPartitionUtil(arr, N, K))
document.write( "YES");
else
document.write( "NO");
}
// Driver code
// Given array
var arr = [ 3, 2, 2, 6, 2 ];
// Size of the array
var N = arr.length;
// Given K
var K = 3;
// Function Call
equalPartition(arr, N, K);
// This code is contributed by itsok.
</script>
Producción:
YES
Tiempo Complejidad: O(32 * N)
Espacio Auxiliar: O(32 * N)
Publicación traducida automáticamente
Artículo escrito por lostsoul27 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA