Количество цифр, которые нужно удалить, чтобы число делилось на 25
Для заданного числа N необходимо найти минимальное количество цифр, которое нужно удалить из числа, чтобы число стало делиться на 25.
Input: N = 71345
Output: 3
Explanation: After removing 1, 3 and 5, the number becomes 75 and it is divisible by 25.Input: N = 32505
Output: 1
Explanation: After removing 5 from last, number becomes 3250 and it is divisible by 25.
Подход: число делится на 25, если его последние две цифры равны «00» или число, образованное его последними двумя цифрами, делится на 25, как описано в разделе «Проверка, делится ли большое число на 25 или нет». Теперь в этой задаче проверьте это условие для всех возможных пар в N и найдите минимальное количество цифр, которые нужно удалить. Если найдется какая-либо пара элементов, удовлетворяющая вышеуказанному условию, то можно составить число, используя эти два элемента в качестве последних цифр, и тогда оно будет кратно 25.
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N 2 )
Вспомогательное пространство: O(1)