Divida una array en grupos de 3 de manera que X3 sea divisible por X2 y X2 sea divisible por X1

Dada una array A que contiene N elementos ( N es divisible por 3 ), la tarea es dividir los números en grupos de 3, dejar que el grupo tenga 3 elementos X1, X2 y X3, las siguientes condiciones deben ser verdaderas para el grupo: 
 

• X1, X2 y X3 son distintos por pares
• X3 es divisible por X2
• X2 es divisible por X1

Imprima -1 si no es posible dividir la array en N/3 Tales grupos.
Nota: Los elementos de la array estarán en el rango de 1 a 6 (inclusive).
Ejemplos: 
 

Input : N = 6, A[] = {2, 2, 1, 1, 4, 6}
Output : 1 2 4
         1 2 6
Explanation: 
Group 1: Pairs = {(1,2), (2,4), (1,4)}
All pairs are distinct, 
4 is divisible by 2 and 2 by 1.
Group 2: Pairs = {(1,2), (2,6), (1,6)}
All pairs are distinct, 
6 is divisible by 2 and 2 by 1.

Input : N = 6, A[] = {1, 1, 1, 6, 6, 3}
Output : -1

Planteamiento:
Dado que los valores de la array están entre 1 y 6, solo se pueden hacer los siguientes tipos de grupos: 
 

• 1 2 4
• 1 2 6
• 1 3 6

Comienza contando la frecuencia de cada elemento. Dado que 1 es común en todos los grupos, debe ocurrir exactamente N/3 veces. 4 se puede poner solo en el primer tipo de grupo, que siempre contiene 2. Por lo tanto, la cuenta de 2 debe ser mayor que la cuenta de 4. Los 2 restantes se pueden poner solo en el segundo tipo de grupos. Ahora, los números restantes deben colocarse en el tercer tipo de grupos. Si en algún momento el conteo es menor al requerido, la respuesta sería -1.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to split array in groups of 3
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to print the groups after
// splitting array in groups of 3
void printGroups(int n, int a[])
{
    int ct[7] = { 0 }, grps = n / 3, i;
 
    // Count occurrence of each element
    for (i = 0; i < n; i++)
        ct[a[i]]++;
 
    // Check if it is possible to form the groups
    if (ct[1] != grps || (ct[4] + ct[6]) != grps
              || (ct[2] + ct[3]) != grps || ct[4] > ct[2])
    {
        cout << -1;
        return;
    }
 
    // Print groups that end at 4
    for (i = 0; i < ct[4]; i++)
        cout << "1 2 4\n";
 
    // Print groups that end at 6, with 2
    // in the middle
    for (i = 0; i < ct[2] - ct[4]; i++)
        cout << "1 2 6\n";
 
    // Print groups that have a 3 in the middle
    for (i = 0; i < ct[3]; i++)
        cout << "1 3 6\n";
}
 
// Driver Code
int main()
{
    int n = 6;
    int a[n] = { 2, 2, 1, 1, 4, 6 };
 
    printGroups(n, a);
 
    return 0;
}

// Java program to split array in groups of 3
class GFG
{
 
    // Function to print the groups after
    // splitting array in groups of 3
    static void printGroups(int n, int a[])
    {
        int ct[] = new int[7], grps = n / 3, i;
 
        // Count occurrence of each element
        for (i = 0; i < n; i++)
        {
            ct[a[i]]++;
        }
 
        // Check if it is possible to form the groups
        if (ct[1] != grps || (ct[4] + ct[6]) != grps
            || (ct[2] + ct[3]) != grps || ct[4] > ct[2])
        {
            System.out.print(-1);
            return;
        }
 
        // Print groups that end at 4
        for (i = 0; i < ct[4]; i++)
        {
            System.out.print("1 2 4\n");
        }
 
        // Print groups that end at 6, with 2
        // in the middle
        for (i = 0; i < ct[2] - ct[4]; i++)
        {
            System.out.print("1 2 6\n");
        }
         
        // Print groups that have a 3 in the middle
        for (i = 0; i < ct[3]; i++)
        {
            System.out.print("1 3 6\n");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int n = 6;
        int a[] = {2, 2, 1, 1, 4, 6};
 
        printGroups(n, a);
    }
}
 
/* This code contributed by PrinciRaj1992 */

# Python3 program to split array in
# groups of 3
 
# Function to print the groups after
# splitting array in groups of 3
def printGroups(n, a):
 
    ct = [0 for i in range(7)]
    grps = n // 3
    i = 0
 
    # Count occurrence of each element
    for i in range(n):
        ct[a[i]] += 1
 
    # Check if it is possible to
    # form the groups
    if (ct[1] != grps or (ct[4] + ct[6]) != grps or
       (ct[2] + ct[3]) != grps or ct[4] > ct[2]):
        print(-1)
        return
 
    # Print groups that end at 4
    for i in range(ct[4]):
        print("1 2 4")
 
    # Print groups that end at 6, with 2
    # in the middle
    for i in range(ct[2] - ct[4]):
        print("1 2 6")
 
    # Print groups that have a 3 in the middle
    for i in range(ct[3]):
        print("1 3 6")
 
# Driver Code
n = 6
a = [2, 2, 1, 1, 4, 6 ]
 
printGroups(n, a)
 
# This code is contributed
# by Mohit Kumar

// C# program to split array in groups of 3
using System;
 
class GFG
{
 
    // Function to print the groups after
    // splitting array in groups of 3
    static void printGroups(int n, int []a)
    {
        int []ct = new int[7];
        int grps = n / 3, i;
 
        // Count occurrence of each element
        for (i = 0; i < n; i++)
        {
            ct[a[i]]++;
        }
 
        // Check if it is possible to form the groups
        if (ct[1] != grps || (ct[4] + ct[6]) != grps ||
           (ct[2] + ct[3]) != grps || ct[4] > ct[2])
        {
            Console.Write(-1);
            return;
        }
 
        // Print groups that end at 4
        for (i = 0; i < ct[4]; i++)
        {
            Console.Write("1 2 4\n");
        }
 
        // Print groups that end at 6, with 2
        // in the middle
        for (i = 0; i < ct[2] - ct[4]; i++)
        {
            Console.Write("1 2 6\n");
        }
         
        // Print groups that have a 3 in the middle
        for (i = 0; i < ct[3]; i++)
        {
            Console.Write("1 3 6\n");
        }
    }
 
    // Driver Code
    public static void Main()
    {
        int n = 6;
        int []a = {2, 2, 1, 1, 4, 6};
 
        printGroups(n, a);
    }
}
 
// This code is contributed
// by Akanksha Rai

<?php
// PHP program to split array in groups of 3
 
// Function to print the groups after
// splitting array in groups of 3
function printGroups($n, $a)
{
    $ct = array(); $grps = $n / 3;
 
    // Count occurrence of each element
    for ($i = 0; $i < $n; $i++)
        $ct[$a[$i]]++;
 
    // Check if it is possible to form the groups
    if ($ct[1] != $grps || ($ct[4] + $ct[6]) != $grps ||
       ($ct[2] + $ct[3]) != $grps || $ct[4] > $ct[2])
    {
        echo -1;
        return;
    }
 
    // Print groups that end at 4
    for ($i = 0; $i < $ct[4]; $i++)
        echo "1 2 4\n";
 
    // Print groups that end at 6, with 2
    // in the middle
    for ($i = 0; $i < $ct[2] - $ct[4]; $i++)
        echo "1 2 6\n";
 
    // Print groups that have a 3 in the middle
    for ($i = 0; $i < $ct[3]; $i++)
        echo "1 3 6\n";
}
 
// Driver Code
$n = 6;
$a = array(2, 2, 1, 1, 4, 6);
 
printGroups($n, $a);
 
// This code is contributed
// by Akanksha Rai
?>

<script>
// Javascript program to split array in groups of 3
 
// Function to print the groups after
// splitting array in groups of 3
function printGroups(n, a)
{
    let ct = new Array(7).fill(0), grps = parseInt(n / 3), i;
 
    // Count occurrence of each element
    for (i = 0; i < n; i++)
        ct[a[i]]++;
 
    // Check if it is possible to form the groups
    if (ct[1] != grps || (ct[4] + ct[6]) != grps
              || (ct[2] + ct[3]) != grps || ct[4] > ct[2])
    {
        document.write(-1);
        return;
    }
 
    // Print groups that end at 4
    for (i = 0; i < ct[4]; i++)
        document.write("1 2 4<br>");
 
    // Print groups that end at 6, with 2
    // in the middle
    for (i = 0; i < ct[2] - ct[4]; i++)
        document.write("1 2 6<br>");
 
    // Print groups that have a 3 in the middle
    for (i = 0; i < ct[3]; i++)
        document.write("1 3 6<br>");
}
 
// Driver Code
    let n = 6;
    let a = [ 2, 2, 1, 1, 4, 6 ];
 
    printGroups(n, a);
 
</script>

1 2 4
1 2 6

Complejidad de tiempo: O(N)