Минимальный подмассив такой, что количество единиц в конкатенации двоичного представления его элементов не менее K

Опубликовано: 14 Января, 2022

Дан массив arr [], состоящий из неотрицательных целых чисел и целого числа k . Задача состоит в том, чтобы найти минимальную длину любого подмассива arr [] , чтобы, если все элементы этого подмассива представлены в двоичной нотации и объединены в двоичную строку, то количество единиц в результирующей строке будет не менее k . Если такой подмассив не существует, выведите -1 .

Примеры:

Input: arr[] = {4, 3, 7, 9}, k = 4
Output: 2
A possible sub-array is {3, 7}.

Input: arr[] = {1, 2, 4, 8}, k = 2
Output: 2

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход: идея состоит в том, чтобы использовать две переменные j и i и инициализировать их значениями 0 и 1 соответственно, а также массив count_one, который будет хранить количество присутствующих в двоичном представлении конкретного элемента массива и сумму переменных для хранения количество единиц до индекса и ответов для хранения минимальной длины. Теперь выполните итерацию по массиву, если количество единиц i-го или j-го элемента count_one равно k, затем обновите ans как 1, если сумма числа 1 до i-го элемента больше или равна k, обновите ans как минимум из ans и (ij) +1 , иначе, если оно меньше k, увеличьте j на 1, чтобы увеличить значение суммы .

Below is the implementation of the approach:

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];
            
Алгоритмы Структуры данных

РЕКОМЕНДУЕМЫЕ СТАТЬИ

Разница между жадным алгоритмом и алгоритмом «разделяй и властвуй»
14 Февраля, 2023
Сжатие и распаковка текстовых файлов с использованием кодирования Хаффмана
21 Января, 2023
Различия между структурой данных массива и словаря
21 Января, 2023
TCS SDE Sheet: Вопросы и ответы для интервью
12 Января, 2023
Введение в амортизированный анализ
12 Января, 2023
Как анализировать сложность рекуррентного отношения
12 Января, 2023
Множественные сравнения в очереди приоритетов С++?
6 Января, 2023
Когда использовать Queue over ArrayList в Java?
6 Января, 2023