Dada una array arr[] y brr[], ambas formadas por N enteros y un entero positivo K , la tarea es encontrar el valor mínimo de X tal que la suma del máximo de (arr[i] – X, 0) aumente a la potencia de brr[i] para todos los elementos de la array (arr[i], brr[i]) es como máximo K .
Ejemplos:
Entrada: arr[] = {2, 1, 4, 3, 5} brr[] = { 4, 3, 2, 3, 1}, K = 12
Salida: 2
Explicación:
Considere el valor de X como 2, luego el valor de la expresión dada es:
=> max(2 – 2, 0) 4 + max(1 – 2, 0) 3 + max(4 – 2, 0) 2 + max(3 – 2, 0) 3 + max(5 – 2, 0) 1
=> 0 4 + 0 3 + 2 2 + 1 3 + 3 1 = 8 <= K(= 12).
Por lo tanto, el valor resultante de X es 2, que es mínimo.Entrada: arr[] = {2, 1, 4, 3, 5} brr[] = { 4, 3, 2, 3, 1}, K = 22
Salida: 1
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es verificar cada valor de X desde 0 hasta el elemento máximo de la array y si existe algún valor de X que satisfaga las condiciones dadas, luego imprima ese valor de X y rompa del bucle .
Complejidad temporal: O(N*M), donde M es el elemento máximo del arreglo .
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando la búsqueda binaria para encontrar el valor de X y si un valor particular de X satisface la condición anterior, todos los valores mayores también cumplirán, por lo tanto, intente buscar valores más bajos. valores. Siga los pasos a continuación para resolver el problema:
- Defina una función check(a[], b[], k, n, x):
- Inicialice la variable sum como 0 para calcular la suma deseada de la array arr[] y brr[].
- Itere sobre el rango [0, N] usando la variable i y agregue el valor de pow(max(arr[i] – x, 0), brr[i]) a la variable sum .
- Si el valor de sum es menor que igual a K , entonces devuelve true . De lo contrario, devuelve falso .
- Inicialice las variables, digamos bajo como 0 y alto como valor máximo de la array.
- Iterar en un bucle while hasta que el nivel bajo sea menor que el nivel alto y realizar los siguientes pasos:
- Inicialice la variable mid como el promedio de low y high .
- Verifique el valor de mid para ver si satisface las condiciones dadas llamando a la función check(arr[], brr[], k, n, mid) .
- Si la función check(arr[], brr[], n, k, mid) devuelve verdadero , entonces actualice high to mid . De lo contrario, actualice el valor de bajo a (medio + 1) .
- Después de completar los pasos anteriores, devuelva el valor de bajo como resultado de la función.
- Después de realizar los pasos anteriores, imprima el valor de bajo como el valor deseado de X como respuesta.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if there exists an
// X that satisfies the given conditions
bool check(int a[], int b[], int k, int n, int x)
{
int sum = 0;
// Find the required value of the
// given expression
for (int i = 0; i < n; i++) {
sum = sum + pow(max(a[i] - x, 0), b[i]);
}
if (sum <= k)
return true;
else
return false;
}
// Function to find the minimum value
// of X using binary search.
int findMin(int a[], int b[], int n, int k)
{
// Boundaries of the Binary Search
int l = 0, u = *max_element(a, a + n);
while (l < u) {
// Find the middle value
int m = (l + u) / 2;
// Check for the middle value
if (check(a, b, k, n, m)) {
// Update the upper
u = m;
}
else {
// Update the lower
l = m + 1;
}
}
return l;
}
// Driver Code
int main()
{
int arr[] = { 2, 1, 4, 3, 5 };
int brr[] = { 4, 3, 2, 3, 1 };
int K = 12;
int N = sizeof(arr) / sizeof(arr[0]);
cout << findMin(arr, brr, N, K);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to check if it is possible to
// get desired result
static boolean check(int a[], int b[], int k, int x)
{
int sum = 0;
for(int i = 0; i < a.length; i++)
{
sum = sum + (int)Math.pow(
Math.max(a[i] - x, 0), b[i]);
}
if (sum <= k)
return true;
else
return false;
}
// Function to find the minimum value
// of X using binary search.
static int findMin(int a[], int b[], int n, int k)
{
// Boundaries of the Binary Search
int l = 0, u = (int)1e9;
while (l < u)
{
// Find the middle value
int m = (l + u) / 2;
// Check for the middle value
if (check(a, b, k, m))
// Update the upper
u = m;
else
// Update the lower
l = m + 1;
}
return l;
}
// Driver code
public static void main(String[] args)
{
int n = 5;
int k = 12;
int a[] = { 2, 1, 4, 3, 5 };
int b[] = { 4, 3, 2, 3, 1 };
System.out.println(findMin(a, b, n, k));
}
}
// This code is contributed by ayush_dragneel
Python3
# Python 3 program for the above approach # Function to check if there exists an # X that satisfies the given conditions def check(a, b, k, n, x): sum = 0 # Find the required value of the # given expression for i in range(n): sum = sum + pow(max(a[i] - x, 0), b[i]) if (sum <= k): return True else: return False # Function to find the minimum value # of X using binary search. def findMin(a, b, n, k): # Boundaries of the Binary Search l = 0 u = max(a) while (l < u): # Find the middle value m = (l + u) // 2 # Check for the middle value if (check(a, b, k, n, m)): # Update the upper u = m else: # Update the lower l = m + 1 return l # Driver Code if __name__ == '__main__': arr = [2, 1, 4, 3, 5] brr = [4, 3, 2, 3, 1] K = 12 N = len(arr) print(findMin(arr, brr, N, K)) # This code is contributed by ipg2016107.
C#
// C# program for the above approach
using System;
public class GFG{
// Function to check if it is possible to
// get desired result
static bool check(int []a, int []b, int k, int x)
{
int sum = 0;
for(int i = 0; i < a.Length; i++)
{
sum = sum + (int)Math.Pow(
Math.Max(a[i] - x, 0), b[i]);
}
if (sum <= k)
return true;
else
return false;
}
// Function to find the minimum value
// of X using binary search.
static int findMin(int []a, int []b, int n, int k)
{
// Boundaries of the Binary Search
int l = 0, u = (int)1e9;
while (l < u)
{
// Find the middle value
int m = (l + u) / 2;
// Check for the middle value
if (check(a, b, k, m))
// Update the upper
u = m;
else
// Update the lower
l = m + 1;
}
return l;
}
// Driver code
public static void Main(String[] args)
{
int n = 5;
int k = 12;
int []a = { 2, 1, 4, 3, 5 };
int []b = { 4, 3, 2, 3, 1 };
Console.WriteLine(findMin(a, b, n, k));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript program for the above approache9 + 7;
// Function to check if there exists an
// X that satisfies the given conditions
function check(a, b, k, n, x) {
let sum = 0;
// Find the required value of the
// given expression
for (let i = 0; i < n; i++) {
sum = sum + Math.pow(Math.max(a[i] - x, 0), b[i]);
}
if (sum <= k)
return true;
else
return false;
}
function max_element(a) {
let maxi = Number.MIN_VALUE;
for (let i = 0; i < a.length; i++) {
if (a[i] > maxi) {
maxi = a[i];
}
}
return maxi;
}
// Function to find the minimum value
// of X using binary search.
function findMin(a, b, n, k) {
// Boundaries of the Binary Search
let l = 0, u = max_element(a);
while (l < u) {
// Find the middle value
let m = Math.floor((l + u) / 2);
// Check for the middle value
if (check(a, b, k, n, m)) {
// Update the upper
u = m;
}
else {
// Update the lower
l = m + 1;
}
}
return l;
}
// Driver Code
let arr = [2, 1, 4, 3, 5];
let brr = [4, 3, 2, 3, 1];
let K = 12;
let N = arr.length;
document.write(findMin(arr, brr, N, K));
// This code is contributed by Potta Lokesh
</script>
2
Complejidad temporal: O(N*log M), donde M es el elemento máximo del arreglo .
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por ayush_dragneel y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA