Find set of m-elements with difference of any two elements is divisible by k
Given an array of n-positive integers and a positive integer k, find a set of exactly m-elements such that difference of any two element is equal to k.
Examples :
Input : arr[] = {4, 7, 10, 6, 9}, k = 3, m = 3 Output : Yes 4 7 10 Input : arr[] = {4, 7, 10, 6, 9}, k = 12, m = 4 Output : No Input : arr[] = {4, 7, 10, 6, 9}, k = 3, m = 4 Output : No
Approach : To solve this question, just keep a record of remainders when an element is divided by k. Create a multi dimensional array remainder_set[][] of size k whose index shows remainder and elements of that array will element as per their corresponding remainder when divided by k. For example if arr[i] % k = 3 then arr[i] will be element of remainder_set[3] and so on for all elements. Now, traversing the remainder set, one can easily get a set whose size is greater than or equal to required size m if exist. And for sure difference of any elements of that set will be divisible by k.
Implementation:
C++
// C++ program for finding remainder set #include <bits/stdc++.h> using namespace std; // function to find remainder set void findSet( int arr[], int n, int k, int m) { vector< int > remainder_set[k]; // calculate remainder set array // and push element as per their remainder for ( int i = 0; i < n; i++) { int rem = arr[i] % k; remainder_set[rem].push_back(arr[i]); } // check whether sizeof any remainder set // is equal or greater than m for ( int i = 0; i < k; i++) { if (remainder_set[i].size() >= m) { cout << "Yes \n" ; for ( int j = 0; j < m; j++) cout << remainder_set[i][j] << " " ; return ; } } cout << "No" ; } // driver program int main() { int arr[] = {5, 8, 9, 12, 13, 7, 11, 15}; int k = 4; int m = 3; int n = sizeof (arr) / sizeof (arr[0]); findSet(arr, n, k, m); } |
Java
// Java program for finding remainder set import java.util.*; class GFG { // function to find remainder set static void findSet( int arr[], int n, int k, int m) { Vector<Integer> []remainder_set = new Vector[k]; for ( int i = 0 ; i < k; i++) { remainder_set[i] = new Vector<Integer>(); } // calculate remainder set array // and push element as per their remainder for ( int i = 0 ; i < n; i++) { int rem = arr[i] % k; remainder_set[rem].add(arr[i]); } // check whether sizeof any remainder set // is equal or greater than m for ( int i = 0 ; i < k; i++) { if (remainder_set[i].size() >= m) { System.out.println( "Yes" ); for ( int j = 0 ; j < m; j++) System.out.print(remainder_set[i].get(j) + " " ); return ; } } System.out.print( "No" ); } // Driver Code public static void main(String[] args) { int arr[] = { 5 , 8 , 9 , 12 , 13 , 7 , 11 , 15 }; int k = 4 ; int m = 3 ; int n = arr.length; findSet(arr, n, k, m); } } // This code is contributed by PrinciRaj1992 |
Python3
# Python3 program to find exactly m-element set # where difference of any two is divisible by k def findSet( arr, k, m): arr_size = len (arr); remainder_set = [ 0 ] * k; # initialize remainder set with blank array for i in range (k): remainder_set[i] = []; # calculate remainder set array # and push element as per their remainder for i in range (arr_size): rem = arr[i] % k; remainder_set[rem].append(arr[i]); # check whether sizeof any remainder set # is equal or greater than m for i in range (k): # if size exist then print yes and all elements if ( len (remainder_set[i]) > = m): print ( "Yes" ); for j in range (m): print (remainder_set[i][j],end = ""); print ( " " ,end = ""); # return if remainder set found return ; # print no if no remainder set found print ( "No" ); arr = [ 5 , 8 , 9 , 12 , 13 , 7 , 11 , 15 ]; k = 4 ; # constant k m = 3 ; # size of set required findSet(arr, k, m); # This code is contributed by mits. |
C#
// C# program for finding // remainder set using System; using System.Collections.Generic; class GFG { // function to find // remainder set static void findSet( int []arr, int n, int k, int m) { List< int >[] remainder_set = new List< int >[k]; for ( int i = 0; i < k; i++) remainder_set[i] = new List< int >(); // calculate remainder set // array and push element // as per their remainder for ( int i = 0; i < n; i++) { int rem = arr[i] % k; remainder_set[rem].Add(arr[i]); } // check whether sizeof // any remainder set is // equal or greater than m for ( int i = 0; i < k; i++) { if (remainder_set[i].Count >= m) { Console.Write( "Yes \n" ); for ( int j = 0; j < m; j++) Console.Write(remainder_set[i][j] + " " ); return ; } } Console.Write( "No" ); } // Driver Code static void Main() { int []arr = new int []{5, 8, 9, 12, 13, 7, 11, 15}; int k = 4; int m = 3; int n = arr.Length; findSet(arr, n, k, m); } } // This code is contributed by // Manish Shaw(manishshaw1) |
PHP
<?php // PHP program to find exactly m-element set // where difference of any two is divisible by k function findSet( $arr , $k , $m ) { $arr_size = sizeof( $arr ); // initialize remainder set with blank array for ( $i = 0; $i < $k ; $i ++) { $remainder_set [ $i ] = array (); } // calculate remainder set array // and push element as per their remainder for ( $i = 0; $i < $arr_size ; $i ++) { $rem = $arr [ $i ] % $k ; array_push ( $remainder_set [ $rem ], $arr [ $i ]); } // check whether sizeof any remainder set // is equal or greater than m for ( $i = 0; $i < $k ; $i ++) { // if size exist then print yes and all elements if (sizeof( $remainder_set [ $i ]) >= $m ) { print ( "Yes\n" ); for ( $j = 0; $j < $m ; $j ++) { print ( $remainder_set [ $i ][ $j ]); print ( " " ); } // return if remainder set found return ; } } // print no if no remainder set found print ( "No" ); } $arr = array (5, 8, 9, 12, 13, 7, 11, 15); $k = 4; // constant k $m = 3; // size of set required findset( $arr , $k , $m ); ?> |
Javascript
<script> // Javascript program to find exactly m-element set // where difference of any two is divisible by k function findSet(arr, k, m) { let arr_size = arr.length; let remainder_set = [] // initialize remainder set with blank array for (let i = 0; i < k; i++) { remainder_set[i] = new Array(); } // calculate remainder set array // and push element as per their remainder for (let i = 0; i < arr_size; i++) { let rem = arr[i] % k; remainder_set[rem].push(arr[i]); } // check whether sizeof any remainder set // is equal or greater than m for (let i = 0; i < k; i++) { // if size exist then print yes and all elements if (remainder_set[i].length >= m) { document.write( "Yes<br>" ); for (let j = 0; j < m; j++) { document.write(remainder_set[i][j]); document.write( " " ); } // return if remainder set found return ; } } // print no if no remainder set found document.write( "No" ); } let arr = [5, 8, 9, 12, 13, 7, 11, 15]; let k = 4; // constant k let m = 3; // size of set required findSet(arr, k, m); // This code is contributed by _saurabh_jaiswal </script> |
Yes 5 9 13