3190.Find Minimum Operations to Make All Elements Divisible by Three

Ссылка на задачу: https://leetcode.com/problems/find-minimum-operations-to-make-all-elements-divisible-by-three/description/

Описание

Дан целочисленный массив nums. За одну операцию можно добавить или вычесть единицу из любого элемента nums. Верните минимальное количество операций, которые нужно совершить для того, чтобы сделать все элементы nums кратными 3.

Примеры

Пример 1

Input:

Output: 3

Объяснение:

• вычесть единицы из 1 (элемент с индексом 0)

• добавить единицу к 2 (элемент с индексом 1)

• вычесть единицу из 4 (самый последний элемент)

Пример 2

Input:

Output: 0

Ограничения

• 1 <= nums.length <= 50

• 1 <= nums[i] <= 50

Решение

Давайте возьмем любое число наугад. Например, 46. Оно не кратно 3, но ближайшее число, кратное 3, - это 45. Оно на 1 меньше 46. Возьмем еще одно, например 20. Тут, опять-таки, ближайшее кратное 3 число (21) тоже отличается от взятого всего на 1. Напоследок, возьмем -15574. Это число тоже не кратно 3, но блжайшее кратное 3 для него - это -15573 (снова отличается от взятого на 1). То есть минимальное количество операций, нужных для того, чтобы сделать элемент кратным 3, равняется 1.

Так, достаточно перебрать все элементы nums и, если текущий элемент не кратен 3, то к искомому количеству минимальных операций достаточно прибавить 1.

Алгоритм:

1. Перебрать каждый элемент nums

2. Проверить, кратен ли 3 текущий элемент; если не кратен, то к ответу ans прибавить 1

Код:

python

class Solution:
    def minimumOperations(self, nums: List[int]) -> int:
        ans = 0
        for i in range(len(nums)):
            if nums[i] % 3 != 0:
                ans += 1
        return ans

C++

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            if (nums[i] % 3 != 0) {
                ++ans;
            }
        }
        return ans;
    }
};

Сложность алгоритма по времени - O(N)

Решение сводится к перебору всех элементов массива nums размером N.

Сложность алгоритма по памяти - O(1)

Для решения не требуется никаких дополнительных объектов.