Dada una array de N enteros y un número X. La tarea es encontrar el índice del primer elemento que es mayor o igual a X en sumas de prefijos de N números.
Ejemplos:
Entrada: arr[] = { 2, 5, 7, 1, 6, 9, 12, 4, 6 } y x = 8
Salida: la array de suma de 2
prefijos formada es { 2, 7, 14, 15, 21, 30, 42, 46, 52}, por lo tanto, 14 es el número cuyo índice es 2Entrada: arr[] = { 2, 5, 7, 1, 6, 9, 12, 4, 6 } y x = 30
Salida: 5
Enfoque: el problema se puede resolver utilizando la función lower_bound en la búsqueda binaria . Pero en esta publicación, el problema se resolverá utilizando Binary-Lifting . En el levantamiento binario, un valor aumenta (o se eleva) en potencias de 2, comenzando con la potencia más alta posible de 2 (log (N)) hasta la potencia más baja (0).
- Inicialice position = 0 y configure cada bit de posición, desde el bit más significativo hasta el bit menos significativo.
- Cada vez que un bit se establece en 1, el valor de la posición aumenta (o se eleva).
- Mientras aumenta o eleva la posición, asegúrese de que la suma del prefijo hasta la posición sea menor que v.
- Aquí, los bits log(N) son necesarios para todos los valores posibles de ‘posición’ (desde log(N)th hasta 0th bit).
- Determine el valor del i-ésimo bit. Primero, verifique si establecer el i-ésimo bit no hará que la ‘posición’ sea mayor que N, que es el tamaño de la array. Antes de subir a la nueva ‘posición’, verifique que el valor en esa nueva ‘posición’ sea menor que X o no.
- Si esta condición es verdadera, la posición de destino se encuentra por encima de la ‘posición’ + 2^i , pero por debajo de la ‘posición’ + 2^(i+1). Esto se debe a que si la posición de destino estaba por encima de ‘posición’ + 2^(i+1), entonces la posición ya se habría elevado en 2^(i+1) (esta lógica es similar a la elevación binaria en los árboles).
- Si es falso, entonces el valor objetivo se encuentra entre ‘posición’ y ‘posición’ + 2^i , así que intente levantar con una potencia menor de 2. Finalmente, el ciclo terminará de tal manera que el valor en esa posición sea menor que X. Aquí, en esta pregunta, se pide el límite inferior. Entonces, devuelve ‘posición’ + 1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find lower_bound of x in
// prefix sums array using binary lifting.
#include <bits/stdc++.h>
using namespace std;
// function to make prefix sums array
void MakePreSum(int arr[], int presum[], int n)
{
presum[0] = arr[0];
for (int i = 1; i < n; i++)
presum[i] = presum[i - 1] + arr[i];
}
// function to find lower_bound of x in
// prefix sums array using binary lifting.
int BinaryLifting(int presum[], int n, int x)
{
// initialize position
int pos = 0;
// find log to the base 2 value of n.
int LOGN = log2(n);
// if x less than first number.
if (x <= presum[0])
return 0;
// starting from most significant bit.
for (int i = LOGN; i >= 0; i--) {
// if value at this position less
// than x then updateposition
// Here (1<<i) is similar to 2^i.
if (pos + (1 << i) < n &&
presum[pos + (1 << i)] < x) {
pos += (1 << i);
}
}
// +1 because 'pos' will have position
// of largest value less than 'x'
return pos + 1;
}
// Driver code
int main()
{
// given array
int arr[] = { 2, 5, 7, 1, 6, 9, 12, 4, 6 };
// value to find
int x = 8;
// size of array
int n = sizeof(arr) / sizeof(arr[0]);
// to store prefix sum
int presum[n] = { 0 };
// call for prefix sum
MakePreSum(arr, presum, n);
// function call
cout << BinaryLifting(presum, n, x);
return 0;
}
Java
// Java program to find lower_bound of x in
// prefix sums array using binary lifting.
import java.util.*;
class solution
{
// function to make prefix sums array
static void MakePreSum(int []arr, int []presum, int n)
{
presum[0] = arr[0];
for (int i = 1; i < n; i++)
presum[i] = presum[i - 1] + arr[i];
}
// function to find lower_bound of x in
// prefix sums array using binary lifting.
static int BinaryLifting(int []presum, int n, int x)
{
// initialize position
int pos = 0;
// find log to the base 2 value of n.
int LOGN = (int)Math.log(n);
// if x less than first number.
if (x <= presum[0])
return 0;
// starting from most significant bit.
for (int i = LOGN; i >= 0; i--) {
// if value at this position less
// than x then updateposition
// Here (1<<i) is similar to 2^i.
if (pos + (1 << i) < n &&
presum[pos + (1 << i)] < x) {
pos += (1 << i);
}
}
// +1 because 'pos' will have position
// of largest value less than 'x'
return pos + 1;
}
// Driver code
public static void main(String args[])
{
// given array
int []arr = { 2, 5, 7, 1, 6, 9, 12, 4, 6 };
// value to find
int x = 8;
// size of array
int n = arr.length;
// to store prefix sum
int []presum = new int[n];
Arrays.fill(presum,0);
// call for prefix sum
MakePreSum(arr, presum, n);
// function call
System.out.println(BinaryLifting(presum, n, x));
}
}
Python 3
# Python 3 program to find # lower_bound of x in prefix # sums array using binary lifting. import math # function to make prefix # sums array def MakePreSum( arr, presum, n): presum[0] = arr[0] for i in range(1, n): presum[i] = presum[i - 1] + arr[i] # function to find lower_bound of x in # prefix sums array using binary lifting. def BinaryLifting(presum, n, x): # initialize position pos = 0 # find log to the base 2 # value of n. LOGN = int(math.log2(n)) # if x less than first number. if (x <= presum[0]): return 0 # starting from most significant bit. for i in range(LOGN, -1, -1) : # if value at this position less # than x then updateposition # Here (1<<i) is similar to 2^i. if (pos + (1 << i) < n and presum[pos + (1 << i)] < x) : pos += (1 << i) # +1 because 'pos' will have position # of largest value less than 'x' return pos + 1 # Driver code if __name__ == "__main__": # given array arr = [ 2, 5, 7, 1, 6, 9, 12, 4, 6 ] # value to find x = 8 # size of array n = len(arr) # to store prefix sum presum = [0] * n # call for prefix sum MakePreSum(arr, presum, n) # function call print(BinaryLifting(presum, n, x)) # This code is contributed # by ChitraNayal
C#
// C# program to find lower_bound of x in
// prefix sums array using binary lifting.
using System;
class GFG
{
// function to make prefix sums array
static void MakePreSum(int []arr,
int []presum, int n)
{
presum[0] = arr[0];
for (int i = 1; i < n; i++)
presum[i] = presum[i - 1] + arr[i];
}
// function to find lower_bound of x in
// prefix sums array using binary lifting.
static int BinaryLifting(int []presum,
int n, int x)
{
// initialize position
int pos = 0;
// find log to the base 2 value of n.
int LOGN = (int)Math.Log(n);
// if x less than first number.
if (x <= presum[0])
return 0;
// starting from most significant bit.
for (int i = LOGN; i >= 0; i--)
{
// if value at this position less
// than x then updateposition
// Here (1<<i) is similar to 2^i.
if (pos + (1 << i) < n &&
presum[pos + (1 << i)] < x)
{
pos += (1 << i);
}
}
// +1 because 'pos' will have position
// of largest value less than 'x'
return pos + 1;
}
// Driver code
public static void Main()
{
// given array
int []arr = { 2, 5, 7, 1, 6, 9, 12, 4, 6 };
// value to find
int x = 8;
// size of array
int n = arr.Length;
// to store prefix sum
int []presum = new int[n];
// call for prefix sum
MakePreSum(arr, presum, n);
// function call
Console.WriteLine(BinaryLifting(presum, n, x));
}
}
// This code has been contributed
// by PrinciRaj1992
Javascript
<script>
// Javascript program to find lower_bound of x in
// prefix sums array using binary lifting.
// function to make prefix sums array
function MakePreSum(arr,presum,n)
{
presum[0] = arr[0];
for (let i = 1; i < n; i++)
presum[i] = presum[i - 1] + arr[i];
}
// function to find lower_bound of x in
// prefix sums array using binary lifting.
function BinaryLifting(presum, n,k)
{
// initialize position
let pos = 0;
// find log to the base 2 value of n.
let LOGN = Math.log(n);
// if x less than first number.
if (x <= presum[0])
return 0;
// starting from most significant bit.
for (let i = LOGN; i >= 0; i--) {
// if value at this position less
// than x then updateposition
// Here (1<<i) is similar to 2^i.
if (pos + (1 << i) < n &&
presum[pos + (1 << i)] < x) {
pos += (1 << i);
}
}
// +1 because 'pos' will have position
// of largest value less than 'x'
return pos + 1;
}
// Driver code
// given array
let arr=[2, 5, 7, 1, 6, 9, 12, 4, 6];
// value to find
let x = 8;
// size of array
let n = arr.length;
// to store prefix sum
let presum = new Array(n);
for(let i=0;i<n;i++)
{
presum[i]=0;
}
// call for prefix sum
MakePreSum(arr, presum, n);
// function call
document.write(BinaryLifting(presum, n, x));
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA