Subconjunto sin suma de pares divisible por K

Dada una array de números enteros, necesitamos encontrar el tamaño máximo de un subconjunto tal que la suma de cada par de este subconjunto no sea divisible por K. 

Ejemplos: 

Input :  arr[] = [3, 7, 2, 9, 1]        
         K = 3
Output : 3
Maximum size subset whose each pair sum 
is not divisible by K is [3, 7, 1] because,
3+7 = 10,    
3+1 = 4,    
7+1 = 8        all are not divisible by 3.
It is not possible to get a subset of size 
bigger than 3 with the above-mentioned property.

Input : arr[] = [3, 17, 12, 9, 11, 15]
        K = 5
Output : 4  

Podemos resolver este problema calculando el módulo de los números de array con K. Si la suma de dos números es divisible por K, entonces si uno de ellos da el resto i, el otro dará el resto (K – i). Primero almacenamos frecuencias de números que dan un resto específico en una array de frecuencias de tamaño K. Luego hacemos un bucle para todos los restos i e incluimos max(f[i], f[K – i]). ¿Por qué? un subconjunto sin suma de pares divisible por K debe incluir elementos con resto f[i] o con resto f[K – i]. Dado que queremos maximizar el tamaño del subconjunto, elegimos un máximo de dos tamaños. 

En la siguiente array de códigos, los números con resto 0 y resto K/2 se manejan por separado. Si incluimos más de 2 números con resto 0, entonces su suma será divisible por K, por lo que hemos tomado como máximo 1 número en nuestra consideración, lo mismo ocurre con los números de array que dan resto K/2.

Implementación:

// C++ program to get size of subset whose
// each pair sum is not divisible by K
#include <bits/stdc++.h>
using namespace std;
 
// Returns maximum size of subset with no pair
// sum divisible by K
int subsetPairNotDivisibleByK(int arr[], int N,
                                         int K)
{
    // Array for storing frequency of modulo
    // values
    int f[K];
    memset(f, 0, sizeof(f));
 
    // Fill frequency array with values modulo K
    for (int i = 0; i < N; i++)
        f[arr[i] % K]++;
 
    //  if K is even, then update f[K/2]
    if (K % 2 == 0)
        f[K/2] = min(f[K/2], 1);
 
    // Initialize result by minimum of 1 or
    // count of numbers giving remainder 0
    int res = min(f[0], 1);
 
    // Choose maximum of count of numbers
    // giving remainder i or K-i
    for (int i = 1; i <= K/2; i++)
        res += max(f[i], f[K-i]);
 
    return res;
}
 
//  Driver code to test above methods
int main()
{
    int arr[] = {3, 7, 2, 9, 1};
    int N = sizeof(arr) / sizeof(arr[0]);
    int K = 3;
    cout << subsetPairNotDivisibleByK(arr, N, K);
    return 0;
}

// Java program to get size of subset whose
// each pair sum is not divisible by K
import java.util.Arrays;
 
class Test {
     
    // Returns maximum size of subset with no pair
    // sum divisible by K
    static int subsetPairNotDivisibleByK(int arr[],
                                      int N, int K)
    {
         
        // Array for storing frequency of modulo
        // values
        int f[] = new int[K];
        Arrays.fill(f, 0);
     
        // Fill frequency array with values modulo K
        for (int i = 0; i < N; i++)
            f[arr[i] % K]++;
     
        // if K is even, then update f[K/2]
        if (K % 2 == 0)
            f[K/2] = Math.min(f[K/2], 1);
     
        // Initialize result by minimum of 1 or
        // count of numbers giving remainder 0
        int res = Math.min(f[0], 1);
     
        // Choose maximum of count of numbers
        // giving remainder i or K-i
        for (int i = 1; i <= K/2; i++)
            res += Math.max(f[i], f[K-i]);
     
        return res;
    }
     
    // Driver method
    public static void main(String[] args)
    {
         
        int arr[] = {3, 7, 2, 9, 1};
        int N = arr.length;
        int K = 3;
         
        System.out.print(subsetPairNotDivisibleByK(
                                         arr, N, K));
    }
}
 
// This code is contributed by Anant Agarwal.

# Python3 program to get size of
# subset whose each pair sum is
# not divisible by K
 
# Returns maximum size of subset
# with no pair sum divisible by K
def subsetPairNotDivisibleByK(arr, N, K):
 
    # Array for storing frequency
    # of modulo values
    f = [0 for i in range(K)]
 
    # Fill frequency array with
    # values modulo K
    for i in range(N):
        f[arr[i] % K] += 1
 
    # if K is even, then update f[K/2]
    if (K % 2 == 0):
        f[K//2] = min(f[K//2], 1)
 
    # Initialize result by minimum of 1 or
    # count of numbers giving remainder 0
    res = min(f[0], 1)
 
    # Choose maximum of count of numbers
    # giving remainder i or K-i
    for i in range(1,(K // 2) + 1):
        res += max(f[i], f[K - i])
 
    return res
     
# Driver Code
arr = [3, 7, 2, 9, 1]
N = len(arr)
K = 3
print(subsetPairNotDivisibleByK(arr, N, K))
 
# This code is contributed by Anant Agarwal.

// C# program to get size of subset whose
// each pair sum is not divisible by K
using System;
 
class Test {
     
    // Returns maximum size of subset
    // with no pair sum divisible by K
    static int subsetPairNotDivisibleByK(int []arr,
                                         int N, int K)
    {
        // Array for storing
        // frequency of modulo values
        int []f = new int[K];
        for(int i = 0; i < K; i++)
        f[i] = 0;
         
     
        // Fill frequency array with values modulo K
        for (int i = 0; i < N; i++)
            f[arr[i] % K]++;
     
        // if K is even, then update f[K/2]
        if (K % 2 == 0)
            f[K/2] = Math.Min(f[K/2], 1);
     
        // Initialize result by minimum of 1 or
        // count of numbers giving remainder 0
        int res = Math.Min(f[0], 1);
     
        // Choose maximum of count of numbers
        // giving remainder i or K-i
        for (int i = 1; i <= K/2; i++)
            res += Math.Max(f[i], f[K-i]);
     
        return res;
    }
     
    // Driver method
    public static void Main()
    {
        int []arr = {3, 7, 2, 9, 1};
        int N = arr.Length;
        int K = 3;
         
        // Function calling
        Console.Write(subsetPairNotDivisibleByK(arr, N, K));
    }
}
 
// This code is contributed by nitin mittal.

<?php
// PHP program to get size of subset whose
// each pair sum is not divisible by K
 
// Returns maximum size of subset with
// no pair sum divisible by K
function subsetPairNotDivisibleByK(&$arr, $N, $K)
{
    // Array for storing frequency of
    // modulo values
    $f = array_fill(0, $K, NULL);
 
    // Fill frequency array with
    // values modulo K
    for ($i = 0; $i < $N; $i++)
        $f[$arr[$i] % $K]++;
 
    // if K is even, then update f[K/2]
    if ($K % 2 == 0)
        $f[$K / 2] = min($f[$K / 2], 1);
 
    // Initialize result by minimum of 1 or
    // count of numbers giving remainder 0
    $res = min($f[0], 1);
 
    // Choose maximum of count of numbers
    // giving remainder i or K-i
    for ($i = 1; $i <= $K / 2; $i++)
        $res += max($f[$i], $f[$K - $i]);
 
    return $res;
}
 
// Driver Code
$arr = array(3, 7, 2, 9, 1);
$N = sizeof($arr);
$K = 3;
echo subsetPairNotDivisibleByK($arr, $N, $K);
 
// This code is contributed by ita_c
?>

<script>
 
// Javascript program to get size of subset whose
// each pair sum is not divisible by K
     
    // Returns maximum size of subset with no pair
    // sum divisible by K
    function subsetPairNotDivisibleByK(arr,N,K)
    {
        // Array for storing frequency of modulo
        // values
        let f = new Array(K);
        for(let i=0;i<K;i++)
        {
            f[i]=0;
        }
         
         
       
        // Fill frequency array with values modulo K
        for (let i = 0; i < N; i++)
            f[arr[i] % K]++;
       
        // if K is even, then update f[K/2]
        if (K % 2 == 0)
            f[K/2] = Math.min(f[K/2], 1);
       
        // Initialize result by minimum of 1 or
        // count of numbers giving remainder 0
        let res = Math.min(f[0], 1);
       
        // Choose maximum of count of numbers
        // giving remainder i or K-i
        for (let i = 1; i <= K/2; i++)
            res += Math.max(f[i], f[K-i]);
       
        return res;
    }
     
    let arr=[3, 7, 2, 9, 1];
    let N = arr.length;
    let K = 3;
    document.write(subsetPairNotDivisibleByK(
                                         arr, N, K));
     
    // This code is contributed by avanitrachhadiya2155
 
</script>

3

Complejidad temporal: O(N + K) 
Espacio auxiliar: O(K)

Este artículo es una contribución de Utkarsh Trivedi . 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.