Найдите количество пар братьев Смит в заданном массиве

Учитывая массив A[] размера N , задача состоит в том, чтобы подсчитать пары Smith Brothers в массиве.

Two numbers X and Y are said to be Smith Brothers Pairs if they are both Smith Numbers and consecutive.  

Примечание. Число Смита — это составное число, сумма цифр которого равна сумме цифр его простой факторизации.

Примеры :

Input: A = {728, 729, 28, 2964, 2965}, N=5  
Output: 2  
Explanation:The pairs are (728, 729) and (2964, 2965) are Smith Brothers Pairs as they are Smith numbers as well as consecutive.  

Input: A = {12345, 6789}, N=5  
Output: 0  

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

1. Инициализируйте переменную count значением 0 , в котором хранится количество пар братьев Смит в массиве.
2. Пройдите массив A от 0 до N-1 . Для каждого текущего индекса i выполните следующие действия:
   1. Пройдите A от i+1 до N-1 . Для каждого текущего индекса j выполните следующие действия:
      1. Проверьте, являются ли A[i] и A[j] числами Смита.
      2. Если это числа кузнеца и их разница равна 1, увеличивается счет.
3. Наконец, количество возвратов

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

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

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

1. Инициализируйте переменную count значением 0 .
2. Сортировать массив, A .
3. Пройдите A от 0 до N-2 и для каждого текущего индекса i сделайте следующее:
   1. Проверьте, являются ли A[i] и A[i+1] числами Смита.
   2. Если оба они являются числами Смита, увеличьте count .
4. Наконец, верните count .

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

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

Ссылка: https://mathworld.wolfram.com/SmithBrothers.html