1018. Binary Prefix Divisible By 5

leetcode easy

#array#backtracking#bit-manipulation#csharp#easy#leetcode#prefix-sum

Task

Вам дан двоичный массив nums (индексированный 0). Мы определяем xi как число, двоичным представлением которого является подмассив nums[0..i] (от старшего бита к младшему). Например, если nums = [1,0,1], то x0 = 1, x1 = 2 и x2 = 5. Верните массив булевых чисел answer, где answer[i] истинно, если xi делится на 5.

Пример:

Input: nums = [0,1,1]

Output: [true,false,false]

C# solution

matched/original

public class Solution {
    public bool[] PrefixesDivBy5(int[] nums) {
        int x = 0;
        bool[] answer = new bool[nums.Length];
        for (int i = 0; i < nums.Length; i++) {
            x = (x * 2 + nums[i]) % 5;
            answer[i] = x == 0;
        }
        return answer;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool[] PrefixesDivBy5(vector<int>& nums) {
        int x = 0;
        bool[] answer = new bool[nums.size()];
        for (int i = 0; i < nums.size(); i++) {
            x = (x * 2 + nums[i]) % 5;
            answer[i] = x == 0;
        }
        return answer;
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public boolean[] PrefixesDivBy5(int[] nums) {
        int x = 0;
        boolean[] answer = new boolean[nums.length];
        for (int i = 0; i < nums.length; i++) {
            x = (x * 2 + nums[i]) % 5;
            answer[i] = x == 0;
        }
        return answer;
    }
}

JavaScript solution

matched/original

class Solution {
    prefixesDivBy5(nums) {
        let x = 0;
        const answer = [];
        for (const num of nums) {
            x = (x * 2 + num) % 5;
            answer.push(x === 0);
        }
        return answer;
    }
}

Python solution

matched/original

class Solution:
    def prefixesDivBy5(self, nums: List[int]) -> List[bool]:
        x = 0
        answer = []
        for num in nums:
            x = (x * 2 + num) % 5
            answer.append(x == 0)
        return answer

Go solution

matched/original

func prefixesDivBy5(nums []int) []bool {
    x := 0
    answer := make([]bool, len(nums))
    for i, num := range nums {
        x = (x * 2 + num) % 5
        answer[i] = x == 0
    }
    return answer
}

Explanation

Algorithm

Инициализация и вычисление:

Создайте переменную x для хранения текущего числа в десятичной системе.

Создайте пустой массив answer для хранения результатов делимости на 5.

Итерация по массиву:

Пройдите по всем элементам массива nums. Для каждого элемента:

Обновите значение x, учитывая текущий бит.

Проверяйте, делится ли x на 5, и добавьте результат (true или false) в массив answer.

Чтобы избежать переполнения, используйте модуль 5 для переменной x.

Возврат результата:

Верните массив answer с результатами проверки делимости на 5.

😎