Dada una array de n enteros positivos y un entero positivo k, encuentre un conjunto de exactamente m elementos tal que la diferencia de dos elementos cualesquiera sea igual a k.
Ejemplos:
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
Enfoque: para resolver esta pregunta, simplemente mantenga un registro de los residuos cuando un elemento se divide por k. Cree una array multidimensional rest_set[][] de tamaño k cuyo índice muestre el resto y los elementos de esa array serán elementos según su resto correspondiente cuando se dividan por k. Por ejemplo, si arr[i] % k = 3, entonces arr[i] será un elemento de rest_set[3] y así sucesivamente para todos los elementos. Ahora, atravesando el conjunto restante, uno puede obtener fácilmente un conjunto cuyo tamaño es mayor o igual al tamaño requerido m si existe. Y seguro que la diferencia de cualquier elemento de ese conjunto será divisible por k.
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>
Producción:
Yes 5 9 13
Publicación traducida automáticamente
Artículo escrito por Shivam.Pradhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA