Dada una array arr[] de N elementos, la tarea es encontrar el recuento de tripletes (arr[i], arr[j], arr[k]) tales que (arr[i] + arr[j] + arr[ k] = L) y (L % arr[i] = L % arr[j] = L % arr[k] = 0 .
Ejemplos:
Entrada: arr[] = {2, 4, 5, 6, 7}
Salida: 1
El único triplete posible es {2, 4, 6}
Entrada: arr[] = {4, 4, 4, 4, 4}
Salida: 10
Acercarse:
- Considere las siguientes ecuaciones:
L = a * arr[i] , L = b * arr[j] y L = c * arr[k] .
Así, arr[i] = L/a , arr[j] = L/b y arr[k] = L/c .
Entonces, usar esto en arr[i] + arr[j] + arr[k] = L da L / a + L / b + L / c = L
o 1 / a + 1 / b + 1 / c = 1 .
Ahora, solo puede haber 10 soluciones posibles de la ecuación anterior, que son
{2, 3, 6}
{2, 4, 4}
{2, 6, 3}
{3, 2, 6}
{3, 3, 3 }
{3, 6, 2}
{4, 2, 4}
{4, 4, 2}
{6, 2, 3}
{6, 3, 2}
Todos los tripletes posibles(arr[i], arr[j], arr[k]) satisfará estas soluciones. Entonces, todas estas soluciones se pueden almacenar en una array 2D, digamos test[][3] . Entonces, se pueden encontrar todos los tripletes que satisfacen estas soluciones.
- Para todo i de 1 a N . Considere arr[i] como el elemento central del triplete. Y encuentre los elementos primero y tercero correspondientes del triplete para todas las soluciones posibles de la ecuación 1 / a + 1 / b + 1 / c = 1 . Encuentre la respuesta para todos los casos y agréguelos a la respuesta final.
- Mantenga los índices donde aparece arr[i] en la array. Para una posible solución dada de la ecuación X y para cada número arr[i] mantenga el número como elemento central del triplete y encuentre el primer y el tercer elemento. Aplique la búsqueda binaria en el conjunto disponible de índices para el primer y el tercer elemento para encontrar el número de ocurrencias del primer elemento de 1 a i – 1 y el número de ocurrencias del tercer elemento de i + 1 a N . Multiplica ambos valores y súmalo a la respuesta final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define MAX 100001
#define ROW 10
#define COl 3
vector<int> indices[MAX];
// All possible solutions of the
// equation 1/a + 1/b + 1/c = 1
int test[ROW][COl] = { { 2, 3, 6 },
{ 2, 4, 4 },
{ 2, 6, 3 },
{ 3, 2, 6 },
{ 3, 3, 3 },
{ 3, 6, 2 },
{ 4, 2, 4 },
{ 4, 4, 2 },
{ 6, 2, 3 },
{ 6, 3, 2 } };
// Function to find the triplets
int find_triplet(int array[], int n)
{
int answer = 0;
// Storing indices of the elements
for (int i = 0; i < n; i++) {
indices[array[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
int y = array[i];
for (int j = 0; j < ROW; j++) {
int s = test[j][1] * y;
// Check if y can act as the middle
// element of triplet with the given
// solution of 1/a + 1/b + 1/c = 1
if (s % test[j][0] != 0)
continue;
if (s % test[j][2] != 0)
continue;
int x = s / test[j][0];
ll z = s / test[j][2];
if (x > MAX || z > MAX)
continue;
int l = 0;
int r = indices[x].size() - 1;
int first = -1;
// Binary search to find the number of
// possible values of the first element
while (l <= r) {
int m = (l + r) / 2;
if (indices[x][m] < i) {
first = m;
l = m + 1;
}
else {
r = m - 1;
}
}
l = 0;
r = indices[z].size() - 1;
int third = -1;
// Binary search to find the number of
// possible values of the third element
while (l <= r) {
int m = (l + r) / 2;
if (indices[z][m] > i) {
third = m;
r = m - 1;
}
else {
l = m + 1;
}
}
if (first != -1 && third != -1) {
// Contribution to the answer would
// be the multiplication of the possible
// values for the first and the third element
answer += (first + 1) * (indices[z].size() - third);
}
}
}
return answer;
}
// Driver code
int main()
{
int array[] = { 2, 4, 5, 6, 7 };
int n = sizeof(array) / sizeof(array[0]);
cout << find_triplet(array, n);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static int MAX = 100001;
static int ROW = 10;
static int COl = 3;
static Vector<Integer> []indices = new Vector[MAX];
// All possible solutions of the
// equation 1/a + 1/b + 1/c = 1
static int test[][] = { { 2, 3, 6 }, { 2, 4, 4 },
{ 2, 6, 3 }, { 3, 2, 6 },
{ 3, 3, 3 }, { 3, 6, 2 },
{ 4, 2, 4 }, { 4, 4, 2 },
{ 6, 2, 3 }, { 6, 3, 2 } };
// Function to find the triplets
static int find_triplet(int array[], int n)
{
int answer = 0;
for (int i = 0; i < MAX; i++)
{
indices[i] = new Vector<>();
}
// Storing indices of the elements
for (int i = 0; i < n; i++)
{
indices[array[i]].add(i);
}
for (int i = 0; i < n; i++)
{
int y = array[i];
for (int j = 0; j < ROW; j++)
{
int s = test[j][1] * y;
// Check if y can act as the middle
// element of triplet with the given
// solution of 1/a + 1/b + 1/c = 1
if (s % test[j][0] != 0)
continue;
if (s % test[j][2] != 0)
continue;
int x = s / test[j][0];
int z = s / test[j][2];
if (x > MAX || z > MAX)
continue;
int l = 0;
int r = indices[x].size() - 1;
int first = -1;
// Binary search to find the number of
// possible values of the first element
while (l <= r)
{
int m = (l + r) / 2;
if (indices[x].get(m) < i)
{
first = m;
l = m + 1;
}
else
{
r = m - 1;
}
}
l = 0;
r = indices[z].size() - 1;
int third = -1;
// Binary search to find the number of
// possible values of the third element
while (l <= r)
{
int m = (l + r) / 2;
if (indices[z].get(m) > i)
{
third = m;
r = m - 1;
}
else
{
l = m + 1;
}
}
if (first != -1 && third != -1)
{
// Contribution to the answer would
// be the multiplication of the possible
// values for the first and the third element
answer += (first + 1) * (indices[z].size() - third);
}
}
}
return answer;
}
// Driver code
public static void main(String []args)
{
int array[] = { 2, 4, 5, 6, 7 };
int n = array.length;
System.out.println(find_triplet(array, n));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach MAX = 100001 ROW = 10 COL = 3 indices = [0] * MAX # All possible solutions of the # equation 1/a + 1/b + 1/c = 1 test = [[2, 3, 6], [2, 4, 4], [2, 6, 3], [3, 2, 6], [3, 3, 3], [3, 6, 2], [4, 2, 4], [4, 4, 2], [6, 2, 3], [6, 3, 2]] # Function to find the triplets def find_triplet(array, n): answer = 0 for i in range(MAX): indices[i] = [] # Storing indices of the elements for i in range(n): indices[array[i]].append(i) for i in range(n): y = array[i] for j in range(ROW): s = test[j][1] * y # Check if y can act as the middle # element of triplet with the given # solution of 1/a + 1/b + 1/c = 1 if s % test[j][0] != 0: continue if s % test[j][2] != 0: continue x = s // test[j][0] z = s // test[j][2] if x > MAX or z > MAX: continue l = 0 r = len(indices[x]) - 1 first = -1 # Binary search to find the number of # possible values of the first element while l <= r: m = (l + r) // 2 if indices[x][m] < i: first = m l = m + 1 else: r = m - 1 l = 0 r = len(indices[z]) - 1 third = -1 # Binary search to find the number of # possible values of the third element while l <= r: m = (l + r) // 2 if indices[z][m] > i: third = m r = m - 1 else: l = m + 1 if first != -1 and third != -1: # Contribution to the answer would # be the multiplication of the possible # values for the first and the third element answer += (first + 1) * (len(indices[z]) - third) return answer # Driver Code if __name__ == "__main__": array = [2, 4, 5, 6, 7] n = len(array) print(find_triplet(array, n)) # This code is contributed by # sanjeev2552
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
static int MAX = 100001;
static int ROW = 10;
static int COl = 3;
static List<int> []indices = new List<int>[MAX];
// All possible solutions of the
// equation 1/a + 1/b + 1/c = 1
static int [,]test = { { 2, 3, 6 }, { 2, 4, 4 },
{ 2, 6, 3 }, { 3, 2, 6 },
{ 3, 3, 3 }, { 3, 6, 2 },
{ 4, 2, 4 }, { 4, 4, 2 },
{ 6, 2, 3 }, { 6, 3, 2 } };
// Function to find the triplets
static int find_triplet(int []array, int n)
{
int answer = 0;
for (int i = 0; i < MAX; i++)
{
indices[i] = new List<int>();
}
// Storing indices of the elements
for (int i = 0; i < n; i++)
{
indices[array[i]].Add(i);
}
for (int i = 0; i < n; i++)
{
int y = array[i];
for (int j = 0; j < ROW; j++)
{
int s = test[j, 1] * y;
// Check if y can act as the middle
// element of triplet with the given
// solution of 1/a + 1/b + 1/c = 1
if (s % test[j, 0] != 0)
continue;
if (s % test[j, 2] != 0)
continue;
int x = s / test[j, 0];
int z = s / test[j, 2];
if (x > MAX || z > MAX)
continue;
int l = 0;
int r = indices[x].Count - 1;
int first = -1;
// Binary search to find the number of
// possible values of the first element
while (l <= r)
{
int m = (l + r) / 2;
if (indices[x][m] < i)
{
first = m;
l = m + 1;
}
else
{
r = m - 1;
}
}
l = 0;
r = indices[z].Count - 1;
int third = -1;
// Binary search to find the number of
// possible values of the third element
while (l <= r)
{
int m = (l + r) / 2;
if (indices[z][m] > i)
{
third = m;
r = m - 1;
}
else
{
l = m + 1;
}
}
if (first != -1 && third != -1)
{
// Contribution to the answer would
// be the multiplication of the possible
// values for the first and the third element
answer += (first + 1) * (indices[z].Count - third);
}
}
}
return answer;
}
// Driver code
public static void Main(String []args)
{
int []array = { 2, 4, 5, 6, 7 };
int n = array.Length;
Console.WriteLine(find_triplet(array, n));
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the approach
var MAX = 100001
var ROW = 10
var COl = 3
var indices = Array.from(Array(MAX), ()=>new Array());
// All possible solutions of the
// equation 1/a + 1/b + 1/c = 1
var test = [ [ 2, 3, 6 ],
[ 2, 4, 4 ],
[ 2, 6, 3 ],
[ 3, 2, 6 ],
[ 3, 3, 3 ],
[ 3, 6, 2 ],
[ 4, 2, 4 ],
[ 4, 4, 2 ],
[ 6, 2, 3 ],
[ 6, 3, 2 ] ];
// Function to find the triplets
function find_triplet(array, n)
{
var answer = 0;
// Storing indices of the elements
for (var i = 0; i < n; i++) {
indices[array[i]].push(i);
}
for (var i = 0; i < n; i++) {
var y = array[i];
for (var j = 0; j < ROW; j++) {
var s = test[j][1] * y;
// Check if y can act as the middle
// element of triplet with the given
// solution of 1/a + 1/b + 1/c = 1
if (s % test[j][0] != 0)
continue;
if (s % test[j][2] != 0)
continue;
var x = s / test[j][0];
var z = s / test[j][2];
if (x > MAX || z > MAX)
continue;
var l = 0;
var r = indices[x].length - 1;
var first = -1;
// Binary search to find the number of
// possible values of the first element
while (l <= r) {
var m = (l + r) / 2;
if (indices[x][m] < i) {
first = m;
l = m + 1;
}
else {
r = m - 1;
}
}
l = 0;
r = indices[z].length - 1;
var third = -1;
// Binary search to find the number of
// possible values of the third element
while (l <= r) {
var m = (l + r) / 2;
if (indices[z][m] > i) {
third = m;
r = m - 1;
}
else {
l = m + 1;
}
}
if (first != -1 && third != -1) {
// Contribution to the answer would
// be the multiplication of the possible
// values for the first and the third element
answer += (first + 1) * (indices[z].length - third);
}
}
}
return answer;
}
// Driver code
var array = [2, 4, 5, 6, 7];
var n = array.length;
document.write( find_triplet(array, n));
</script>
Producción:
1