打印所有对都可以被m整除的k个数字-yiteyi-C++库

给定一个整数数组和两个数字k和m。从数组中打印k个数字，这样任意两对之间的差可以被m整除。如果没有k个数字，则打印-1。 例如：

null

Input: arr[] = {1, 8, 4}           k = 2            m = 3    Output: 1 4 Explanation: Difference between1 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.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 幼稚的方法 对每个元素进行迭代，并与所有其他元素进行检查，如果差值可被m整除的数字的计数大于等于k，则我们通过再次迭代来打印这些k个数字。但这不够有效，因为它运行两个嵌套循环。时间复杂度：O（n*n）辅助空间：O（1）一 有效的方法 应用数学方法，我们知道（x-y）%m是否等于x%m–y%m。因此，如果我们可以存储所有在除以m时留下相同余数的数字，如果留下相同余数的数大于或等于，那么我们的答案就是所有留下相同余数的数。下面是上述方法的实现

C++

                         // 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

                         // 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

                         # 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#

                         // 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                       
                         // 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                       
                         ?>                       

Javascript

                         <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>                       

输出：

1 4

时间复杂性： O（n） 辅助空间： O（m）本文由 拉贾·维克拉马蒂亚 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章