Count all possible groups of size 2 or 3 that have sum as multiple of 3

Given an unsorted integer (positive values only) array of size ‘n’, we can form a group of two or three, the group should be such that the sum of all elements in that group is a multiple of 3. Count all possible number of groups that can be generated in this way.
Examples:

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}

The idea is to see remainder of every element when divided by 3. A set of elements can form a group only if sun of their remainders is multiple of 3.
For example : 8, 4, 12. Now, the remainders are 2, 1, and 0 respectively. This means 8 is 2 distance away from 3s multiple (6), 4 is 1 distance away from 3s multiple(3), and 12 is 0 distance away. So, we can write the sum as 8 (can be written as 6+2), 4 (can be written as 3+1), and 12 (can be written as 12+0). Now the sum of 8, 4 and 12 can be written as 6+2+3+1+12+0. Now, 6+3+12 will always be divisible by 3 as all the terms are multiple of three. Now, we only need to check if 2+1+0 (remainders) is divisible by 3 or not which makes the complete sum divisible by 3.
Since the task is to enumerate groups, we count all elements with different remainders.

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.

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
", 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 
?> 

Output:

Required number of groups are 8

Time Complexity: O(n)
Auxiliary Space: O(1)

Count all possible groups of size 2 or 3 that have sum as multiple of 3

C++

C

Java

Python3

C#

PHP

tags:

leave a comment

0 Comments

Subscribe to Our Newsletter

Top Followed books