Dada una array arr[] que consta de N enteros y una array P[] que consta de M enteros tal que P[i] representa la puntuación obtenida al trabajar en el i- ésimo día . La tarea es encontrar la cantidad mínima de días necesarios para trabajar para lograr una puntuación de al menos arr[i] , para cada elemento de la array arr[i] .
Ejemplos:
Entrada: arr[] = {400, 200, 700}, P[] = {100, 300, 400, 500, 600}
Salida: 2 2 3 4 5
Explicación:
Los siguientes son el número de días necesarios para cada elemento de la array:
- arr[0](= 400): Para ganar 400 puntos, uno tiene que trabajar durante los primeros 2 días haciendo que el total de puntos sea igual a 100 + 300 = 400(>= arr[0]).
- arr[1](= 200): Para ganar 200 puntos uno tiene que trabajar durante los primeros 2 días haciendo un total de puntos = 100 + 300 = 400(>= arr[1]).
- arr[2](= 700): Para ganar 700 puntos uno tiene que trabajar durante los primeros 3 días haciendo un total de puntos = 100 + 300 + 400 = 800(>= arr[2]).
Entrada: arr[] = {1400}, P[] = {100, 300}
Salida: -1
Enfoque ingenuo: el enfoque más simple para resolver el problema es atravesar la array arr[] y, para cada array, el elemento encuentra el índice mínimo de la array P[] tal que la suma de la subarreglo sobre el rango [0, i] es al menos arr[i] .
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar encontrando la array de suma de prefijos de P[] y luego usando la búsqueda binaria para encontrar la suma cuyo valor es al menos arr[i] . Siga los pasos a continuación para resolver el problema:
- Encuentre la array de suma de prefijos de la array P[] .
- Recorra la array dada arr[] y realice los siguientes pasos:
- Encuentre el índice del primer elemento mayor que el elemento actual arr[i] en la array P[] y guárdelo en una variable, digamos index .
- Si el valor del índice es -1 , imprima -1 . De lo contrario, imprima el valor de (índice + 1) como resultado del índice actual.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the lower bound
// of N using binary search
int binarySeach(vector<int> P, int N)
{
// Stores the lower bound
int i = 0;
// Stores the upper bound
int j = P.size() - 1;
// Stores the minimum index
// having value is at least N
int index = -1;
// Iterator while i<=j
while (i <= j)
{
// Stores the mid index
// of the range [i, j]
int mid = i + (j - i) / 2;
// If P[mid] is at least N
if (P[mid] >= N)
{
// Update the value of
// mid to index
index = mid;
// Update the value of j
j = mid - 1;
}
// Update the value of i
else
{
i = mid + 1;
}
}
// Return the resultant index
return index;
}
// Function to find the minimum number
// of days required to work to at least
// arr[i] points for every array element
void minDays(vector<int> P, vector<int> arr)
{
// Traverse the array P[]
for(int i = 1; i < P.size(); i++)
{
// Find the prefix sum
P[i] += P[i] + P[i - 1];
}
// Traverse the array arr[]
for(int i = 0; i < arr.size(); i++)
{
// Find the minimum index of
// the array having value
// at least arr[i]
int index = binarySeach(P, arr[i]);
// If the index is not -1
if (index != -1)
{
cout << index + 1 << " ";
}
// Otherwise
else
{
cout << -1 << " ";
}
}
}
// Driver Code
int main()
{
vector<int> arr = { 400, 200, 700, 900, 1400 };
vector<int> P = { 100, 300, 400, 500, 600 };
minDays(P, arr);
return 0;
}
// This code is contributed by nirajgusain5
Java
// Java program for the above approach
public class GFG {
// Function to find the minimum number
// of days required to work to at least
// arr[i] points for every array element
static void minDays(int[] P, int[] arr)
{
// Traverse the array P[]
for (int i = 1; i < P.length; i++) {
// Find the prefix sum
P[i] += P[i] + P[i - 1];
}
// Traverse the array arr[]
for (int i = 0;
i < arr.length; i++) {
// Find the minimum index of
// the array having value
// at least arr[i]
int index = binarySeach(
P, arr[i]);
// If the index is not -1
if (index != -1) {
System.out.print(
index + 1 + " ");
}
// Otherwise
else {
System.out.print(
-1 + " ");
}
}
}
// Function to find the lower bound
// of N using binary search
static int binarySeach(
int[] P, int N)
{
// Stores the lower bound
int i = 0;
// Stores the upper bound
int j = P.length - 1;
// Stores the minimum index
// having value is at least N
int index = -1;
// Iterator while i<=j
while (i <= j) {
// Stores the mid index
// of the range [i, j]
int mid = i + (j - i) / 2;
// If P[mid] is at least N
if (P[mid] >= N) {
// Update the value of
// mid to index
index = mid;
// Update the value of j
j = mid - 1;
}
// Update the value of i
else {
i = mid + 1;
}
}
// Return the resultant index
return index;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 400, 200, 700, 900, 1400 };
int[] P = { 100, 300, 400, 500, 600 };
minDays(P, arr);
}
}
Python3
# Python3 program for the above approach # Function to find the minimum number # of days required to work to at least # arr[i] points for every array element def minDays(P, arr): # Traverse the array P[] for i in range(1, len(P)): # Find the prefix sum P[i] += P[i] + P[i - 1] # Traverse the array arr[] for i in range(len(arr)): # Find the minimum index of # the array having value # at least arr[i] index = binarySeach(P, arr[i]) # If the index is not -1 if (index != -1): print(index + 1, end = " ") # Otherwise else: print(-1, end = " ") # Function to find the lower bound # of N using binary search def binarySeach(P, N): # Stores the lower bound i = 0 # Stores the upper bound j = len(P) - 1 # Stores the minimum index # having value is at least N index = -1 # Iterator while i<=j while (i <= j): # Stores the mid index # of the range [i, j] mid = i + (j - i) // 2 # If P[mid] is at least N if (P[mid] >= N): # Update the value of # mid to index index = mid # Update the value of j j = mid - 1 # Update the value of i else: i = mid + 1 # Return the resultant index return index # Driver Code if __name__ == '__main__': arr = [400, 200, 700,900,1400 ] P = [100, 300, 400, 500, 600 ] minDays(P, arr) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG{
// Function to find the minimum number
// of days required to work to at least
// arr[i] points for every array element
static void minDays(int[] P, int[] arr)
{
// Traverse the array P[]
for(int i = 1; i < P.Length; i++)
{
// Find the prefix sum
P[i] += P[i] + P[i - 1];
}
// Traverse the array arr[]
for(int i = 0; i < arr.Length; i++)
{
// Find the minimum index of
// the array having value
// at least arr[i]
int index = binarySeach(P, arr[i]);
// If the index is not -1
if (index != -1)
{
Console.Write(index + 1 + " ");
}
// Otherwise
else
{
Console.Write(-1 + " ");
}
}
}
// Function to find the lower bound
// of N using binary search
static int binarySeach(int[] P, int N)
{
// Stores the lower bound
int i = 0;
// Stores the upper bound
int j = P.Length - 1;
// Stores the minimum index
// having value is at least N
int index = -1;
// Iterator while i<=j
while (i <= j)
{
// Stores the mid index
// of the range [i, j]
int mid = i + (j - i) / 2;
// If P[mid] is at least N
if (P[mid] >= N)
{
// Update the value of
// mid to index
index = mid;
// Update the value of j
j = mid - 1;
}
// Update the value of i
else
{
i = mid + 1;
}
}
// Return the resultant index
return index;
}
// Driver Code
public static void Main(string[] args)
{
int[] arr = { 400, 200, 700, 900, 1400 };
int[] P = { 100, 300, 400, 500, 600 };
minDays(P, arr);
}
}
// This code is contributed by ukasp
Javascript
<script>
// JavaScript program for the above approach
// Function to find the lower bound
// of N using binary search
function binarySeach(P, N)
{
// Stores the lower bound
var i = 0;
// Stores the upper bound
var j = P.length - 1;
// Stores the minimum index
// having value is at least N
var index = -1;
// Iterator while i<=j
while (i <= j)
{
// Stores the mid index
// of the range [i, j]
var mid = i + parseInt((j - i) / 2);
// If P[mid] is at least N
if (P[mid] >= N)
{
// Update the value of
// mid to index
index = mid;
// Update the value of j
j = mid - 1;
}
// Update the value of i
else
{
i = mid + 1;
}
}
// Return the resultant index
return index;
}
// Function to find the minimum number
// of days required to work to at least
// arr[i] points for every array element
function minDays(P, arr)
{
// Traverse the array P[]
for(var i = 1; i < P.length; i++)
{
// Find the prefix sum
P[i] += P[i] + P[i - 1];
}
// Traverse the array arr[]
for(var i = 0; i < arr.length; i++)
{
// Find the minimum index of
// the array having value
// at least arr[i]
var index = binarySeach(P, arr[i]);
// If the index is not -1
if (index != -1)
{
document.write( (index + 1) + " ");
}
// Otherwise
else
{
document.write( -1 + " ");
}
}
}
// Driver Code
var arr = [400, 200, 700, 900, 1400];
var P = [100, 300, 400, 500, 600];
minDays(P, arr);
</script>
Producción:
2 2 2 3 3
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)