Imprime k números donde todos los pares son divisibles por m

Dada una array de enteros y dos números k y m. Imprima k números de la array, de modo que la diferencia entre dos pares cualesquiera sea divisible por m. Si no hay k números, imprima -1.
Ejemplos: 
 

Input: arr[] = {1, 8, 4}
           k = 2 
           m = 3    
Output: 1 4 
Explanation: Difference between
1 and 4 is divisible by 3.

Input: arr[] = {1, 8, 4} 
       k = 3 
       m = 3 
Output: -1 
Explanation: there are only two numbers 
whose difference is divisible by m, but 
k is three here which is not possible, 
hence we print -1.

Un enfoque ingenuo es iterar para cada elemento y verificar con todos los demás elementos, y si el recuento de números cuya diferencia es divisible por m es mayor que k, entonces imprimimos esos k números iterando nuevamente. Pero esto no será lo suficientemente eficiente ya que ejecuta dos bucles anidados. 
Complejidad temporal: O(n * n) 
Espacio auxiliar: O(1) 
Un enfoque eficiente es aplicar un enfoque matemático, donde sabemos si (xy) % m es igual a x%m – y%m. Entonces, si podemos almacenar todos los números que dejan el mismo resto cuando se dividen por m, 
y si la cuenta de los números que dejan el mismo resto es mayor que k o igual a k, entonces tenemos nuestra respuesta como todos esos números que dejan el mismo resto. mismo resto.
A continuación se muestra la implementación del enfoque anterior. 
 

// CPP program to find a list of k elements from
// an array such that difference between all of
// them is divisible by m.
#include <bits/stdc++.h>
using namespace std;
 
// function to generate k numbers whose difference
// is divisible by m
void print_result(int a[], int n, int k, int m)
{
    // Using an adjacency list like representation
    // to store numbers that lead to same
    // remainder.
    vector<int> v[m];
 
    for (int i = 0; i < n; i++) {
 
        // stores the modulus when divided
        // by m
        int rem = a[i] % m;
 
        v[rem].push_back(a[i]);
         
        // If we found k elements which
        // have same remainder.
        if (v[rem].size() == k)
        {
            for (int j = 0; j < k; j++)
                cout << v[rem][j] << " ";
            return;            
        }
    }
   
    // If we could not find k elements
    cout << "-1";
}
 
// driver program to test the above function
int main()
{
    int a[] = { 1, 8, 4 };
    int n = sizeof(a) / sizeof(a[0]);
    print_result(a, n, 2, 3);
    return 0;
}

