Dada una array de enteros y un número k, escriba una función que devuelva verdadero si la array dada se puede dividir en pares de modo que la suma de cada par sea divisible por k.
Ejemplos:
C++
// A C++ program to check if arr[0..n-1] can be divided
// in pairs such that every pair is divisible by k.
#include <bits/stdc++.h>
using namespace std;
// Returns true if arr[0..n-1] can be divided into pairs
// with sum divisible by k.
bool canPairs(int arr[], int n, int k)
{
// An odd length array cannot be divided into pairs
if (n & 1)
return false;
// Create a frequency array to count occurrences
// of all remainders when divided by k.
unordered_map<int, int> freq;
// Count occurrences of all remainders
for (int i = 0; i < n; i++)
freq[((arr[i] % k) + k) % k]++;
// Traverse input array and use freq[] to decide
// if given array can be divided in pairs
for (int i = 0; i < n; i++) {
// Remainder of current element
int rem = ((arr[i] % k) + k) % k;
// If remainder with current element divides
// k into two halves.
if (2 * rem == k) {
// Then there must be even occurrences of
// such remainder
if (freq[rem] % 2 != 0)
return false;
}
// If remainder is 0, then there must be even
// number of elements with 0 remainder
else if (rem == 0) {
if (freq[rem] & 1)
return false;
}
// Else number of occurrences of remainder
// must be equal to number of occurrences of
// k - remainder
else if (freq[rem] != freq[k - rem])
return false;
}
return true;
}
// Driver code
int main()
{
int arr[] = { 92, 75, 65, 48, 45, 35 };
int k = 10;
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
canPairs(arr, n, k) ? cout << "True" : cout << "False";
return 0;
}
Java
// JAVA program to check if arr[0..n-1] can be divided
// in pairs such that every pair is divisible by k.
import java.util.HashMap;
public class Divisiblepair {
// Returns true if arr[0..n-1] can be divided into pairs
// with sum divisible by k.
static boolean canPairs(int ar[], int k)
{
// An odd length array cannot be divided into pairs
if (ar.length % 2 == 1)
return false;
// Create a frequency array to count occurrences
// of all remainders when divided by k.
HashMap<Integer, Integer> hm = new HashMap<>();
// Count occurrences of all remainders
for (int i = 0; i < ar.length; i++) {
int rem = ((ar[i] % k) + k) % k;
if (!hm.containsKey(rem)) {
hm.put(rem, 0);
}
hm.put(rem, hm.get(rem) + 1);
}
// Traverse input array and use freq[] to decide
// if given array can be divided in pairs
for (int i = 0; i < ar.length; i++) {
// Remainder of current element
int rem = ((ar[i] % k) + k) % k;
// If remainder with current element divides
// k into two halves.
if (2 * rem == k) {
// Then there must be even occurrences of
// such remainder
if (hm.get(rem) % 2 == 1)
return false;
}
// If remainder is 0, then there must be two
// elements with 0 remainder
else if (rem == 0) {
// Then there must be even occurrences of
// such remainder
if (hm.get(rem) % 2 == 1)
return false;
}
// Else number of occurrences of remainder
// must be equal to number of occurrences of
// k - remainder
else {
if (hm.get(k - rem) != hm.get(rem))
return false;
}
}
return true;
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 92, 75, 65, 48, 45, 35 };
int k = 10;
// Function call
boolean ans = canPairs(arr, k);
if (ans)
System.out.println("True");
else
System.out.println("False");
}
}
// This code is contributed by Rishabh Mahrsee
Python3
# Python3 program to check if
# arr[0..n-1] can be divided
# in pairs such that every
# pair is divisible by k.
from collections import defaultdict
# Returns true if arr[0..n-1] can be
# divided into pairs with sum
# divisible by k.
def canPairs(arr, n, k):
# An odd length array cannot
# be divided into pairs
if (n & 1):
return 0
# Create a frequency array to
# count occurrences of all
# remainders when divided by k.
freq = defaultdict(lambda: 0)
# Count occurrences of all remainders
for i in range(0, n):
freq[((arr[i] % k) + k) % k] += 1
# Traverse input array and use
# freq[] to decide if given array
# can be divided in pairs
for i in range(0, n):
# Remainder of current element
rem = ((arr[i] % k) + k) % k
# If remainder with current element
# divides k into two halves.
if (2 * rem == k):
# Then there must be even occurrences
# of such remainder
if (freq[rem] % 2 != 0):
return 0
# If remainder is 0, then there
# must be two elements with 0 remainder
else if (rem == 0):
if (freq[rem] & 1):
return 0
# Else number of occurrences of
# remainder must be equal to
# number of occurrences of
# k - remainder
else if (freq[rem] != freq[k - rem]):
return 0
return 1
# Driver code
arr = [92, 75, 65, 48, 45, 35]
k = 10
n = len(arr)
# Function call
if (canPairs(arr, n, k)):
print("True")
else:
print("False")
# This code is contributed by Stream_Cipher
C#
// C# program to check if arr[0..n-1]
// can be divided in pairs such that
// every pair is divisible by k.
using System.Collections.Generic;
using System;
class GFG {
// Returns true if arr[0..n-1] can be
// divided into pairs with sum
// divisible by k.
static bool canPairs(int[] ar, int k)
{
// An odd length array cannot
// be divided into pairs
if (ar.Length % 2 == 1)
return false;
// Create a frequency array to count
// occurrences of all remainders when
// divided by k.
Dictionary<Double, int> hm
= new Dictionary<Double, int>();
// Count occurrences of all remainders
for (int i = 0; i < ar.Length; i++) {
int rem = ((ar[i] % k) + k) % k;
if (!hm.ContainsKey(rem)) {
hm[rem] = 0;
}
hm[rem]++;
}
// Traverse input array and use freq[]
// to decide if given array can be
// divided in pairs
for (int i = 0; i < ar.Length; i++) {
// Remainder of current element
int rem = ((ar[i] % k) + k) % k;
// If remainder with current element
// divides k into two halves.
if (2 * rem == k) {
// Then there must be even occurrences
// of such remainder
if (hm[rem] % 2 == 1)
return false;
}
// If remainder is 0, then there
// must be two elements with 0
// remainder
else if (rem == 0) {
// Then there must be even occurrences
// of such remainder
if (hm[rem] % 2 == 1)
return false;
}
// Else number of occurrences of remainder
// must be equal to number of occurrences of
// k - remainder
else {
if (hm[k - rem] != hm[rem])
return false;
}
}
return true;
}
// Driver code
public static void Main()
{
int[] arr = { 92, 75, 65, 48, 45, 35 };
int k = 10;
// Function call
bool ans = canPairs(arr, k);
if (ans)
Console.WriteLine("True");
else
Console.WriteLine("False");
}
}
// This code is contributed by Stream_Cipher
Javascript
<script>
// Javascript program to check if arr[0..n-1] can be divided
// in pairs such that every pair is divisible by k.
// Returns true if arr[0..n-1] can be divided into pairs
// with sum divisible by k.
function canPairs(ar, k)
{
// An odd length array cannot be divided into pairs
if (ar.length % 2 == 1)
return false;
// Create a frequency array to count occurrences
// of all remainders when divided by k.
let hm = new Map();
// Count occurrences of all remainders
for (let i = 0; i < ar.length; i++) {
let rem = ((ar[i] % k) + k) % k;
if (!hm.has(rem)) {
hm.set(rem, 0);
}
hm.set(rem, hm.get(rem) + 1);
}
// Traverse input array and use freq[] to decide
// if given array can be divided in pairs
for (let i = 0; i < ar.length; i++) {
// Remainder of current element
let rem = ((ar[i] % k) + k) % k;
// If remainder with current element divides
// k into two halves.
if (2 * rem == k) {
// Then there must be even occurrences of
// such remainder
if (hm.get(rem) % 2 == 1)
return false;
}
// If remainder is 0, then there must be two
// elements with 0 remainder
else if (rem == 0) {
// Then there must be even occurrences of
// such remainder
if (hm.get(rem) % 2 == 1)
return false;
}
// Else number of occurrences of remainder
// must be equal to number of occurrences of
// k - remainder
else {
if (hm.get(k - rem) != hm.get(rem))
return false;
}
}
return true;
}
// Driver program
let arr = [ 92, 75, 65, 48, 45, 35 ];
let k = 10;
// Function call
let ans = canPairs(arr, k);
if (ans)
document.write("True");
else
document.write("False");
</script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA