Dada una array de n elementos. La tarea es encontrar el número de sextillizos que satisfagan la siguiente ecuación de modo que a, b, c, d, e y f pertenezcan a la array dada:
a * b + c - e = f
d
Ejemplos:
Input : arr[] = { 1 }.
Output : 1
a = b = c = d = e = f = 1 satisfy
the equation.
Input : arr[] = { 2, 3 }
Output : 4
Input : arr[] = { 1, -1 }
Output : 24
Primero, reordena la ecuación, a * b + c = (f + e) * d.
Ahora, haga dos arrays, una para LHS (lado izquierdo) de la ecuación y otra para RHS (lado derecho) de la ecuación. Busque cada elemento de la array de RHS en la array de LHS. Cada vez que encuentre un valor de RHS en LHS, verifique cuántas veces se repite en LHS y agregue esa cuenta al total. La búsqueda se puede realizar mediante búsqueda binaria, ordenando la array LHS.
A continuación se muestra la implementación de este enfoque:
C++
// C++ program to count of 6 values from an array
// that satisfy an equation with 6 variables
#include<bits/stdc++.h>
using namespace std;
// Returns count of 6 values from arr[]
// that satisfy an equation with 6 variables
int findSextuplets(int arr[], int n)
{
// Generating possible values of RHS of the equation
int index = 0;
int RHS[n*n*n + 1];
for (int i = 0; i < n; i++)
if (arr[i]) // Checking d should be non-zero.
for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
RHS[index++] = arr[i] * (arr[j] + arr[k]);
// Sort RHS[] so that we can do binary search in it.
sort(RHS, RHS + n);
// Generating all possible values of LHS of the equation
// and finding the number of occurrences of the value in RHS.
int result = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for(int k = 0; k < n; k++)
{
int val = arr[i] * arr[j] + arr[k];
result += (upper_bound(RHS, RHS + index, val) -
lower_bound(RHS, RHS + index, val));
}
}
}
return result;
}
// Driven Program
int main()
{
int arr[] = {2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
cout << findSextuplets(arr, n) << endl;
return 0;
}
Java
// Java program to count of 6 values from an array
// that satisfy an equation with 6 variables
import java.util.Arrays;
class GFG{
static int upper_bound(int[] array, int length, int value) {
int low = 0;
int high = length;
while (low < high) {
final int mid = (low + high) / 2;
if (value >= array[mid]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
static int lower_bound(int[] array, int length, int value) {
int low = 0;
int high = length;
while (low < high) {
final int mid = (low + high) / 2;
if (value <= array[mid]) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
static int findSextuplets(int[] arr, int n)
{
// Generating possible values of RHS of the equation
int index = 0;
int[] RHS = new int[n * n * n + 1];
for (int i = 0; i < n; i++)
{
if (arr[i] != 0) // Checking d should be non-zero.
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
RHS[index++] = arr[i] * (arr[j] + arr[k]);
}
}
}
}
// Sort RHS[] so that we can do binary search in it.
Arrays.sort(RHS);
// Generating all possible values of LHS of the equation
// and finding the number of occurrences of the value in RHS.
int result = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
int val = arr[i] * arr[j] + arr[k];
result += (upper_bound(RHS, index, val)-lower_bound(RHS, index, val));
}
}
}
return result;
}
// Driven Program
public static void main(String[] args)
{
int[] arr = {2, 3};
int n = arr.length;
System.out.println(findSextuplets(arr, n));
}
}
// This code is contributed by mits
Python3
# Python3 program to count of 6 values # from an array that satisfy an equation # with 6 variables def upper_bound(array, length, value): low = 0; high = length; while (low < high): mid = int((low + high) / 2); if (value >= array[mid]): low = mid + 1; else: high = mid; return low; def lower_bound(array, length, value): low = 0; high = length; while (low < high): mid = int((low + high) / 2); if (value <= array[mid]): high = mid; else: low = mid + 1; return low; def findSextuplets(arr, n): # Generating possible values of # RHS of the equation index = 0; RHS = [0] * (n * n * n + 1); for i in range(n): if (arr[i] != 0): # Checking d should be non-zero. for j in range(n): for k in range(n): RHS[index] = arr[i] * (arr[j] + arr[k]); index += 1; # Sort RHS[] so that we can do # binary search in it. RHS.sort(); # Generating all possible values of # LHS of the equation and finding the # number of occurrences of the value in RHS. result = 0; for i in range(n): for j in range(n): for k in range(n): val = arr[i] * arr[j] + arr[k]; result += (upper_bound(RHS, index, val) - lower_bound(RHS, index, val)); return result; # Driver Code arr = [2, 3]; n = len(arr); print(findSextuplets(arr, n)); # This code is contributed by mits
C#
// C# program to count of 6 values from an array
// that satisfy an equation with 6 variables
using System;
using System.Collections;
class GFG{
static int upper_bound(int[] array, int length, int value) {
int low = 0;
int high = length;
while (low < high) {
int mid = (low + high) / 2;
if (value >= array[mid]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
static int lower_bound(int[] array, int length, int value) {
int low = 0;
int high = length;
while (low < high) {
int mid = (low + high) / 2;
if (value <= array[mid]) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
static int findSextuplets(int[] arr, int n)
{
// Generating possible values of RHS of the equation
int index = 0;
int[] RHS = new int[n * n * n + 1];
for (int i = 0; i < n; i++)
{
if (arr[i] != 0) // Checking d should be non-zero.
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
RHS[index++] = arr[i] * (arr[j] + arr[k]);
}
}
}
}
// Sort RHS[] so that we can do binary search in it.
Array.Sort(RHS);
// Generating all possible values of LHS of the equation
// and finding the number of occurrences of the value in RHS.
int result = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
for (int k = 0; k < n; k++)
{
int val = arr[i] * arr[j] + arr[k];
result += (upper_bound(RHS, index, val)-lower_bound(RHS, index, val));
}
}
}
return result;
}
// Driven Program
static void Main()
{
int[] arr = {2, 3};
int n = arr.Length;
Console.WriteLine(findSextuplets(arr, n));
}
}
// This code is contributed by mits
PHP
<?php
// PHP program to count of 6 values from
// an array that satisfy an equation
// with 6 variables
function upper_bound($array, $length, $value)
{
$low = 0;
$high = $length;
while ($low < $high)
{
$mid = (int)(($low + $high) / 2);
if ($value >= $array[$mid])
$low = $mid + 1;
else
$high = $mid;
}
return $low;
}
function lower_bound($array, $length, $value)
{
$low = 0;
$high = $length;
while ($low < $high)
{
$mid = (int)(($low + $high) / 2);
if ($value <= $array[$mid])
$high = $mid;
else
$low = $mid + 1;
}
return $low;
}
// Returns count of 6 values from arr[]
// that satisfy an equation with 6 variables
function findSextuplets($arr, $n)
{
// Generating possible values of
// RHS of the equation
$index = 0;
$RHS = array_fill(0, $n * $n * $n + 1, 0);
for ($i = 0; $i < $n; $i++)
if ($arr[$i] != 0) // Checking d should be non-zero.
for ($j = 0; $j < $n; $j++)
for ($k = 0; $k < $n; $k++)
$RHS[$index++] = $arr[$i] *
($arr[$j] + $arr[$k]);
// Sort RHS[] so that we can do
// binary search in it.
sort($RHS);
// Generating all possible values of LHS
// of the equation and finding the number
// of occurrences of the value in RHS.
$result = 0;
for ($i = 0; $i < $n; $i++)
for ($j = 0; $j < $n; $j++)
for ($k = 0; $k < $n; $k++)
{
$val = $arr[$i] * $arr[$j] + $arr[$k];
$result += (upper_bound($RHS, $index, $val) -
lower_bound($RHS, $index, $val));
}
return $result;
}
// Driver Code
$arr = array(2, 3);
$n = count($arr);
print(findSextuplets($arr, $n));
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to count of
// 6 values from an array
// that satisfy an equation with
// 6 variables
function upper_bound(array , length , value)
{
var low = 0;
var high = length;
while (low < high) {
var mid = parseInt((low + high) / 2);
if (value >= array[mid]) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
function lower_bound(array , length , value)
{
var low = 0;
var high = length;
while (low < high) {
var mid = parseInt((low + high) / 2);
if (value <= array[mid]) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
function findSextuplets(arr , n)
{
// Generating possible values of
// RHS of the equation
var index = 0;
var RHS = Array.from({length: n * n * n + 1},
(_, i) => 0);
for (i = 0; i < n; i++)
{
// Checking d should be non-zero.
if (arr[i] != 0)
{
for (j = 0; j < n; j++)
{
for (k = 0; k < n; k++)
{
RHS[index++] = arr[i] *
(arr[j] + arr[k]);
}
}
}
}
// Sort RHS so that we can do
// binary search in it.
RHS.sort((a,b)=>a-b);
// Generating all possible values
// of LHS of the equation
// and finding the number of occurrences
// of the value in RHS.
var result = 0;
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
for (k = 0; k < n; k++)
{
var val = arr[i] * arr[j] + arr[k];
result += (upper_bound(RHS, index, val)-
lower_bound(RHS, index, val));
}
}
}
return result;
}
// Driven Program
var arr = [2, 3];
var n = arr.length;
document.write(findSextuplets(arr, n));
// This code is contributed by 29AjayKumar
</script>
Producción:
4
Complejidad de tiempo: O (N 3 log N)
Este artículo es una contribución de Anuj Chauhan(anuj0503) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA