Рубрики

Проверьте, можно ли разбить массив на пары, сумма которых делится на k

Учитывая массив целых чисел и число k, напишите функцию, которая возвращает true, если данный массив можно разделить на пары так, чтобы сумма каждой пары делилась на k.

Примеры:

Input: arr[] = {9, 7, 5, 3},
k = 6
Output: True
We can divide array into (9, 3) and
(7, 5). Sum of both of these pairs
is a multiple of 6.

Input: arr[] = {92, 75, 65, 48, 45, 35},
k = 10
Output: True
We can divide array into (92, 48), (75, 65)
and (45, 35). Sum of all these pairs is a
multiple of 10.

Input: arr[] = {91, 74, 66, 48}, k = 10
Output: False

Простое решение состоит в том, чтобы перебрать каждый элемент arr [i]. Найдите, есть ли еще один еще не посещенный элемент, который имеет остаток как (k — arr [i]% k) . Если такого элемента нет, верните false. Если пара найдена, пометьте оба элемента как посещенные.

Временная сложность этого решения составляет O (n 2) и требует O (n) дополнительного пространства.

Эффективным решением является использование хеширования.

1) If length of given array is odd, return false. 
    An odd length array cannot be divided into pairs.
2) Traverse input array and count occurrences of 
    all reminders. 
      freq[arr[i] % k]++
3) Traverse input array again. 
   a) Find the remainder of the current element.
   b) If remainder divides k into two halves, then
      there must be even occurrences of it as it 
      forms pair with itself only.
   c) If the remainder is 0, then there must be 
      even occurrences.
   c) Else, number of occurrences of current 
      the remainder must be equal to a number of 
      occurrences of "k - current remainder".

Эффективным подходом является использование карты в C ++ STL. Карта обычно реализуется с использованием красно-черного дерева и требует O (Log n) времени для доступа. Следовательно, временная сложность нижеприведенной реализации составляет O (n Log n), но алгоритм может быть легко реализован за O (n) время с использованием хеш-таблицы.

На рисунке ниже показана пробная версия вышеуказанного подхода:

Ниже приведено описание вышеупомянутого подхода:

C ++

// Программа на C ++ для проверки, можно ли разделить arr [0..n-1]
// в парах так, что каждая пара делится на k.
#include <bits/stdc++.h>

using namespace std;

  
// Возвращает true, если arr [0..n-1] можно разделить на пары
// с суммой, кратной k.

bool canPairs(int arr[], int n, int k)

{

    // Массив нечетной длины нельзя разбить на пары

    if (n & 1)

        return false;

  

    // Создать частотный массив для подсчета вхождений

    // всех остатков при делении на k.

    map<int, int> freq;

  

    // Подсчитать вхождения всех остатков

    for (int i = 0; i < n; i++)

        freq[arr[i] % k]++;

  

    // Обход входного массива и использование freq [] для принятия решения

    // если данный массив можно разбить на пары

    for (int i = 0; i < n; i++)

    {

        // Остаток текущего элемента

        int rem = arr[i] % k;

  

        // Если остаток от текущего элемента делится

        // k на две половины.

        if  (2*rem == k)

        {

            // Тогда должны быть четные случаи

            // такой остаток

            if (freq[rem] % 2 != 0)

                return false;

        }

  

        // Если остаток равен 0, то должно быть два

        // элементы с 0 остатками

        else if (rem == 0)

        {

           if (freq[rem] & 1)           

               return false;

        }        

  

        // Остальное количество вхождений остатка

        // должно быть равно числу вхождений

        // k - остаток

        else if (freq[rem] != freq[k - rem])

            return false;

    }

    return true;

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int arr[] =  {92, 75, 65, 48, 45, 35};

    int k = 10;

    int n = sizeof(arr)/sizeof(arr[0]);

    canPairs(arr, n, k)? cout << "True": cout << "False";

    return 0;

}

Джава

   

import java.util.HashMap;

  

public class Divisiblepair 

{

    // Возвращает true, если arr [0..n-1] можно разделить на пары

    // с суммой, кратной k.

    static boolean canPairs(int ar[], int k) 

    {

        // Массив нечетной длины нельзя разбить на пары

        if (ar.length % 2 == 1)

            return false;

          

        // Создать частотный массив для подсчета вхождений

        // всех остатков при делении на k.

        HashMap<Integer, Integer> hm = new HashMap<>();

          

        // Подсчитать вхождения всех остатков

        for (int i = 0; i < ar.length; i++) 

        {

            int rem = ar[i] % k;

            if (!hm.containsKey(rem)) 

            {

                hm.put(rem, 0);

            }

            hm.put(rem, hm.get(rem) + 1);

        }

          

        // Обход входного массива и использование freq [] для принятия решения

        // если данный массив можно разбить на пары

        for (int i = 0; i < ar.length; i++) 

        {

             // Остаток текущего элемента

            int rem = ar[i] % k;

              

            // Если остаток от текущего элемента делится

            // k на две половины.

            if (2 * rem == k) 

            {

                // Тогда должны быть четные случаи

                // такой остаток

                if (hm.get(rem) % 2 == 1)

                    return false;

            

              

            // Если остаток равен 0, то должно быть два

            // элементы с 0 остатками

            else if (rem == 0

            {

                // Тогда должны быть четные случаи

                // такой остаток

                if (hm.get(rem) % 2 == 1)

                    return false;

            }

              

            // Остальное количество вхождений остатка

            // должно быть равно числу вхождений

            // k - остаток

            else 

            {

                if (hm.get(k - rem) != hm.get(rem))

                    return false;

            }

        }

        return true;

    }

  

    // Программа драйвера для проверки вышеуказанных функций

    public static void main(String[] args) 

    {

        int arr[] = { 92, 75, 65, 48, 45, 35 };

        int k = 10;

        boolean ans = canPairs(arr, k);

        if (ans)

            System.out.println("True");

        else

            System.out.println("False");

  

    }

}

  
// Этот код предоставлен Rishabh Mahrsee


Выход:

True

Временная сложность: O (n).

Эта статья предоставлена Приянкой . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Проверьте, можно ли разбить массив на пары, сумма которых делится на k

0.00 (0%) 0 votes