1018. Binary Prefix Divisible By 5

You are given a binary array nums (0-indexed).

We define $x_i$ as the number whose binary representation is the subarray nums[0…i] (from most-significant-bit to least-significant-bit).

• For example, if nums = [1,0,1], then $x_0=1,x_1=2,and{x}_2=5$.

Return an array of booleans answer where answer[i] is true if $x_i$ is divisible by 5.
 

Example 1:

Input: nums = [0,1,1]
Output: [true,false,false]
Explantion: The input numbers in binary are 0, 01, 011; which are 0, 1, and 3 in base-10.
Only the first number is divisible by 5, so answer[0] is true.

Example 2:

Input: nums = [1,1,1]
Output: [false,false,false]

Constraints:

• $1<=nums.length<=10^5$
• nums[i] is either 0 or 1.

From: LeetCode
Link: 1018. Binary Prefix Divisible By 5

Solution:

Ideas:

• Let the current prefix value be x.

• When a new bit b is appended, the new value becomes x * 2 + b.

• We only care whether it is divisible by 5, so keep x % 5 instead of the full number.

• Update with rem = (rem * 2 + nums[i]) % 5.

• If rem == 0, that prefix is divisible by 5.

Code:

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
bool* prefixesDivBy5(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    bool* ans = (bool*)malloc(sizeof(bool) * numsSize);
    
    int rem = 0;  // current prefix value modulo 5
    
    for (int i = 0; i < numsSize; i++) {
        rem = (rem * 2 + nums[i]) % 5;
        ans[i] = (rem == 0);
    }
    
    return ans;
}