Cuente los pares en una array cuya suma sea divisible por 4

Dada una array si ‘n’ enteros positivos. Cuente el número de pares de enteros en la array que tienen la suma divisible por 4. 

Ejemplos:

Input: {2, 2, 1, 7, 5}
Output: 3

Explanation:
Only three pairs are possible whose sum
is divisible by '4' i.e., (2, 2), 
(1, 7) and (7, 5)

Input: {2, 2, 3, 5, 6}
Output: 4

El enfoque ingenuo es iterar a través de cada par de arrays pero usando dos bucles for anidados y contar aquellos pares cuya suma es divisible por ‘4’. La complejidad temporal de este enfoque es O(n ² ).

El enfoque eficiente es utilizar la técnica Hashing. Solo pueden surgir tres condiciones cuya suma sea divisible por ‘4’, es decir,

1. Si ambos son divisibles por 4.
2. Si uno de ellos es igual a 1 módulo 4 y el otro es 3 módulo 4 . Por ejemplo, (1, 3), (5, 7), (5, 11).
3. Si ambos son iguales a 2 módulo 4 es decir, (2, 2), (2, 6), (6, 10)

Almacene todos los módulos en el arreglo freq[] tal que freq[i] = número de elementos del arreglo que son iguales a
i módulo 4

Entonces responde =>
 

 

 

Implementación:

// C++ Program to count pairs
// whose sum divisible by '4'
#include <bits/stdc++.h>
using namespace std;
 
// Program to count pairs whose sum divisible
// by '4'
int count4Divisibiles(int arr[], int n)
{
    // Create a frequency array to count
    // occurrences of all remainders when
    // divided by 4
    int freq[4] = {0, 0, 0, 0};
 
    // Count occurrences of all remainders
    for (int i = 0; i < n; i++)
        ++freq[arr[i] % 4];
 
    // If both pairs are divisible by '4'
    int ans = freq[0] * (freq[0] - 1) / 2;
 
    // If both pairs are 2 modulo 4
    ans += freq[2] * (freq[2] - 1) / 2;
 
    // If one of them is equal
    // to 1 modulo 4 and the
    // other is equal to 3
    // modulo 4
    ans += freq[1] * freq[3];
 
    return ans;
}
 
