Find set of m-elements with difference of any two elements is divisible by k

0 0 5 minutes read

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>

Output:

Yes 
5 9 13

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!