Print k numbers where all pairs are divisible by m
Given an integer array and two numbers k and m. Print k numbers from the array, such that difference between any two pairs is divisible by m. If there are no k numbers, then print -1.
Examples:
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.
A naive approach is to iterate for every element and check with all other elements, and if the count of numbers whose difference is divisible by m is greater than equal to k, then we print those k numbers by again iterating. But this won’t be efficient enough as it runs two nested loops.
C++
#include <iostream> #include <vector> using namespace std; vector< int > find_k_numbers(vector< int >& arr, int k, int m) { vector< int > result; for ( int i = 0; i < arr.size(); i++) { if (result.size() == k) { break ; } for ( int j = i + 1; j < arr.size(); j++) { if ((arr[i] - arr[j]) % m == 0) { result.push_back(arr[i]); if (result.size() == k) { break ; } result.push_back(arr[j]); if (result.size() == k) { break ; } } } } if (result.size() == k) { return result; } else { return { -1 }; } } int main() { vector< int > arr = { 1, 8, 4 }; int k = 2; int m = 3; vector< int > result = find_k_numbers(arr, k, m); for ( int i = 0; i < result.size(); i++) { cout << result[i] << " " ; } return 0; } |
Java
// Java code addition import java.util.ArrayList; public class Main { // Java function to find k numbers that satisfy the condition public static ArrayList<Integer> findKNumbers(ArrayList<Integer> arr, int k, int m) { ArrayList<Integer> result = new ArrayList<>(); // initialize an empty ArrayList to store the k numbers that satisfy the condition for ( int i = 0 ; i < arr.size(); i++) { if (result.size() == k) { // if we've already found k numbers, stop searching break ; } for ( int j = i + 1 ; j < arr.size(); j++) { // loop over all numbers after the i-th number to avoid duplicates if ((arr.get(i) - arr.get(j)) % m == 0 ) { // if the difference between i-th and // j-th number is divisible by m, // add them to the result ArrayList result.add(arr.get(i)); if (result.size() == k) { // if we've already found k numbers, stop searching break ; } result.add(arr.get(j)); if (result.size() == k) { // if we've already found k numbers, stop searching break ; } } } } if (result.size() == k) { // if we've found k numbers that satisfy // the condition, return the result ArrayList return result; } else { // otherwise, return -1 to indicate that // there are no k numbers that satisfy the condition return new ArrayList<Integer>(java.util.Arrays.asList(- 1 )); } } public static void main(String[] args) { // example usage ArrayList<Integer> arr = new ArrayList<Integer>(); arr.add( 1 ); arr.add( 8 ); arr.add( 4 ); int k = 2 ; int m = 3 ; ArrayList<Integer> result = findKNumbers(arr, k, m); for ( int i = 0 ; i < result.size(); i++) { System.out.print(result.get(i) + " " ); // prints [1, 4] } } } // The code is contributed by Arushi Goel. |
Python3
def find_k_numbers(arr, k, m): result = [] # initialize an empty list to store the k numbers that satisfy the condition for i in range ( len (arr)): # loop over all possible pairs of numbers in the array if len (result) = = k: # if we've already found k numbers, stop searching break # loop over all numbers after the i-th number to avoid duplicates for j in range (i + 1 , len (arr)): # if the difference between i-th and j-th number is divisible by m, add them to the result list if (arr[i] - arr[j]) % m = = 0 : result.append(arr[i]) if len (result) = = k: # if we've already found k numbers, stop searching break result.append(arr[j]) if len (result) = = k: # if we've already found k numbers, stop searching break if len (result) = = k: # if we've found k numbers that satisfy the condition, return the result list return result else : # otherwise, return -1 to indicate that there are no k numbers that satisfy the condition return - 1 # example usage arr = [ 1 , 8 , 4 ] k = 2 m = 3 print (find_k_numbers(arr, k, m)) # prints [1, 4] |
C#
using System; using System.Collections.Generic; class Program { static List< int > FindKNumbers(List< int > arr, int k, int m) { List< int > result = new List< int >(); for ( int i = 0; i < arr.Count; i++) { // Check if we have already found k numbers if (result.Count == k) { break ; } for ( int j = i + 1; j < arr.Count; j++) { // Check if (arr[i] - arr[j]) is divisible // by m if ((arr[i] - arr[j]) % m == 0) { // Add arr[i] and arr[j] to the result // list result.Add(arr[i]); if (result.Count == k) { break ; } result.Add(arr[j]); if (result.Count == k) { break ; } } } } // Check if we have found k numbers if (result.Count == k) { return result; } else { return new List< int >() { -1 }; } } static void Main( string [] args) { List< int > arr = new List< int >() { 1, 8, 4 }; int k = 2; int m = 3; List< int > result = FindKNumbers(arr, k, m); // Print the result for ( int i = 0; i < result.Count; i++) { Console.Write(result[i] + " " ); } } } |
Javascript
// JavaScript function to find k numbers that satisfy the condition function find_k_numbers(arr, k, m) { const result = []; // initialize an empty array to store the k numbers that satisfy the condition for (let i = 0; i < arr.length; i++) { if (result.length === k) { // if we've already found k numbers, stop searching break ; } for (let j = i + 1; j < arr.length; j++) { // loop over all numbers after // the i-th number to avoid duplicates if ((arr[i] - arr[j]) % m === 0) { // if the difference between i-th and // j-th number is divisible by m, // add them to the result array result.push(arr[i]); if (result.length === k) { // if we've already found k numbers, stop searching break ; } result.push(arr[j]); if (result.length === k) { // if we've already found k numbers, stop searching break ; } } } } if (result.length === k) { // if we've found k numbers that satisfy // the condition, return the result array return result; } else { // otherwise, return -1 to indicate that // there are no k numbers that satisfy the condition return -1; } } // example usage const arr = [1, 8, 4]; const k = 2; const m = 3; console.log(find_k_numbers(arr, k, m)); // prints [1, 4] |
[1, 4]
Time complexity: O(n * n)
Auxiliary space: O(1)
An efficient approach is apply a mathematical approach, where we know if (x-y) % m is equal to x%m – y%m. So if we can store all the numbers who leave the same remainder when divided by m,
And if the count of numbers which leaves the same remainder is more than k or equal to k, then we have our answer as all those numbers who leave the same remainder.
Below is the implementation of the above approach
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> |
Output:
1 4
Time complexity: O(n)
Auxiliary Space: O(m)