Dada una array de enteros no ordenados (solo valores positivos) de tamaño ‘n’, podemos formar un grupo de dos o tres, el grupo debe ser tal que la suma de todos los elementos en ese grupo sea un múltiplo de 3. Cuente todos los números posibles de grupos que se pueden generar de esta manera.
Ejemplos:
Input: arr[] = {3, 6, 7, 2, 9}
Output: 8
// Groups are {3,6}, {3,9}, {9,6}, {7,2}, {3,6,9},
// {3,7,2}, {7,2,6}, {7,2,9}
Input: arr[] = {2, 1, 3, 4}
Output: 4
// Groups are {2,1}, {2,4}, {2,1,3}, {2,4,3}
La idea es ver el resto de cada elemento cuando se divide por 3. Un conjunto de elementos puede formar un grupo solo si el sol de sus restos es múltiplo de 3.
Por ejemplo: 8, 4, 12. Ahora, los residuos son 2, 1 y 0 respectivamente. Esto significa que 8 está a 2 distancias del múltiplo de 3 (6), 4 está a 1 distancia del múltiplo de 3 (3) y 12 está a 0 distancias. Entonces, podemos escribir la suma como 8 (se puede escribir como 6+2), 4 (se puede escribir como 3+1) y 12 (se puede escribir como 12+0). Ahora la suma de 8, 4 y 12 se puede escribir como 6+2+3+1+12+0. Ahora, 6+3+12 siempre será divisible por 3 ya que todos los términos son múltiplos de tres. Ahora, solo necesitamos verificar si 2+1+0 (restos) es divisible por 3 o no, lo que hace que la suma completa sea divisible por 3.
Dado que la tarea es enumerar grupos, contamos todos los elementos con diferentes residuos.
1. Hash all elements in a count array based on remainder, i.e,
for all elements a[i], do c[a[i]%3]++;
2. Now c[0] contains the number of elements which when divided
by 3 leave remainder 0 and similarly c[1] for remainder 1
and c[2] for 2.
3. Now for group of 2, we have 2 possibilities
a. 2 elements of remainder 0 group. Such possibilities are
c[0]*(c[0]-1)/2
b. 1 element of remainder 1 and 1 from remainder 2 group
Such groups are c[1]*c[2].
4. Now for group of 3,we have 4 possibilities
a. 3 elements from remainder group 0.
No. of such groups are c[0]C3
b. 3 elements from remainder group 1.
No. of such groups are c[1]C3
c. 3 elements from remainder group 2.
No. of such groups are c[2]C3
d. 1 element from each of 3 groups.
No. of such groups are c[0]*c[1]*c[2].
5. Add all the groups in steps 3 and 4 to obtain the result.
Implementación:
C++
// C++ Program to count all possible
// groups of size 2 or 3 that have
// sum as multiple of 3
#include<bits/stdc++.h>
using namespace std;
// Returns count of all possible groups
// that can be formed from elements of a[].
int findgroups(int arr[], int n)
{
// Create an array C[3] to store counts
// of elements with remainder 0, 1 and 2.
// c[i] would store count of elements
// with remainder i
int c[3] = {0}, i;
int res = 0; // To store the result
// Count elements with remainder 0, 1 and 2
for (i=0; i<n; i++)
c[arr[i]%3]++;
// Case 3.a: Count groups of size 2
// from 0 remainder elements
res += ((c[0]*(c[0]-1))>>1);
// Case 3.b: Count groups of size 2 with
// one element with 1 remainder and other
// with 2 remainder
res += c[1] * c[2];
// Case 4.a: Count groups of size 3
// with all 0 remainder elements
res += (c[0] * (c[0]-1) * (c[0]-2))/6;
// Case 4.b: Count groups of size 3
// with all 1 remainder elements
res += (c[1] * (c[1]-1) * (c[1]-2))/6;
// Case 4.c: Count groups of size 3
// with all 2 remainder elements
res += ((c[2]*(c[2]-1)*(c[2]-2))/6);
// Case 4.c: Count groups of size 3
// with different remainders
res += c[0]*c[1]*c[2];
// Return total count stored in res
return res;
}
// Driver Code
int main()
{
int arr[] = {3, 6, 7, 2, 9};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Required number of groups are "
<< findgroups(arr,n) << endl;
return 0;
}
// This code is contributed
// by Akanksha Rai
C
// C Program to count all possible
// groups of size 2 or 3 that have
// sum as multiple of 3
#include<stdio.h>
// Returns count of all possible groups that can be formed from elements
// of a[].
int findgroups(int arr[], int n)
{
// Create an array C[3] to store counts of elements with remainder
// 0, 1 and 2. c[i] would store count of elements with remainder i
int c[3] = {0}, i;
int res = 0; // To store the result
// Count elements with remainder 0, 1 and 2
for (i=0; i<n; i++)
c[arr[i]%3]++;
// Case 3.a: Count groups of size 2 from 0 remainder elements
res += ((c[0]*(c[0]-1))>>1);
// Case 3.b: Count groups of size 2 with one element with 1
// remainder and other with 2 remainder
res += c[1] * c[2];
// Case 4.a: Count groups of size 3 with all 0 remainder elements
res += (c[0] * (c[0]-1) * (c[0]-2))/6;
// Case 4.b: Count groups of size 3 with all 1 remainder elements
res += (c[1] * (c[1]-1) * (c[1]-2))/6;
// Case 4.c: Count groups of size 3 with all 2 remainder elements
res += ((c[2]*(c[2]-1)*(c[2]-2))/6);
// Case 4.c: Count groups of size 3 with different remainders
res += c[0]*c[1]*c[2];
// Return total count stored in res
return res;
}
// Driver program to test above functions
int main()
{
int arr[] = {3, 6, 7, 2, 9};
int n = sizeof(arr)/sizeof(arr[0]);
printf("Required number of groups are %d\n", findgroups(arr,n));
return 0;
}
Java
// Java Program to count all possible
// groups of size 2 or 3 that have
// sum as multiple of 3
class FindGroups
{
// Returns count of all possible groups that can be formed from elements
// of a[].
int findgroups(int arr[], int n)
{
// Create an array C[3] to store counts of elements with remainder
// 0, 1 and 2. c[i] would store count of elements with remainder i
int c[] = new int[]{0, 0, 0};
int i;
int res = 0; // To store the result
// Count elements with remainder 0, 1 and 2
for (i = 0; i < n; i++)
c[arr[i] % 3]++;
// Case 3.a: Count groups of size 2 from 0 remainder elements
res += ((c[0] * (c[0] - 1)) >> 1);
// Case 3.b: Count groups of size 2 with one element with 1
// remainder and other with 2 remainder
res += c[1] * c[2];
// Case 4.a: Count groups of size 3 with all 0 remainder elements
res += (c[0] * (c[0] - 1) * (c[0] - 2)) / 6;
// Case 4.b: Count groups of size 3 with all 1 remainder elements
res += (c[1] * (c[1] - 1) * (c[1] - 2)) / 6;
// Case 4.c: Count groups of size 3 with all 2 remainder elements
res += ((c[2] * (c[2] - 1) * (c[2] - 2)) / 6);
// Case 4.c: Count groups of size 3 with different remainders
res += c[0] * c[1] * c[2];
// Return total count stored in res
return res;
}
public static void main(String[] args)
{
FindGroups groups = new FindGroups();
int arr[] = {3, 6, 7, 2, 9};
int n = arr.length;
System.out.println("Required number of groups are "
+ groups.findgroups(arr, n));
}
}
Python3
# Python3 Program to Count groups
# of size 2 or 3 that have sum
# as multiple of 3
# Returns count of all possible
# groups that can be formed
# from elements of a[].
def findgroups(arr, n):
# Create an array C[3] to store
# counts of elements with
# remainder 0, 1 and 2. c[i]
# would store count of elements
# with remainder i
c = [0, 0, 0]
# To store the result
res = 0
# Count elements with remainder
# 0, 1 and 2
for i in range(0, n):
c[arr[i] % 3] += 1
# Case 3.a: Count groups of size
# 2 from 0 remainder elements
res += ((c[0] * (c[0] - 1)) >> 1)
# Case 3.b: Count groups of size
# 2 with one element with 1
# remainder and other with 2 remainder
res += c[1] * c[2]
# Case 4.a: Count groups of size
# 3 with all 0 remainder elements
res += (c[0] * (c[0] - 1) * (c[0] - 2)) / 6
# Case 4.b: Count groups of size 3
# with all 1 remainder elements
res += (c[1] * (c[1] - 1) * (c[1] - 2)) / 6
# Case 4.c: Count groups of size 3
# with all 2 remainder elements
res += ((c[2] * (c[2] - 1) * (c[2] - 2)) / 6)
# Case 4.c: Count groups of size 3
# with different remainders
res += c[0] * c[1] * c[2]
# Return total count stored in res
return res
# Driver program
arr = [3, 6, 7, 2, 9]
n = len(arr)
print ("Required number of groups are",
int(findgroups(arr, n)))
# This article is contributed by shreyanshi_arun
C#
// C# Program to count all possible
// groups of size 2 or 3 that have
// sum as multiple of 3
using System;
class FindGroups
{
// Returns count of all possible
// groups that can be formed
// from elements of a[].
int findgroups(int []arr, int n)
{
// Create an array C[3] to store
// counts of elements with remainder
// 0, 1 and 2. c[i] would store
// count of elements with remainder i
int [] c= new int[]{0, 0, 0};
int i;
// To store the result
int res = 0;
// Count elements with
// remainder 0, 1 and 2
for (i = 0; i < n; i++)
c[arr[i] % 3]++;
// Case 3.a: Count groups of size
// 2 from 0 remainder elements
res += ((c[0] * (c[0] - 1)) >> 1);
// Case 3.b: Count groups of size 2
// with one element with 1 remainder
// and other with 2 remainder
res += c[1] * c[2];
// Case 4.a: Count groups of size 3
// with all 0 remainder elements
res += (c[0] * (c[0] - 1) *
(c[0] - 2)) / 6;
// Case 4.b: Count groups of size 3
// with all 1 remainder elements
res += (c[1] * (c[1] - 1) *
(c[1] - 2)) / 6;
// Case 4.c: Count groups of size 3
// with all 2 remainder elements
res += ((c[2] * (c[2] - 1) *
(c[2] - 2)) / 6);
// Case 4.c: Count groups of size 3
// with different remainders
res += c[0] * c[1] * c[2];
// Return total count stored in res
return res;
}
// Driver Code
public static void Main()
{
FindGroups groups = new FindGroups();
int []arr = {3, 6, 7, 2, 9};
int n = arr.Length;
Console.Write("Required number of groups are "
+ groups.findgroups(arr, n));
}
}
// This code is contributed by nitin mittal.
PHP
<?php
// PHP Program to Count groups of size
// 2 or 3 that have sum as multiple of 3
// Returns count of all possible groups
// that can be formed from elements of a[].
function findgroups($arr, $n)
{
// Create an array C[3] to store counts
// of elements with remainder 0, 1 and 2.
// c[i] would store count of elements
// with remainder i
$c = array(0, 0, 0);
// To store the result
$res = 0;
// Count elements with remainder
// 0, 1 and 2
for($i = 0; $i < $n; $i++)
$c[$arr[$i] % 3] += 1;
// Case 3.a: Count groups of size
// 2 from 0 remainder elements
$res += (($c[0] * ($c[0] - 1)) >> 1);
// Case 3.b: Count groups of size
// 2 with one element with 1
// remainder and other with 2 remainder
$res += $c[1] * $c[2];
// Case 4.a: Count groups of size
// 3 with all 0 remainder elements
$res += ($c[0] * ($c[0] - 1) *
($c[0] - 2)) / 6;
// Case 4.b: Count groups of size 3
// with all 1 remainder elements
$res += ($c[1] * ($c[1] - 1) *
($c[1] - 2)) / 6;
// Case 4.c: Count groups of size 3
// with all 2 remainder elements
$res += (($c[2] * ($c[2] - 1) *
($c[2] - 2)) / 6);
// Case 4.c: Count groups of size 3
// with different remainders
$res += $c[0] * $c[1] * $c[2];
// Return total count stored in res
return $res;
}
// Driver Code
$arr = array(3, 6, 7, 2, 9);
$n = count($arr);
echo "Required number of groups are " .
(int)(findgroups($arr, $n));
// This code is contributed by mits
?>
Javascript
<script>
// JavaScript Program to count all possible
// groups of size 2 or 3 that have
// sum as multiple of 3
// Returns count of all possible groups
// that can be formed from elements of a[].
function findgroups(arr, n){
// Create an array C[3] to store counts
// of elements with remainder 0, 1 and 2.
// c[i] would store count of elements
// with remainder i
let c = [0,0,0];
let i;
// To store the result
let res = 0;
// Count elements with remainder 0, 1 and 2
for (i=0; i<n; i++)
c[arr[i]%3]++;
// Case 3.a: Count groups of size 2
// from 0 remainder elements
res += ((c[0]*(c[0]-1))>>1);
// Case 3.b: Count groups of size 2 with
// one element with 1 remainder and other
// with 2 remainder
res += c[1] * c[2];
// Case 4.a: Count groups of size 3
// with all 0 remainder elements
res += (c[0] * (c[0]-1) * Math.floor((c[0]-2))/6);
// Case 4.b: Count groups of size 3
// with all 1 remainder elements
res += (c[1] * (c[1]-1) * Math.floor((c[1]-2))/6);
// Case 4.c: Count groups of size 3
// with all 2 remainder elements
res += (Math.floor(c[2]*(c[2]-1)*(c[2]-2))/6);
// Case 4.c: Count groups of size 3
// with different remainders
res += c[0]*c[1]*c[2];
// Return total count stored in res
return res;
}
// Driver Code
let arr = [3, 6, 7, 2, 9];
let n = arr.length;
document.write("Required number of groups are " + findgroups(arr,n));
</script>
Producción
Required number of groups are 8
Complejidad temporal: O(n)
Espacio auxiliar: O(1)
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