Número de cuádruples donde los primeros tres términos están en AP y los últimos tres términos están en GP

Posted on by Rudeus Greyrat

Dada una array arr[] de N enteros. La tarea es encontrar el número de índices cuádruples (i, j, k, l) tales que a[i], a[j] y a[k] están en AP y a[j], a[k] y a [l] están en GP . Todos los cuádruples tienen que ser distintos.
Ejemplos: 
 

Entrada: arr[] = {2, 6, 4, 9, 2} 
Salida: 2  Los
índices de elementos en los cuádruples son (0, 2, 1, 3) y (4, 2, 1, 3) y los cuádruples correspondientes son (2, 4, 6, 9) y (2, 4, 6, 9)
Entrada: arr[] = {1, 1, 1, 1} 
Salida: 24 
 

Un enfoque ingenuo es resolver el problema anterior utilizando cuatro bucles anidados. Verifique los primeros tres elementos si están en AP o no y luego verifique si los últimos tres elementos están en GP o no. Si se cumplen ambas condiciones, entonces aumentan el conteo en 1. 
Complejidad de tiempo: O(n 4 ) 
Un enfoque eficiente es usar la combinatoria para resolver el problema anterior. Inicialmente mantenga un recuento del número de ocurrencias de cada elemento de la array. Ejecute dos bucles anidados y considere que ambos elementos son el segundo y el tercer número. Por tanto, el primer elemento será a[j] – (a[k] – a[j]) y el cuarto elemento seráa[k] * a[k] / a[j] si es un valor entero. Por lo tanto, el número de cuádruples usando estos dos índices j y k será un conteo del primer número * conteo del cuarto número con el segundo y tercer elemento siendo fijos. 
A continuación se muestra la implementación del enfoque anterior: 
 

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of quadruples
int countQuadruples(int a[], int n)
{
 
    // Hash table to count the number of occurrences
    unordered_map<int, int> mpp;
 
    // Traverse and increment the count
    for (int i = 0; i < n; i++)
        mpp[a[i]]++;
 
    int count = 0;
 
    // Run two nested loop for second and third element
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
 
            // If they are same
            if (j == k)
                continue;
 
            // Initially decrease the count
            mpp[a[j]]--;
            mpp[a[k]]--;
 
            // Find the first element using common difference
            int first = a[j] - (a[k] - a[j]);
 
            // Find the fourth element using GP
            // y^2 = x * z property
            int fourth = (a[k] * a[k]) / a[j];
 
            // If it is an integer
            if ((a[k] * a[k]) % a[j] == 0) {
 
                // If not equal
                if (a[j] != a[k])
                    count += mpp[first] * mpp[fourth];
 
                // Same elements
                else
                    count += mpp[first] * (mpp[fourth] - 1);
            }
 
            // Later increase the value for
            // future calculations
            mpp[a[j]]++;
            mpp[a[k]]++;
        }
    }
    return count;
}
 
// Driver code
int main()
{
    int a[] = { 2, 6, 4, 9, 2 };
    int n = sizeof(a) / sizeof(a[0]);
 
    cout << countQuadruples(a, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG
{
 
    // Function to return the count of quadruples
    static int countQuadruples(int a[], int n)
    {
 
        // Hash table to count the number of occurrences
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>();
 
        // Traverse and increment the count
        for (int i = 0; i < n; i++)
            if (mp.containsKey(a[i]))
            {
                mp.put(a[i], mp.get(a[i]) + 1);
            }
            else
            {
                mp.put(a[i], 1);
            }
 
        int count = 0;
 
        // Run two nested loop for second and third element
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
 
                // If they are same
                if (j == k)
                    continue;
 
                // Initially decrease the count
                mp.put(a[j], mp.get(a[j]) - 1);
                mp.put(a[k], mp.get(a[k]) - 1);
 
                // Find the first element using common difference
                int first = a[j] - (a[k] - a[j]);
 
                // Find the fourth element using GP
                // y^2 = x * z property
                int fourth = (a[k] * a[k]) / a[j];
 
                // If it is an integer
                if ((a[k] * a[k]) % a[j] == 0)
                {
 
                    // If not equal
                    if (a[j] != a[k])
                    {
                        if (mp.containsKey(first) && mp.containsKey(fourth))
                            count += mp.get(first) * mp.get(fourth);
                    }
                     
                    // Same elements
                    else if (mp.containsKey(first) && mp.containsKey(fourth))
                        count += mp.get(first) * (mp.get(fourth) - 1);
                }
 
                // Later increase the value for
                // future calculations
                if (mp.containsKey(a[j]))
                {
                    mp.put(a[j], mp.get(a[j]) + 1);
                }
                else
                {
                    mp.put(a[j], 1);
                }
                if (mp.containsKey(a[k]))
                {
                    mp.put(a[k], mp.get(a[k]) + 1);
                }
                else
                {
                    mp.put(a[k], 1);
                }
            }
        }
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int a[] = { 2, 6, 4, 9, 2 };
        int n = a.length;
 
        System.out.print(countQuadruples(a, n));
    }
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
 
# Function to return the count of quadruples
def countQuadruples(a, n) :
 
    # Hash table to count the number
    # of occurrences
    mpp = dict.fromkeys(a, 0);
 
    # Traverse and increment the count
    for i in range(n) :
        mpp[a[i]] += 1;
 
    count = 0;
 
    # Run two nested loop for second
    # and third element
    for j in range(n) :
        for k in range(n) :
 
            # If they are same
            if (j == k) :
                continue;
 
            # Initially decrease the count
            mpp[a[j]] -= 1;
            mpp[a[k]] -= 1;
 
            # Find the first element using
            # common difference
            first = a[j] - (a[k] - a[j]);
             
            if first not in mpp :
                mpp[first] = 0;
                 
            # Find the fourth element using
            # GP y^2 = x * z property
            fourth = (a[k] * a[k]) // a[j];
             
            if fourth not in mpp :
                mpp[fourth] = 0;
                 
            # If it is an integer
            if ((a[k] * a[k]) % a[j] == 0) :
 
                # If not equal
                if (a[j] != a[k]) :
                    count += mpp[first] * mpp[fourth];
 
                # Same elements
                else :
                    count += (mpp[first] *
                             (mpp[fourth] - 1));
             
            # Later increase the value for
            # future calculations
            mpp[a[j]] += 1;
            mpp[a[k]] += 1;
             
    return count;
 
# Driver code
if __name__ == "__main__" :
 
    a = [ 2, 6, 4, 9, 2 ];
    n = len(a) ;
 
    print(countQuadruples(a, n));
 
# This code is contributed by Ryuga

C#

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
 
    // Function to return the count of quadruples
    static int countQuadruples(int []a, int n)
    {
 
        // Hash table to count the number of occurrences
        Dictionary<int, int> mp = new Dictionary<int, int>();
 
        // Traverse and increment the count
        for (int i = 0; i < n; i++)
            if (mp.ContainsKey(a[i]))
            {
                mp[a[i]] = mp[a[i]] + 1;
            }
            else
            {
                mp.Add(a[i], 1);
            }
 
        int count = 0;
 
        // Run two nested loop for second and third element
        for (int j = 0; j < n; j++)
        {
            for (int k = 0; k < n; k++)
            {
 
                // If they are same
                if (j == k)
                    continue;
 
                // Initially decrease the count
                mp[a[j]] = mp[a[j]] - 1;
                mp[a[k]] = mp[a[k]] - 1;
 
                // Find the first element using common difference
                int first = a[j] - (a[k] - a[j]);
 
                // Find the fourth element using GP
                // y^2 = x * z property
                int fourth = (a[k] * a[k]) / a[j];
 
                // If it is an integer
                if ((a[k] * a[k]) % a[j] == 0)
                {
 
                    // If not equal
                    if (a[j] != a[k])
                    {
                        if (mp.ContainsKey(first) && mp.ContainsKey(fourth))
                            count += mp[first] * mp[fourth];
                    }
                     
                    // Same elements
                    else if (mp.ContainsKey(first) && mp.ContainsKey(fourth))
                        count += mp[first] * (mp[fourth] - 1);
                }
 
                // Later increase the value for
                // future calculations
                if (mp.ContainsKey(a[j]))
                {
                    mp[a[j]] = mp[a[j]] + 1;
                }
                else
                {
                    mp.Add(a[j], 1);
                }
                if (mp.ContainsKey(a[k]))
                {
                    mp[a[k]] = mp[a[k]] + 1;
                }
                else
                {
                    mp.Add(a[k], 1);
                }
            }
        }
        return count;
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        int []a = { 2, 6, 4, 9, 2 };
        int n = a.Length;
 
        Console.Write(countQuadruples(a, n));
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript implementation of the approach
 
    // Function to return the count of quadruples
    function countQuadruples(a, n)
    {
   
        // Hash table to count the
        // number of occurrences
        let mp = new Map();
   
        // Traverse and increment the count
        for (let i = 0; i < n; i++)
            if (mp.has(a[i]))
            {
                mp.set(a[i], mp.get(a[i]) + 1);
            }
            else
            {
                mp.set(a[i], 1);
            }
   
        let count = 0;
   
        // Run two nested loop for second
        // and third element
        for (let j = 0; j < n; j++)
        {
            for (let k = 0; k < n; k++)
            {
   
                // If they are same
                if (j == k)
                    continue;
   
                // Initially decrease the count
                mp.set(a[j], mp.get(a[j]) - 1);
                mp.set(a[k], mp.get(a[k]) - 1);
   
                // Find the first element using
                // common difference
                let first = a[j] - (a[k] - a[j]);
   
                // Find the fourth element using GP
                // y^2 = x * z property
                let fourth = (a[k] * a[k]) / a[j];
   
                // If it is an integer
                if ((a[k] * a[k]) % a[j] == 0)
                {
   
                    // If not equal
                    if (a[j] != a[k])
                    {
                        if (mp.has(first) && mp.has(fourth))
                            count +=
                            mp.get(first) * mp.get(fourth);
                    }
                       
                    // Same elements
                    else if (mp.has(first) && mp.has(fourth))
                        count +=
                        mp.get(first) * (mp.get(fourth) - 1);
                }
   
                // Later increase the value for
                // future calculations
                if (mp.has(a[j]))
                {
                    mp.set(a[j], mp.get(a[j]) + 1);
                }
                else
                {
                    mp.set(a[j], 1);
                }
                if (mp.has(a[k]))
                {
                    mp.set(a[k], mp.get(a[k]) + 1);
                }
                else
                {
                    mp.set(a[k], 1);
                }
            }
        }
        return count;
    }
       
    // Driver code
     
    let a = [ 2, 6, 4, 9, 2 ];
        let n = a.length;
   
        document.write(countQuadruples(a, n));
                   
</script>
Producción: 

2

 

Complejidad de tiempo: O(N 2 ), ya que estamos usando bucles anidados para atravesar N*N veces. Donde N es el número de elementos de la array.
Espacio Auxiliar: O(N), ya que están usando espacio extra para el mapa. 
 

Publicación traducida automáticamente

Artículo escrito por Striver 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 *