Recuento de tripletes en una array que satisfacen las condiciones dadas

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:
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

 

Publicación traducida automáticamente

Artículo escrito por krikti y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *