Encuentre todos los trillizos en una array ordenada que forma la progresión geométrica

Dada una array ordenada de enteros positivos distintos, imprima todos los tripletes que forman la Progresión geométrica con razón común integral.
Una progresión geométrica es una secuencia de números donde cada término después del primero se encuentra multiplicando el anterior por un número fijo distinto de cero llamado razón común. Por ejemplo, la sucesión 2, 6, 18, 54,… es una progresión geométrica de razón común 3.

Ejemplos: 

Input: 
arr = [1, 2, 6, 10, 18, 54]
Output: 
2 6 18
6 18 54

Input: 
arr = [2, 8, 10, 15, 16, 30, 32, 64]
Output: 
2 8 32
8 16 32
16 32 64

Input: 
arr = [ 1, 2, 6, 18, 36, 54]
Output: 
2 6 18
1 6 36
6 18 54

La idea es comenzar desde el segundo elemento y fijar cada elemento como elemento medio y buscar los otros dos elementos en un triplete (uno más pequeño y otro más grande). Para que un elemento arr[j] esté en el medio de una progresión geométrica, deben existir elementos arr[i] y arr[k] tales que: 

arr[j] / arr[i] = r and arr[k] / arr[j] = r
where r is an positive integer and 0 <= i < j and j < k <= n - 1

A continuación se muestra la implementación de la idea anterior.

C++

// C++ program to find if there exist three elements in
// Geometric Progression or not
#include <iostream>
using namespace std;
 
// The function prints three elements in GP if exists
// Assumption: arr[0..n-1] is sorted.
void findGeometricTriplets(int arr[], int n)
{
    // One by fix every element as middle element
    for (int j = 1; j < n - 1; j++)
    {
        // Initialize i and k for the current j
        int i = j - 1, k = j + 1;
 
        // Find all i and k such that (i, j, k)
        // forms a triplet of GP
        while (i >= 0 && k <= n - 1)
        {
            // if arr[j]/arr[i] = r and arr[k]/arr[j] = r
            // and r is an integer (i, j, k) forms Geometric
            // Progression
            while (arr[j] % arr[i] == 0 &&
                    arr[k] % arr[j] == 0 &&
                    arr[j] / arr[i] == arr[k] / arr[j])
            {
                // print the triplet
                cout << arr[i] << " " << arr[j]
                     << " " << arr[k] << endl;
 
                // Since the array is sorted and elements
                // are distinct.
                k++ , i--;
            }
 
            // if arr[j] is multiple of arr[i] and arr[k] is
            // multiple of arr[j], then arr[j] / arr[i] !=
            // arr[k] / arr[j]. We compare their values to
            // move to next k or previous i.
            if(arr[j] % arr[i] == 0 &&
                    arr[k] % arr[j] == 0)
            {
                if(arr[j] / arr[i] < arr[k] / arr[j])
                    i--;
                else k++;
            }
 
            // else if arr[j] is multiple of arr[i], then
            // try next k. Else, try previous i.
            else if (arr[j] % arr[i] == 0)
                k++;
            else i--;
        }
    }
}
 
// Driver code
int main()
{
    // int arr[] = {1, 2, 6, 10, 18, 54};
    // int arr[] = {2, 8, 10, 15, 16, 30, 32, 64};
    // int arr[] = {1, 2, 6, 18, 36, 54};
    int arr[] = {1, 2, 4, 16};
    // int arr[] = {1, 2, 3, 6, 18, 22};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    findGeometricTriplets(arr, n);
 
    return 0;
}

Java

// Java program to find if there exist three elements in
// Geometric Progression or not
import java.util.*;
 
class GFG
{
 
// The function prints three elements in GP if exists
// Assumption: arr[0..n-1] is sorted.
static void findGeometricTriplets(int arr[], int n)
{
    // One by fix every element as middle element
    for (int j = 1; j < n - 1; j++)
    {
        // Initialize i and k for the current j
        int i = j - 1, k = j + 1;
 
        // Find all i and k such that (i, j, k)
        // forms a triplet of GP
        while (i >= 0 && k <= n - 1)
        {
            // if arr[j]/arr[i] = r and arr[k]/arr[j] = r
            // and r is an integer (i, j, k) forms Geometric
            // Progression
            while (i >= 0 && arr[j] % arr[i] == 0 &&
                    arr[k] % arr[j] == 0 &&
                    arr[j] / arr[i] == arr[k] / arr[j])
            {
                // print the triplet
                System.out.println(arr[i] +" " + arr[j]
                    + " " + arr[k]);
 
                // Since the array is sorted and elements
                // are distinct.
                k++ ; i--;
            }
 
            // if arr[j] is multiple of arr[i] and arr[k] is
            // multiple of arr[j], then arr[j] / arr[i] !=
            // arr[k] / arr[j]. We compare their values to
            // move to next k or previous i.
            if(i >= 0 && arr[j] % arr[i] == 0 &&
                    arr[k] % arr[j] == 0)
            {
                if(i >= 0 && arr[j] / arr[i] < arr[k] / arr[j])
                    i--;
                else k++;
            }
 
            // else if arr[j] is multiple of arr[i], then
            // try next k. Else, try previous i.
            else if (i >= 0 && arr[j] % arr[i] == 0)
                k++;
            else i--;
        }
    }
}
 
// Driver code
public static void main(String[] args)
{
    // int arr[] = {1, 2, 6, 10, 18, 54};
    // int arr[] = {2, 8, 10, 15, 16, 30, 32, 64};
    // int arr[] = {1, 2, 6, 18, 36, 54};
    int arr[] = {1, 2, 4, 16};
    // int arr[] = {1, 2, 3, 6, 18, 22};
    int n = arr.length;
 
    findGeometricTriplets(arr, n);
}
}
 
// This code is contributed by Rajput-Ji

Python 3

# Python 3 program to find if
# there exist three elements in
# Geometric Progression or not
 
# The function prints three elements
# in GP if exists.
# Assumption: arr[0..n-1] is sorted.
def findGeometricTriplets(arr, n):
 
    # One by fix every element
    # as middle element
    for j in range(1, n - 1):
     
        # Initialize i and k for
        # the current j
        i = j - 1
        k = j + 1
 
        # Find all i and k such that
        # (i, j, k) forms a triplet of GP
        while (i >= 0 and k <= n - 1):
         
            # if arr[j]/arr[i] = r and
            # arr[k]/arr[j] = r and r
            # is an integer (i, j, k) forms
            # Geometric Progression
            while (arr[j] % arr[i] == 0 and
                   arr[k] % arr[j] == 0 and
                   arr[j] // arr[i] == arr[k] // arr[j]):
             
                # print the triplet
                print( arr[i] , " " , arr[j],
                                " " , arr[k])
 
                # Since the array is sorted and
                # elements are distinct.
                k += 1
                i -= 1
 
            # if arr[j] is multiple of arr[i]
            # and arr[k] is multiple of arr[j],
            # then arr[j] / arr[i] != arr[k] / arr[j].
            # We compare their values to
            # move to next k or previous i.
            if(arr[j] % arr[i] == 0 and
                        arr[k] % arr[j] == 0):
             
                if(arr[j] // arr[i] < arr[k] // arr[j]):
                    i -= 1
                else:
                    k += 1
 
            # else if arr[j] is multiple of
            # arr[i], then try next k. Else,
            # try previous i.
            elif (arr[j] % arr[i] == 0):
                k += 1
            else:
                i -= 1
 
# Driver code
if __name__ =="__main__":
     
    arr = [1, 2, 4, 16]
    n = len(arr)
 
    findGeometricTriplets(arr, n)
 
# This code is contributed
# by ChitraNayal

C#

// C# program to find if there exist three elements
// in Geometric Progression or not
using System;
 
class GFG
{
     
// The function prints three elements in GP if exists
// Assumption: arr[0..n-1] is sorted.
static void findGeometricTriplets(int []arr, int n)
{
     
    // One by fix every element as middle element
    for (int j = 1; j < n - 1; j++)
    {
        // Initialize i and k for the current j
        int i = j - 1, k = j + 1;
 
        // Find all i and k such that (i, j, k)
        // forms a triplet of GP
        while (i >= 0 && k <= n - 1)
        {
            // if arr[j]/arr[i] = r and arr[k]/arr[j] = r
            // and r is an integer (i, j, k) forms Geometric
            // Progression
            while (i >= 0 && arr[j] % arr[i] == 0 &&
                             arr[k] % arr[j] == 0 &&
                    arr[j] / arr[i] == arr[k] / arr[j])
            {
                // print the triplet
            Console.WriteLine(arr[i] +" " +
                              arr[j] + " " + arr[k]);
 
                // Since the array is sorted and elements
                // are distinct.
                k++ ; i--;
            }
 
            // if arr[j] is multiple of arr[i] and arr[k] is
            // multiple of arr[j], then arr[j] / arr[i] !=
            // arr[k] / arr[j]. We compare their values to
            // move to next k or previous i.
            if(i >= 0 && arr[j] % arr[i] == 0 &&
                         arr[k] % arr[j] == 0)
            {
                if(i >= 0 && arr[j] / arr[i] <
                             arr[k] / arr[j])
                    i--;
                else k++;
            }
 
            // else if arr[j] is multiple of arr[i], then
            // try next k. Else, try previous i.
            else if (i >= 0 && arr[j] % arr[i] == 0)
                k++;
            else i--;
        }
    }
}
 
// Driver code
static public void Main ()
{
     
    // int arr[] = {1, 2, 6, 10, 18, 54};
    // int arr[] = {2, 8, 10, 15, 16, 30, 32, 64};
    // int arr[] = {1, 2, 6, 18, 36, 54};
    int []arr = {1, 2, 4, 16};
     
    // int arr[] = {1, 2, 3, 6, 18, 22};
    int n = arr.Length;
     
    findGeometricTriplets(arr, n);
}
}
 
// This code is contributed by ajit.

Javascript

<script>
// Javascript program to find if there exist three elements in
// Geometric Progression or not
 
    // The function prints three elements in GP if exists
    // Assumption: arr[0..n-1] is sorted.
    function findGeometricTriplets(arr,n)
    {
     
        // One by fix every element as middle element
        for (let j = 1; j < n - 1; j++)
        {
         
            // Initialize i and k for the current j
            let i = j - 1, k = j + 1;
       
            // Find all i and k such that (i, j, k)
            // forms a triplet of GP
            while (i >= 0 && k <= n - 1)
            {
             
                // if arr[j]/arr[i] = r and arr[k]/arr[j] = r
                // and r is an integer (i, j, k) forms Geometric
                // Progression
                while (i >= 0 && arr[j] % arr[i] == 0 &&
                        arr[k] % arr[j] == 0 &&
                        arr[j] / arr[i] == arr[k] / arr[j])
                {
                 
                    // print the triplet
                    document.write(arr[i] +" " + arr[j]
                        + " " + arr[k]+"<br>");
       
                    // Since the array is sorted and elements
                    // are distinct.
                    k++ ; i--;
                }
       
                // if arr[j] is multiple of arr[i] and arr[k] is
                // multiple of arr[j], then arr[j] / arr[i] !=
                // arr[k] / arr[j]. We compare their values to
                // move to next k or previous i.
                if(i >= 0 && arr[j] % arr[i] == 0 &&
                        arr[k] % arr[j] == 0)
                {
                    if(i >= 0 && arr[j] / arr[i] < arr[k] / arr[j])
                        i--;
                    else k++;
                }
       
                // else if arr[j] is multiple of arr[i], then
                // try next k. Else, try previous i.
                else if (i >= 0 && arr[j] % arr[i] == 0)
                    k++;
                else i--;
            }
        }
    }
     
    // Driver code
    // int arr[] = {1, 2, 6, 10, 18, 54};
    // int arr[] = {2, 8, 10, 15, 16, 30, 32, 64};
    // int arr[] = {1, 2, 6, 18, 36, 54};
     
    let arr = [1, 2, 4, 16];
     
    // int arr[] = {1, 2, 3, 6, 18, 22};
    let n = arr.length;
    findGeometricTriplets(arr, n);
     
    // This code is contributed by avanitrachhadiya2155
</script>
Producción

1 2 4
1 4 16

La complejidad temporal de la solución anterior es O(n 2 ) ya que para cada j, encontramos i y k en tiempo lineal.

Este artículo es una contribución de Aditya Goel . 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.

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

Deja una respuesta

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