Número de grupos de tamaños dos o tres divisibles por 3

Posted on by Rudeus Greyrat

Te dan N números distintos. Tienes la tarea de encontrar el número de grupos de 2 o 3 que se pueden formar cuya suma es divisible por tres.
Ejemplos: 
 

Input  : 1 5 7 2 9 14
Output : 13
The groups of two that can be 
formed are:
(1, 5)
(5, 7)
(1, 2)
(2, 7)
(1, 14)
(7, 14)
The groups of three are:
(1, 5, 9)
(5, 7, 9)
(1, 2, 9)
(2, 7, 9)
(2, 5, 14)
(1, 9, 14)
(7, 9, 14)

Input  : 3 6 9 12
Output : 10
All groups of 2 and 3 are valid.

Enfoque ingenuo: para cada número, podemos sumarlo con cualquier otro número y ver si la suma es divisible por 3. Luego almacenamos estas sumas, de modo que podamos sumar cada número nuevamente para verificar grupos de tres. 
Complejidad de tiempo: O(N^2) para grupos de 2, O(N^3) para grupos de 3 
Espacio auxiliar: O(N^2)
Enfoque óptimo 
Si observamos cuidadosamente cada número, nos damos cuenta de que existen 3 opciones: 
 

  1. el numero es divisible por 3
  2. El número deja un resto de 1, cuando se divide por 3
  3. El número deja un resto de 2, cuando se divide por 3

Ahora, para que los grupos de dos sean divisibles por 3, o ambos números deben pertenecer a la categoría 1 (ambos son divisibles por 3), o un número debe dejar un residuo 1 y el otro un residuo 2. De esta manera los residuos se suman a 3, haciendo que la suma sea divisible por 3. 
Para formar un grupo de tres, o los tres números deben dar el mismo resto, o uno debe dar el resto 0, otro debe dar 1 y el último debe dar 2.
De esta manera, no nos importan los números en sí, sino sus respectivos restos. Así, al agruparlos en tres categorías, podemos encontrar el total de grupos posibles usando una fórmula simple. 
Sea C1 el número de elementos divisible por 3. 
Sea C2 el número de elementos que dejan resto 1. 
Sea C3 el número de elementos que dejan resto 2. 
 

Answer = 
C2 * C3 + C1 * (C1 - 1) / 2    --> Groups of 2
+ C1 * (C1 - 1) * (C1 - 2) / 6 
+ C2 * (C2 - 1) * (C2 - 2) / 6 
+ C3 * (C3 - 1) * (C3 - 2) / 6 --> Groups of 3 
                   with elements of same remainder
+ C1 * C2 * C3 --> Groups of three with all
                         distinct remainders

CPP

// Program to find groups of 2 or 3
// whose sum is divisible by 3
#include <iostream>
using namespace std;
 
int numOfCombinations(int arr[], int N)
{
    // Initialize groups to 0
    int C[3] = { 0, 0, 0 };
 
    // Increment group with specified remainder
    for (int i = 0; i < N; ++i)
        ++C[arr[i] % 3];
 
    // Return groups using the formula
    return C[1] * C[2] + C[0] * (C[0] - 1) / 2 + C[0] * (C[0] - 1) * (C[0] - 2) / 6 + C[1] * (C[1] - 1) * (C[1] - 2) / 6 + C[2] * (C[2] - 1) * (C[2] - 2) / 6 + C[0] * C[1] * C[2];
}
 
// Driver Function
int main()
{
    int arr1[6] = { 1, 5, 7, 2, 9, 14 };
    cout << numOfCombinations(arr1, 6) << "\n";
    int arr2[4] = { 3, 6, 9, 12 };
    cout << numOfCombinations(arr2, 4) << "\n";
    return 0;
}

Java

// Program to find groups of 2 or 3
// whose sum is divisible by 3
 
class GFG {
 
    static int numOfCombinations(int arr[], int N)
    {
        // Initialize groups to 0
        int C[] = { 0, 0, 0 };
 
        // Increment group with specified remainder
        for (int i = 0; i < N; ++i)
            ++C[arr[i] % 3];
 
        // Return groups using the formula
        return C[1] * C[2] + C[0] * (C[0] - 1) / 2 + C[0] * (C[0] - 1) * (C[0] - 2) / 6 + C[1] * (C[1] - 1) * (C[1] - 2) / 6 + C[2] * (C[2] - 1) * (C[2] - 2) / 6 + C[0] * C[1] * C[2];
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int arr1[] = { 1, 5, 7, 2, 9, 14 };
        System.out.print(numOfCombinations(arr1, 6) + "\n");
        int arr2[] = { 3, 6, 9, 12 };
        System.out.print(numOfCombinations(arr2, 4) + "\n");
    }
}
 
