Подсчитайте пары в массиве, сумма элементов которых равна сумме их соответствующих цифр.

Опубликовано: 21 Сентября, 2022

Дан массив arr[] , состоящий из N положительных целых чисел, задача состоит в том, чтобы подсчитать количество пар в массиве, скажем (a, b), таких, что сумма a с его суммой цифр равна сумме b с его суммой цифр.

Примеры:

Input: arr[] = {1, 1, 2, 2}
Output: 2
Explanation:
Following are the pairs that satisfy the given criteria:

  1. (1, 1): The difference between 1+ sumOfDigits(1) and 1+sumOfDigits(1) is 0, thus they are equal.
  2. (2, 2): The difference between 2+sumOfDigits(2) and 2+sumOfDigits(2) is 0 , thus they are equal.

Therefore, the total number of pairs are 2.

Input: arr[] = {105, 96, 20, 2, 87, 96}
Output: 3
Following are the pairs that satisfy the given criteria:

  1. (105, 96): The difference between 105+ sumOfDigits(105) and 96+sumOfDigits(96) is 0, thus they are equal.
  2. (105, 96): The difference between 105+ sumOfDigits(105) and 96+sumOfDigits(96) is 0, thus they are equal.
  3. (96, 96): The difference between 96+ sumOfDigits(96) and 96+sumOfDigits(96) is 0, thus they are equal.

Input: arr[] = {1, 2, 3, 4}
Output: 0

Наивный подход: самый простой подход к решению проблемы — сгенерировать все возможные пары заданного массива и подсчитать те пары, которые удовлетворяют заданным критериям. После проверки всех пар выведите общее количество полученных пар.

Временная сложность: O(N 2 )
Вспомогательное пространство: O(1)

Эффективный подход. Описанный выше подход также можно оптимизировать, сохраняя сумму элементов с их суммой цифр в HashMap, а затем подсчитывая общее количество сформированных пар соответствующим образом. Следуйте инструкциям ниже, чтобы решить проблему:

  • Инициализируйте unordered_map, M , который хранит частоту суммы элементов с его суммой цифр для каждого элемента массива.
  • Пройдите по заданному массиву и увеличьте частоту (arr[i] + sumOfDigits(arr[i])) на карте M .
  • Инициализируйте переменную, скажем, count как 0 , которая хранит общее количество результирующих пар.
  • Пройдите по заданной карте M и, если частота любого элемента, скажем, F больше или равна 2 , затем увеличьте значение count на (F*(F – 1))/2 .
  • После выполнения вышеуказанных шагов выведите значение count как результирующее количество пар.

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

Временная сложность: O(N)
Вспомогательное пространство: O(N)

РЕКОМЕНДУЕМЫЕ СТАТЬИ