Найдите число такое, что сумма N с ним является палиндромом

Для заданного очень большого числа N [1 ≤ длина цифры числа N (n) ≤ 10 ⁶ ] задача состоит в том, чтобы найти некоторое натуральное число той же длины, что и N, без начальных нулей, такое, что сумма этих двух чисел равна палиндром.

Примеры :

Input: N = 54321
Output: 45678
Explanation: 54321 + 45678 = 99999 which is a palindrome.

Input: N = 999
Output: 112

Подход : Чтобы решить проблему, следуйте следующей идее:

If the number does not start with 9, then make the palindrome of  9999…… of length of N and if the number starts with 9 then make the palindrome 1111….. of length of (n + 1).

• So, the resultant number if it does not starts with 9 is (9999….. to n – N). 
• And, the resultant number if it starts with 9 is (11111….. to n+1 – N). 

Выполните следующие шаги, чтобы решить проблему:

• Найдите количество цифр в числе N.
• Если N начинается с 9:
  • Тогда считайте, что сумма равна [ 1111…to (n+1) ].
  • Затем вычислите число, как указано выше.
• Если N не начинается с 9:
  • Тогда считайте, что сумма равна [ 999…to n ].
  • Получите номер, следуя описанному выше процессу.

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

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