// Driver code
int main()
{
 
    int arr[] = { 2, 2, 1, 7, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    cout << count4Divisibiles(arr, n);
 
    return 0;
}

// Java program to count pairs
// whose sum divisible by '4'
import java.util.*;
 
class Count{
    public static int count4Divisibiles(int arr[] ,
                                            int n )
    {
        // Create a frequency array to count
        // occurrences of all remainders when
        // divided by 4
        int freq[] = {0, 0, 0, 0};
        int i = 0;
        int ans;
         
        // Count occurrences of all remainders
        for (i = 0; i < n; i++)
                ++freq[arr[i] % 4];
         
        //If both pairs are divisible by '4'
        ans = freq[0] * (freq[0] - 1) / 2;
     
        // If both pairs are 2 modulo 4
        ans += freq[2] * (freq[2] - 1) / 2;
     
        // If one of them is equal
        // to 1 modulo 4 and the
        // other is equal to 3
        // modulo 4
        ans += freq[1] * freq[3];
     
        return (ans);
    }
    public static void main(String[] args)
    {
        int arr[] = {2, 2, 1, 7, 5};
        int n = 5;
        System.out.print(count4Divisibiles(arr, n));
    }
}
 
// This code is contributed by rishabh_jain

# Python3 code to count pairs whose
# sum is divisible by '4'
 
# Function to count pairs whose
# sum is divisible by '4'
def count4Divisibiles( arr , n ):
     
    # Create a frequency array to count
    # occurrences of all remainders when
    # divided by 4
    freq = [0, 0, 0, 0]
     
    # Count occurrences of all remainders
    for i in range(n):
        freq[arr[i] % 4]+=1
         
    #If both pairs are divisible by '4'
    ans = freq[0] * (freq[0] - 1) / 2
     
    # If both pairs are 2 modulo 4
    ans += freq[2] * (freq[2] - 1) / 2
     
    # If one of them is equal
    # to 1 modulo 4 and the
    # other is equal to 3
    # modulo 4
    ans += freq[1] * freq[3]
     
    return int(ans)
 
# Driver code
arr = [2, 2, 1, 7, 5]
n = len(arr)
print(count4Divisibiles(arr, n))
 
# This code is contributed by "Sharad_Bhardwaj".

// C# program to count pairs
// whose sum divisible by '4'
using System;
 
class Count{
    public static int count4Divisibiles(int []arr ,
                                            int n )
    {
        // Create a frequency array to count
        // occurrences of all remainders when
        // divided by 4
        int []freq = {0, 0, 0, 0};
        int i = 0;
        int ans;
         
        // Count occurrences of all remainders
        for (i = 0; i < n; i++)
            ++freq[arr[i] % 4];
         
        //If both pairs are divisible by '4'
        ans = freq[0] * (freq[0] - 1) / 2;
     
        // If both pairs are 2 modulo 4
        ans += freq[2] * (freq[2] - 1) / 2;
     
        // If one of them is equal
        // to 1 modulo 4 and the
        // other is equal to 3
        // modulo 4
        ans += freq[1] * freq[3];
     
        return (ans);
    }
     
    // Driver code
    public static void Main()
    {
        int []arr = {2, 2, 1, 7, 5};
        int n = 5;
        Console.WriteLine(count4Divisibiles(arr, n));
    }
}
 
// This code is contributed by vt_m

<?php
// PHP Program to count pairs
// whose sum divisible by '4'
 
// Program to count pairs whose
// sum divisible by '4'
function count4Divisibiles($arr, $n)
{
    // Create a frequency array to
    // count occurrences of all
    // remainders when divided by 4
    $freq = array(0, 0, 0, 0);
 
    // Count occurrences
    // of all remainders
    for ( $i = 0; $i < $n; $i++)
        ++$freq[$arr[$i] % 4];
 
    // If both pairs are
    // divisible by '4'
    $ans = $freq[0] *
        ($freq[0] - 1) / 2;
 
    // If both pairs are
    // 2 modulo 4
    $ans += $freq[2] *
        ($freq[2] - 1) / 2;
 
    // If one of them is equal
    // to 1 modulo 4 and the
    // other is equal to 3
    // modulo 4
    $ans += $freq[1] * $freq[3];
 
    return $ans;
}
 
// Driver code
$arr = array(2, 2, 1, 7, 5);
$n = sizeof($arr) ;
 
echo count4Divisibiles($arr, $n);
 
// This code is contributed by ajit
?>

// JavaScript Program to count pairs
// whose sum divisible by '4'
 
// Program to count pairs whose sum divisible
// by '4'
function count4Divisibiles(arr, n)
{
    // Create a frequency array to count
    // occurrences of all remainders when
    // divided by 4
    let freq = [0, 0, 0, 0];
 
    // Count occurrences of all remainders
    for (var i = 0; i < n; i++)
        ++freq[arr[i] % 4];
 
    // If both pairs are divisible by '4'
    let ans = Math.floor(freq[0] * (freq[0] - 1) / 2);
 
    // If both pairs are 2 modulo 4
    ans += Math.floor(freq[2] * (freq[2] - 1) / 2);
 
    // If one of them is equal
    // to 1 modulo 4 and the
    // other is equal to 3
    // modulo 4
    ans += freq[1] * freq[3];
 
    return ans;
}
 
// Driver code
let arr = [ 2, 2, 1, 7, 5 ];
let n = arr.length;
 
console.log(count4Divisibiles(arr, n));
 
 
 
// This code is contributed by phasing17

3

Complejidad temporal: O(n)
Espacio auxiliar: O(1)