Dada una array arr[] que consta de enteros no negativos y un entero k . La tarea es encontrar la longitud mínima de cualquier subarreglo de arr[] tal que si todos los elementos de este subarreglo se representan en notación binaria y se concatenan para formar una string binaria, entonces el número de 1 en la string resultante es al menos k _ Si no existe tal subarreglo, imprima -1 .
Ejemplos:
Entrada: array[] = {4, 3, 7, 9}, k = 4
Salida: 2
Una posible sub-array es {3, 7}.Entrada: arr[] = {1, 2, 4, 8}, k = 2
Salida: 2
Enfoque: la idea es usar dos variables j e i e inicializarlas en 0 y 1 respectivamente, y una array count_one que almacenará el número de uno presente en la representación binaria de un elemento particular de la array y una suma variable para almacenar el número de 1 hasta i-ésimo índice y ans para almacenar la longitud mínima. Ahora itere sobre la array, si el número de 1 del i-ésimo o j-ésimo elemento de contar_uno es igual a k, entonces actualice ans como 1, si la suma del número de 1 hasta el i-ésimo elemento es mayor o igual a k actualice ans como mínimo de ans y (ij)+1, de lo contrario, si es menor que k, entonces incremente j en 1, para aumentar el valor de sum .
A continuación se muestra la implementación del enfoque:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Finds the sub-array with maximum length
int FindSubarray(int arr[], int n, int k)
{
// Array which stores number of ones
// present in the binary representation
// of ith element of the array
int count_one[n];
for (int i = 0; i < n; i++) {
count_one[i] = __builtin_popcount(arr[i]);
}
// Sum variable to store sum of
// number of ones
// Initialize it as number of ones
// present in the binary representation
// of 0th element of the array
int sum = count_one[0];
// If there is only a single element
if (n == 1) {
if (count_one[0] >= k)
return 1;
else
return -1;
}
// Stores the minimum length
// of the required sub-array
int ans = INT_MAX;
int i = 1;
int j = 0;
while (i < n) {
// If binary representation of jth
// element of array has 1's equal to k
if (k == count_one[j]) {
ans = 1;
break;
}
// If binary representation of ith
// element of array has 1's equal to k
else if (k == count_one[i]) {
ans = 1;
break;
}
// If sum of number of 1's of
// binary representation of elements upto
// ith element is less than k
else if (sum + count_one[i] < k) {
sum += count_one[i];
i++;
}
// If sum of number of 1's of
// binary representation of elements upto
// ith element is greater than k
else if (sum + count_one[i] > k) {
ans = min(ans, (i - j) + 1);
sum -= count_one[j];
j++;
}
else if (sum + count_one[i] == k) {
ans = min(ans, (i - j) + 1);
sum += count_one[i];
i++;
}
}
if (ans != INT_MAX)
return ans;
else
return -1;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 4, 8 };
int n = sizeof(arr) / sizeof(int);
int k = 2;
cout << FindSubarray(arr, n, k);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Finds the sub-array with maximum length
static int FindSubarray(int arr[], int n, int k)
{
// Array which stores number of ones
// present in the binary representation
// of ith element of the array
int []count_one = new int[n];
for (int i = 0; i < n; i++)
{
count_one[i] = Integer.bitCount(arr[i]);
}
// Sum variable to store sum of
// number of ones
// Initialize it as number of ones
// present in the binary representation
// of 0th element of the array
int sum = count_one[0];
// If there is only a single element
if (n == 1)
{
if (count_one[0] >= k)
return 1;
else
return -1;
}
// Stores the minimum length
// of the required sub-array
int ans = Integer.MAX_VALUE;
int i = 1;
int j = 0;
while (i < n)
{
// If binary representation of jth
// element of array has 1's equal to k
if (k == count_one[j])
{
ans = 1;
break;
}
// If binary representation of ith
// element of array has 1's equal to k
else if (k == count_one[i])
{
ans = 1;
break;
}
// If sum of number of 1's of
// binary representation of elements upto
// ith element is less than k
else if (sum + count_one[i] < k)
{
sum += count_one[i];
i++;
}
// If sum of number of 1's of
// binary representation of elements upto
// ith element is greater than k
else if (sum + count_one[i] > k)
{
ans = Math.min(ans, (i - j) + 1);
sum -= count_one[j];
j++;
}
else if (sum + count_one[i] == k)
{
ans = Math.min(ans, (i - j) + 1);
sum += count_one[i];
i++;
}
}
if (ans != Integer.MAX_VALUE)
return ans;
else
return -1;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 4, 8 };
int n = arr.length;
int k = 2;
System.out.println(FindSubarray(arr, n, k));
}
}
// This code is contributed by Princi Singh
Python3
# Python3 implementation of the approach
import sys;
# Finds the sub-array with maximum length
def FindSubarray(arr, n, k) :
# Array which stores number of ones
# present in the binary representation
# of ith element of the array
count_one = [0] * n;
for i in range(n) :
count_one[i] = bin(arr[i]).count('1');
# Sum variable to store sum of
# number of ones
# Initialize it as number of ones
# present in the binary representation
# of 0th element of the array
sum = count_one[0];
# If there is only a single element
if (n == 1) :
if (count_one[0] >= k) :
return 1;
else :
return -1;
# Stores the minimum length
# of the required sub-array
ans = sys.maxsize;
i = 1;
j = 0;
while (i < n) :
# If binary representation of jth
# element of array has 1's equal to k
if (k == count_one[j]) :
ans = 1;
break;
# If binary representation of ith
# element of array has 1's equal to k
elif (k == count_one[i]) :
ans = 1;
break;
# If sum of number of 1's of
# binary representation of elements upto
# ith element is less than k
elif (sum + count_one[i] < k) :
sum += count_one[i];
i += 1;
# If sum of number of 1's of
# binary representation of elements upto
# ith element is greater than k
elif (sum + count_one[i] > k) :
ans = min(ans, (i - j) + 1);
sum -= count_one[j];
j += 1;
elif (sum + count_one[i] == k) :
ans = min(ans, (i - j) + 1);
sum += count_one[i];
i += 1;
if (ans != sys.maxsize) :
return ans;
else :
return -1;
# Driver code
if __name__ == "__main__" :
arr = [ 1, 2, 4, 8 ];
n = len(arr);
k = 2;
print(FindSubarray(arr, n, k));
# This code is contributed by Ryuga
C#
// C# implementation of the approach
using System;
class GFG
{
// Finds the sub-array with maximum length
static int FindSubarray(int []arr, int n, int k)
{
// Array which stores number of ones
// present in the binary representation
// of ith element of the array
int []count_one = new int[n];
int i = 0;
for (i = 0; i < n; i++)
{
count_one[i] = bitCount(arr[i]);
}
// Sum variable to store sum of
// number of ones
// Initialize it as number of ones
// present in the binary representation
// of 0th element of the array
int sum = count_one[0];
// If there is only a single element
if (n == 1)
{
if (count_one[0] >= k)
return 1;
else
return -1;
}
// Stores the minimum length
// of the required sub-array
int ans = int.MaxValue;
i = 1;
int j = 0;
while (i < n)
{
// If binary representation of jth
// element of array has 1's equal to k
if (k == count_one[j])
{
ans = 1;
break;
}
// If binary representation of ith
// element of array has 1's equal to k
else if (k == count_one[i])
{
ans = 1;
break;
}
// If sum of number of 1's of
// binary representation of elements upto
// ith element is less than k
else if (sum + count_one[i] < k)
{
sum += count_one[i];
i++;
}
// If sum of number of 1's of
// binary representation of elements upto
// ith element is greater than k
else if (sum + count_one[i] > k)
{
ans = Math.Min(ans, (i - j) + 1);
sum -= count_one[j];
j++;
}
else if (sum + count_one[i] == k)
{
ans = Math.Min(ans, (i - j) + 1);
sum += count_one[i];
i++;
}
}
if (ans != int.MaxValue)
return ans;
else
return -1;
}
static int bitCount(long x)
{
int setBits = 0;
while (x != 0)
{
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 1, 2, 4, 8 };
int n = arr.Length;
int k = 2;
Console.WriteLine(FindSubarray(arr, n, k));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
// Finds the sub-array with maximum length
function FindSubarray(arr, n, k)
{
// Array which stores number of ones
// present in the binary representation
// of ith element of the array
let count_one = new Array(n);
let i = 0;
for(i = 0; i < n; i++)
{
count_one[i] = bitCount(arr[i]);
}
// Sum variable to store sum of
// number of ones
// Initialize it as number of ones
// present in the binary representation
// of 0th element of the array
let sum = count_one[0];
// If there is only a single element
if (n == 1)
{
if (count_one[0] >= k)
return 1;
else
return -1;
}
// Stores the minimum length
// of the required sub-array
let ans = Number.MAX_VALUE;
i = 1;
let j = 0;
while (i < n)
{
// If binary representation of jth
// element of array has 1's equal to k
if (k == count_one[j])
{
ans = 1;
break;
}
// If binary representation of ith
// element of array has 1's equal to k
else if (k == count_one[i])
{
ans = 1;
break;
}
// If sum of number of 1's of
// binary representation of elements upto
// ith element is less than k
else if (sum + count_one[i] < k)
{
sum += count_one[i];
i++;
}
// If sum of number of 1's of
// binary representation of elements upto
// ith element is greater than k
else if (sum + count_one[i] > k)
{
ans = Math.min(ans, (i - j) + 1);
sum -= count_one[j];
j++;
}
else if (sum + count_one[i] == k)
{
ans = Math.min(ans, (i - j) + 1);
sum += count_one[i];
i++;
}
}
if (ans != Number.MAX_VALUE)
return ans;
else
return -1;
}
function bitCount(x)
{
let setBits = 0;
while (x != 0)
{
x = x & (x - 1);
setBits++;
}
return setBits;
}
// Driver code
let arr = [ 1, 2, 4, 8 ];
let n = arr.length;
let k = 2;
document.write(FindSubarray(arr, n, k));
// This code is contributed by divyeshrabadiya07
</script>
Producción:
2
Publicación traducida automáticamente
Artículo escrito por Sakshi_Srivastava y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA