Проверьте, можно ли сделать элементы массива равными, добавив цифру единицы к числу

Опубликовано: 26 Февраля, 2023

Учитывая массив arr[] из N целых чисел, задача состоит в том, чтобы проверить, возможно ли сделать все элементы массива идентичными, применяя следующую опцию любое количество раз:

  • Выберите любое число и добавьте к нему цифру единицы.

Примеры :

Input: arr[] = {1, 2, 4, 8, 24}
Output: Possible
Explanation: 
For 1: 1 -> 2 -> 4 -> 8 -> 16- > 22 -> 24
For 2: 2 -> 4 -> 8 -> 16 -> 22 -> 24
For 4: 4 -> 8 -> 16 -> 22 -> 24
For 8: 16- > 22 -> 24
For 24: 24 (it’s already 24, so, no need to change)

Input: arr[] = {5, 10}
Output: Possible

Подход : Задача может быть решена на основе следующего наблюдения.

Any number can be converted to have either 0 or 2 as its unit digit by repetitively adding its unit digit to itself at most 10 times. 

The idea is to 

  • Initially make the unit digit of every number either 2 or 0.
  • Then for the numbers that have 0 as their unit digit, all of those numbers must be same(because x+0 = 0), and 
  • For every number with 2 as the unit digit, the difference between them must be multiple of 20 so that they can be made equal.

Следуйте инструкциям, чтобы решить эту проблему:

  • Добавляйте цифру единиц каждого числа к самой себе, пока ее цифра единиц не станет 2 или 0.
  • Для каждого числа, которое имеет 0 в качестве единичной цифры, проверьте, все ли числа равны.
  • Для чисел с 2 в качестве единицы измерения разница между ними должна быть кратна 20.

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

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

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