Подсчитайте пары в массиве, сумма элементов которых равна сумме их соответствующих цифр.
Дан массив 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): The difference between 1+ sumOfDigits(1) and 1+sumOfDigits(1) is 0, thus they are equal.
- (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:
- (105, 96): The difference between 105+ sumOfDigits(105) and 96+sumOfDigits(96) is 0, thus they are equal.
- (105, 96): The difference between 105+ sumOfDigits(105) and 96+sumOfDigits(96) is 0, thus they are equal.
- (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)