Encuentre todos los rangos de índice de subarreglo en un Array dado con una suma de bits establecida igual a X

Posted on by Rudeus Greyrat

Dada una array arr (indexación basada en 1) de longitud N y un número entero X , la tarea es encontrar e imprimir todos los rangos de índice que tengan una suma de bits establecida igual a X en la array.

Ejemplos:

Entrada: A[] = {1 4 3 5 7}, X = 4
Salida:  (1, 3), (3, 4)
Explicación: En el subarreglo de la array anterior, la suma de bits establecida es igual a X (= 4). 
Partiendo del índice 1 al 3. {1 4 3} = (001) + (100) + (011) = 4 y 
otro es del 3 al 4 {3, 5} = (011) + (101) = 4.

Entrada: arr[] = {5, 3, 0, 4, 10}, X = 7
Salida:  (1 5)
Explicación: En la array anterior, los subarreglos que establecieron la suma de bits igual a X(= 7) comienzan de 1 a 5 solamente.

 

Enfoque: El problema se resuelve utilizando el enfoque de dos punteros . 

  • Escriba una función countSetBit para contar el número de bits establecidos.
    • Inicialice un contador c=0 para almacenar el recuento individual de cada número en la array.
    • Iterar sobre la array y verificar cada bit establecido y aumentar el contador.
    • reemplazar cada número con el conteo de un número de bits establecidos
  • Escriba una función para imprimir un rango de subarreglos PrintIndex
       Ejecute un ciclo usando dos punteros i y j y verifique la suma de la siguiente manera:
    • Si la suma del índice actual es menor que X, agregue el valor en arr[j] en currsum
    • de lo contrario, si la suma es igual a X, retroceda el índice inicial y final de la array e incremente el contador i.
    • de lo contrario, disminuya el contador, reste el valor en arr[i] de currsum.
    • Repita lo mismo para todos los elementos.
       

A continuación se muestra la implementación del método anterior:

C++

// C++ program to Find all range
// Having set bit sum X  in array
#include <bits/stdc++.h>
using namespace std;
 
// Function to replace elements
// With their set bit count
void countSetBit(vector<int>& arr, int n)
{
    int c = 0, i;
 
    for (i = 0; i < n; i++) {
 
        int x = arr[i];
        while (x) {
            int l = x % 10;
            if (x & 1)
                c++;
            x /= 2;
        }
        // Replace array element
        // to set bit count
        arr[i] = c;
        c = 0;
    }
}
 
// Function to find range of subarrays
// having set bit sum equal to X.
void PrintIndex(vector<int> arr, int N, int X,
                vector<int>& v)
{
 
    int i = 0, j = 0, currSum = arr[0];
    while (j < N && i < N) {
        if (currSum == X) {
            // push back index i start
            // point ans end point j
            // when sum == X
 
            v.push_back(i + 1);
            v.push_back(j + 1);
 
            j++;
            currSum += arr[j];
        }
        // when current sum is
        // less than X increment j
        // and add arr[j]
        else if (currSum < X) {
            j++;
            currSum += arr[j];
        }
        // when current sum is
        // greater than X increment j
        // and subtract arr[i]
        else {
            currSum -= arr[i];
            i++;
        }
    }
}
 
// Driver code
int main()
{
    vector<int> v = { 1, 4, 3, 5, 7 };
    int X = 4;
    int N = v.size();
 
    // replace all the array element into
    // their set bit count value
    countSetBit(v, N);
 
    vector<int> ans;
 
    PrintIndex(v, N, X, ans);
 
    for (int i = 0; i < ans.size() - 1; i += 2)
        cout << "(" << ans[i] << " "
             << ans[i + 1] << ")"
             << " ";
 
    return 0;
}

Java

// JAVA code to implement the above approach
import java.util.*;
class GFG {
 
  // Function to replace elements
  // With their set bit count
  static void countSetBit(int[] arr, int n)
  {
    int c = 0, i;
 
    for (i = 0; i < n; i++) {
 
      int x = arr[i];
      while (x > 0) {
        int l = x % 10;
        if ((x & 1) == 1)
          c++;
        x /= 2;
      }
      // Replace array element
      // to set bit count
      arr[i] = c;
      c = 0;
    }
  }
 
  // Function to find range of subarrays
  // having set bit sum equal to X.
  static void PrintIndex(int[] arr, int N, int X,
                         ArrayList<Integer> v)
  {
 
    int i = 0, j = 0, currSum = arr[0];
    while (j < N && i < N) {
      if (currSum == X) {
        // push back index i start
        // point ans end point j
        // when sum == X
 
        v.add(i + 1);
        v.add(j + 1);
 
        j++;
        if (j < N)
          currSum += arr[j];
      }
      // when current sum is
      // less than X increment j
      // and add arr[j]
      else if (currSum < X) {
        j++;
        if (j < N)
          currSum += arr[j];
      }
      // when current sum is
      // greater than X increment j
      // and subtract arr[i]
      else {
        currSum -= arr[i];
        i++;
      }
    }
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int[] v = { 1, 4, 3, 5, 7 };
    int X = 4;
    int N = v.length;
 
    // replace all the array element into
    // their set bit count value
    countSetBit(v, N);
 
    ArrayList<Integer> ans = new  ArrayList<Integer>();
 
    PrintIndex(v, N, X, ans);
 
    for (int i = 0; i < ans.size() - 1; i += 2)
      System.out.print("(" + ans.get(i) + " " + ans.get(i + 1)
                       + ")"
                       + " ");
  }
}
 
// This code is contributed by sanjoy_62.

Python3

# Python program to Find all range
# Having set bit sum X in array
 
# Function to replace elements
# With their set bit count
def countSetBit(arr, n):
    c = 0
 
    for i in range(n):
        x = arr[i]
        while (x):
            l = x % 10
            if (x & 1):
                c += 1
            x = x // 2
                 
        # Replace array element
        # to set bit count
        arr[i] = c
        c = 0
 
# Function to find range of subarrays
# having set bit sum equal to X.
def PrintIndex(arr, N, X, v):
 
    i,j,currSum = 0,0,arr[0]
 
    while (j < N and i < N):
 
        if (currSum == X):
                 
            # append back index i start
            # point ans end point j
            # when sum == X
 
            v.append(i + 1)
            v.append(j + 1)
 
            j += 1
            if(j<N):
                currSum += arr[j]
                 
        # when current sum is
        # less than X increment j
        # and add arr[j]
        elif (currSum < X):
            j += 1
            if(j<N):
                currSum += arr[j]
                 
        # when current sum is
        # greater than X increment j
        # and subtract arr[i]
        else:
            currSum -= arr[i]
            i += 1
 
# Driver code
v = [1, 4, 3, 5, 7]
X = 4
N = len(v)
 
# replace all the array element into
# their set bit count value
countSetBit(v, N)
ans = []
PrintIndex(v, N, X, ans)
 
for i in range(0,len(ans) - 1,2):
    print(f"({ans[i]} {ans[i + 1]})",end=" ")
 
# This code is contributed by shinjanpatra

C#

// C# program to Find all range
// Having set bit sum X  in array
using System;
using System.Collections;
 
class GFG {
 
  // Function to replace elements
  // With their set bit count
  static void countSetBit(int[] arr, int n)
  {
    int c = 0, i;
 
    for (i = 0; i < n; i++) {
 
      int x = arr[i];
      while (x > 0) {
        int l = x % 10;
        if ((x & 1) == 1)
          c++;
        x /= 2;
      }
      // Replace array element
      // to set bit count
      arr[i] = c;
      c = 0;
    }
  }
 
  // Function to find range of subarrays
  // having set bit sum equal to X.
  static void PrintIndex(int[] arr, int N, int X,
                         ArrayList v)
  {
 
    int i = 0, j = 0, currSum = arr[0];
    while (j < N && i < N) {
      if (currSum == X) {
        // push back index i start
        // point ans end point j
        // when sum == X
 
        v.Add(i + 1);
        v.Add(j + 1);
 
        j++;
        if (j < N)
          currSum += arr[j];
      }
      // when current sum is
      // less than X increment j
      // and add arr[j]
      else if (currSum < X) {
        j++;
        if (j < N)
          currSum += arr[j];
      }
      // when current sum is
      // greater than X increment j
      // and subtract arr[i]
      else {
        currSum -= arr[i];
        i++;
      }
    }
  }
 
  // Driver code
  public static void Main()
  {
    int[] v = { 1, 4, 3, 5, 7 };
    int X = 4;
    int N = v.Length;
 
    // replace all the array element into
    // their set bit count value
    countSetBit(v, N);
 
    ArrayList ans = new ArrayList();
 
    PrintIndex(v, N, X, ans);
 
    for (int i = 0; i < ans.Count - 1; i += 2)
      Console.Write("(" + ans[i] + " " + ans[i + 1]
                    + ")"
                    + " ");
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript program to Find all range
    // Having set bit sum X in array
 
    // Function to replace elements
    // With their set bit count
    const countSetBit = (arr, n) => {
        let c = 0, i;
 
        for (i = 0; i < n; i++) {
 
            let x = arr[i];
            while (x) {
                let l = x % 10;
                if (x & 1)
                    c++;
                x = parseInt(x / 2);
            }
             
            // Replace array element
            // to set bit count
            arr[i] = c;
            c = 0;
        }
    }
 
    // Function to find range of subarrays
    // having set bit sum equal to X.
    const PrintIndex = (arr, N, X, v) => {
 
        let i = 0, j = 0, currSum = arr[0];
        while (j < N && i < N)
        {
            if (currSum == X)
            {
             
                // push back index i start
                // point ans end point j
                // when sum == X
 
                v.push(i + 1);
                v.push(j + 1);
 
                j++;
                currSum += arr[j];
            }
             
            // when current sum is
            // less than X increment j
            // and add arr[j]
            else if (currSum < X) {
                j++;
                currSum += arr[j];
            }
             
            // when current sum is
            // greater than X increment j
            // and subtract arr[i]
            else {
                currSum -= arr[i];
                i++;
            }
        }
    }
 
    // Driver code
    let v = [1, 4, 3, 5, 7];
    let X = 4;
    let N = v.length;
 
    // replace all the array element into
    // their set bit count value
    countSetBit(v, N);
 
    let ans = [];
 
    PrintIndex(v, N, X, ans);
 
    for (let i = 0; i < ans.length - 1; i += 2)
        document.write(`(${ans[i]} ${ans[i + 1]}) `);
 
// This code is contributed by rakeshsahni
 
</script>
Producción: 

(1 3) (3 4)

 

Complejidad de tiempo: O(N * d) donde d es el conteo de bits en un elemento de array
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por nobita04 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *