Проверить, делится ли сумма цифр в левой половине на сумму цифр в правой половине в наибольшей перестановке N

Учитывая положительное целое число N , задача состоит в том, чтобы максимизировать целое число N , переставляя цифры и проверяя, делится ли сумма левых половин цифр на сумму правых половин цифр или нет. Если найдено верно, то выведите «Да» . В противном случае выведите «Нет» .

If the number of digits(say D) in the given number N is odd, then consider any of the two possibilities:

• Consider the first (D/2) digit in the left half.
• Consider the first (D/2 + 1) digit in the left half.

Примеры:

Input: N = 43729
Output: Yes
Explanation:
Maximum value of N possible by rearranging the digits is 97432.
Case 1: 
Sum of digits in the left half = 9 + 7 = 16. 
Sum of digits in the right half = 4 + 3 + 2 = 9. 
Since, 16 is not divisible by 9, the condition is not satisfied.
Case 2: 
Sum of digits in the left half = 9 + 7 + 4 = 20. 
Sum of digits in the right half = 3 + 2 = 5. 
Since, 20 is divisible by 5, the condition is satisfied.

Input: N = 3746
Output: No

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

• Инициализируйте переменную, скажем, D , которая хранит количество цифр данного числа N.
• Сохраните заданное число как строку в переменной, скажем, temp .
• Отсортируйте строку temp в порядке убывания.
• Теперь проверьте, делится ли сумма первых (D/2) цифр на сумму последних (D/2) цифр, затем выведите «Да» . В противном случае выведите «Нет» .

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

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