// Java program to find a list of k elements from
// an array such that difference between all of
// them is divisible by m.
import java.util.*;
class GFG
{
 
// function to generate k numbers whose difference
// is divisible by m
static void print_result(int a[], int n,
                         int k, int m)
{
    // Using an adjacency list like representation
    // to store numbers that lead to same
    // remainder.
    Vector<Vector<Integer>> v = new Vector<Vector<Integer>>(m);
    for(int i = 0; i < m; i++)
        v.add(new Vector<Integer>());
 
    for (int i = 0; i < n; i++)
    {
 
        // stores the modulus when divided
        // by m
        int rem = a[i] % m;
 
        v.get(rem).add(a[i]);
         
        // If we found k elements which
        // have same remainder.
        if (v.get(rem).size() == k)
        {
            for (int j = 0; j < k; j++)
                System.out.print(v.get(rem).get(j) + " ");
            return;            
        }
    }
     
    // If we could not find k elements
    System.out.print("-1");
}
 
// Driver Code
public static void main(String[] args)
{
    int a[] = { 1, 8, 4 };
    int n = a.length;
    print_result(a, n, 2, 3);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find a list of k elements from
# an array such that difference between all of
# them is divisible by m.
 
# function to generate k numbers whose difference
# is divisible by m
def print_result(a, n, k, m):
 
    # Using an adjacency list like representation
    # to store numbers that lead to same
    # remainder.
    v = [[] for i in range(m)]
 
    for i in range(0, n):
 
        # stores the modulus when divided
        # by m
        rem = a[i] % m
 
        v[rem].append(a[i])
 
        # If we found k elements which
        # have same remainder.
        if(len(v[rem]) == k):
 
            for j in range(0, k):
                print(v[rem][j], end=" ")
            return
 
    # If we could not find k elements
    print(-1)
 
# driver program to test the above function
if __name__=='__main__':
    a = [1, 8, 4]
    n = len(a)
    print_result(a, n, 2, 3)
 
# This code is contributed by
# Sanjit_Prasad

// C# program to find a list of k elements from
// an array such that difference between all of
// them is divisible by m.
using System;
using System.Collections.Generic;
 
class GFG
{
 
// function to generate k numbers whose difference
// is divisible by m
static void print_result(int []a, int n,
                         int k, int m)
{
    // Using an adjacency list like representation
    // to store numbers that lead to same
    // remainder.
    List<List<int>> v = new List<List<int>>(m);
    for(int i = 0; i < m; i++)
        v.Add(new List<int>());
 
    for (int i = 0; i < n; i++)
    {
 
        // stores the modulus when divided
        // by m
        int rem = a[i] % m;
 
        v[rem].Add(a[i]);
         
        // If we found k elements which
        // have same remainder.
        if (v[rem].Count == k)
        {
            for (int j = 0; j < k; j++)
                Console.Write(v[rem][j] + " ");
            return;            
        }
    }
     
    // If we could not find k elements
    Console.Write("-1");
}
 
// Driver Code
public static void Main(String[] args)
{
    int []a = { 1, 8, 4 };
    int n = a.Length;
    print_result(a, n, 2, 3);
}
}
 
// This code is contributed by PrinciRaj1992

<?php
// PHP program to find a list of k elements
// from an array such that difference between
// all of them is divisible by m.
 
// function to generate k numbers whose
// difference is divisible by m
function print_result($a, $n, $k, $m)
{
    // Using an adjacency list like representation
    // to store numbers that lead to same
    // remainder.
    $v = array_fill(0, $m + 1, array());
 
    for ($i = 0; $i < $n; $i++)
    {
 
        // stores the modulus when divided
        // by m
        $rem = $a[$i] % $m;
 
        array_push($v[$rem], $a[$i]);
         
        // If we found k elements which
        // have same remainder.
        if (count($v[$rem]) == $k)
        {
            for ($j = 0; $j < $k; $j++)
                echo $v[$rem][$j] . " ";
            return;        
        }
    }
 
    // If we could not find k elements
    echo "-1";
}
 
// Driver Code
$a = array( 1, 8, 4 );
$n = count($a);
print_result($a, $n, 2, 3);
 
// This code is contributed by mits
?>

<script>
 
// JavaScript program to find a list of k elements from
// an array such that difference between all of
// them is divisible by m.
 
// function to generate k numbers whose difference
// is divisible by m
function print_result(a, n, k, m)
{
    // Using an adjacency list like representation
    // to store numbers that lead to same
    // remainder.
    var v = Array.from(Array(m), ()=> Array());
 
    for (var i = 0; i < n; i++) {
 
        // stores the modulus when divided
        // by m
        var rem = a[i] % m;
 
        v[rem].push(a[i]);
         
        // If we found k elements which
        // have same remainder.
        if (v[rem].length == k)
        {
            for (var j = 0; j < k; j++)
                document.write( v[rem][j] + " ");
            return;            
        }
    }
   
    // If we could not find k elements
    document.write( "-1");
}
 
// driver program to test the above function
var a = [1, 8, 4];
var n = a.length;
print_result(a, n, 2, 3);
 
</script>

Producción:  

1 4 

Complejidad del tiempo: O(n) 
Espacio auxiliar: O(m) 
Este artículo es una contribución de Raja Vikramaditya . 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 contribuir@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.