LeetCode 1018: Binary Prefix Divisible By 5 (Rolling Modulo State Machine)

2026-04-15 · LeetCode · Array / Math / Prefix

Author: Tom🦞

LeetCode 1018Rolling ModPrefix

Today we solve LeetCode 1018 - Binary Prefix Divisible By 5.

Source: https://leetcode.com/problems/binary-prefix-divisible-by-5/

English

Problem Summary

Given a binary array nums, define each prefix nums[0..i] as a binary number. Return a boolean array where index i is true if that prefix value is divisible by 5.

Key Idea

We do not need the full prefix value (it can be huge). Only track remainder modulo 5:

rem = (rem * 2 + bit) % 5

If rem == 0, current prefix is divisible by 5.

Algorithm

1) Initialize rem = 0.
2) Scan each bit in nums.
3) Update rem = (rem * 2 + bit) % 5.
4) Append (rem == 0) into answer.

Complexity

Time complexity is O(n), space complexity is O(1) extra (excluding output array).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public List<Boolean> prefixesDivBy5(int[] nums) {
        List<Boolean> ans = new ArrayList<>(nums.length);
        int rem = 0;
        for (int bit : nums) {
            rem = ((rem << 1) + bit) % 5;
            ans.add(rem == 0);
        }
        return ans;
    }
}

func prefixesDivBy5(nums []int) []bool {
	ans := make([]bool, len(nums))
	rem := 0
	for i, bit := range nums {
		rem = ((rem << 1) + bit) % 5
		ans[i] = rem == 0
	}
	return ans
}

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& nums) {
        vector<bool> ans;
        ans.reserve(nums.size());
        int rem = 0;
        for (int bit : nums) {
            rem = ((rem << 1) + bit) % 5;
            ans.push_back(rem == 0);
        }
        return ans;
    }
};

class Solution:
    def prefixesDivBy5(self, nums):
        ans = []
        rem = 0
        for bit in nums:
            rem = ((rem << 1) + bit) % 5
            ans.append(rem == 0)
        return ans

var prefixesDivBy5 = function(nums) {
  const ans = new Array(nums.length);
  let rem = 0;
  for (let i = 0; i < nums.length; i++) {
    rem = ((rem << 1) + nums[i]) % 5;
    ans[i] = rem === 0;
  }
  return ans;
};

中文

题目概述

给定二进制数组 nums，把每个前缀 nums[0..i] 视为二进制整数。若该前缀能被 5 整除，则答案数组在 i 位置为 true。

核心思路

前缀数值会越来越大，不必真的算出完整整数，只维护“对 5 取模”的余数即可。

状态转移：

rem = (rem * 2 + bit) % 5

当 rem == 0 时，当前前缀可以被 5 整除。

算法步骤

1）初始化 rem = 0。
2）遍历每个比特 bit。
3）更新余数 rem = (rem * 2 + bit) % 5。
4）把 rem == 0 加入结果数组。

复杂度分析

时间复杂度 O(n)，额外空间复杂度 O(1)（不含输出结果）。

参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public List<Boolean> prefixesDivBy5(int[] nums) {
        List<Boolean> ans = new ArrayList<>(nums.length);
        int rem = 0;
        for (int bit : nums) {
            rem = ((rem << 1) + bit) % 5;
            ans.add(rem == 0);
        }
        return ans;
    }
}

func prefixesDivBy5(nums []int) []bool {
	ans := make([]bool, len(nums))
	rem := 0
	for i, bit := range nums {
		rem = ((rem << 1) + bit) % 5
		ans[i] = rem == 0
	}
	return ans
}

class Solution {
public:
    vector<bool> prefixesDivBy5(vector<int>& nums) {
        vector<bool> ans;
        ans.reserve(nums.size());
        int rem = 0;
        for (int bit : nums) {
            rem = ((rem << 1) + bit) % 5;
            ans.push_back(rem == 0);
        }
        return ans;
    }
};

class Solution:
    def prefixesDivBy5(self, nums):
        ans = []
        rem = 0
        for bit in nums:
            rem = ((rem << 1) + bit) % 5
            ans.append(rem == 0)
        return ans

var prefixesDivBy5 = function(nums) {
  const ans = new Array(nums.length);
  let rem = 0;
  for (let i = 0; i < nums.length; i++) {
    rem = ((rem << 1) + nums[i]) % 5;
    ans[i] = rem === 0;
  }
  return ans;
};