// This code is contributed by Anant Agarwal.

Python3

# Program to find groups of 2 or 3
# whose sum is divisible by 3
 
def numOfCombinations(arr, N):
    # Initialize groups to 0
    C = [0, 0, 0]
  
    # Increment group with
    # specified remainder
    for i in range(N):
         
        C[arr[i] % 3]= C[arr[i] % 3]+1
  
    # Return groups using the formula
    return (C[1] * C[2] + C[0] * (C[0] - 1) / 2 + C[0] * (C[0] - 1) * (C[0] - 2) / 6 + C[1] * (C[1] - 1) * (C[1] - 2) / 6 + C[2] * (C[2] - 1) * (C[2] - 2) / 6 + C[0] * C[1] * C[2])
 
# Driver code
 
arr1 = [1, 5, 7, 2, 9, 14]
print(int(numOfCombinations(arr1, 6)))
arr2 = [3, 6, 9, 12]
print(int(numOfCombinations(arr2, 4)))
 
 
# This code is contributed
# by Anant Agarwal.

C#

// C# Program to find groups of 2 or
// 3 whose sum is divisible by 3
using System;
 
class GFG {
 
    // Function to find number of combinations
    static int numOfCombinations(int[] arr,
                                 int N)
    {
 
        // Initialize groups to 0
        int[] C = { 0, 0, 0 };
 
        // Increment group with specified remainder
        for (int i = 0; i < N; ++i)
            ++C[arr[i] % 3];
 
        // Return groups using the formula
        return C[1] * C[2] + C[0] * (C[0] - 1) / 2 + C[0] * (C[0] - 1) * (C[0] - 2) / 6 + C[1] * (C[1] - 1) * (C[1] - 2) / 6 + C[2] * (C[2] - 1) * (C[2] - 2) / 6 + C[0] * C[1] * C[2];
    }
 
    // Driver code
    public static void Main()
    {
        int[] arr1 = { 1, 5, 7, 2, 9, 14 };
        Console.WriteLine(numOfCombinations(arr1, 6));
        int[] arr2 = { 3, 6, 9, 12 };
        Console.WriteLine(numOfCombinations(arr2, 4));
    }
}
 
// This code is contributed by vt_m.

PHP

<?php
 
// PHP Program to find
// groups of 2 or 3
// whose sum is divisible by 3
 
 
function numOfCombinations($arr, $N)
{
    // Initialize groups to 0
    $C = array(0, 0, 0);
 
    // Increment group with
    // specified remainder
    for ($i = 0; $i < $N; ++$i)
        ++$C[$arr[$i] % 3];
 
    // Return groups using the formula
    return $C[1] * $C[2] +
           $C[0] * ($C[0] - 1) / 2 +
           $C[0] * ($C[0] - 1) *
                   ($C[0] - 2) / 6 +
           $C[1] * ($C[1] - 1) *
                   ($C[1] - 2) / 6 +
           $C[2] * ($C[2] - 1) *
                   ($C[2] - 2) / 6 +
           $C[0] * $C[1] * $C[2];
}
 
// Driver Code
$arr1 = array(1, 5, 7, 2, 9, 14);
echo numOfCombinations($arr1, 6), "\n";
 
$arr2 = array(3, 6, 9, 12);
    echo numOfCombinations($arr2, 4), "\n";
 
// This code is contributed by ajit
?>

Javascript

<script>
// Javascript Program to find
// groups of 2 or 3
// whose sum is divisible by 3
function numOfCombinations(arr, N)
{
 
    // Initialize groups to 0
    let C = [0, 0, 0];
 
    // Increment group with
    // specified remainder
    for (let i = 0; i < N; ++i)
        ++C[arr[i] % 3];
 
    // Return groups using the formula
    return C[1] * C[2] +
        C[0] * (C[0] - 1) / 2 +
        C[0] * (C[0] - 1) *
                (C[0] - 2) / 6 +
        C[1] * (C[1] - 1) *
                (C[1] - 2) / 6 +
        C[2] * (C[2] - 1) *
                (C[2] - 2) / 6 +
        C[0] * C[1] * C[2];
}
 
// Driver Code
let arr1 = [1, 5, 7, 2, 9, 14];
document.write(numOfCombinations(arr1, 6) + "<br>");
 
let arr2 = [3, 6, 9, 12];
document.write(numOfCombinations(arr2, 4) + "<br>");
 
// This code is contributed by gfgking.
</script>

Producción : 
 

13
10

Preguntado en Amazon
Este artículo es una contribución de Aditya Kamath . 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.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
 

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 *