You are given a binary array nums (0-indexed).
We define xi as the number whose binary representation is the subarray nums[0..i] (from most-significant-bit to least-significant-bit).
nums = [1,0,1], then x0 = 1, x1 = 2, and x2 = 5.Return an array of booleans answer where answer[i] is true if xi is divisible by 5.
Example 1:
Input: nums = [0,1,1] Output: [true,false,false] Explanation: 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 <= 105nums[i] is either 0 or 1.This approach involves constructing the number iteratively while evaluating the divisibility by 5. By maintaining the current number modulo 5, we can check divisibility efficiently without overflowing the integer limits.
The solution iteratively constructs the binary number by shifting the current number left by one (multiplying by 2) and adding the new bit. It keeps track of the number modulo 5 to ensure we deal only with small numbers, thereby checking for divisibility by 5 efficiently.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the length of the input array.
Space Complexity: O(n) for the storage of the answer array.
This alternative approach attempts to leverage bitwise operations to handle binary numbers more explicitly. While this is an interesting take, keep in mind the modulo method employed earlier is quite optimized already.
In this C solution, we use bitwise left shift to double the current number before adding the new bit, effectively building the binary number. The modulo operation is consistent to manage potential overflow.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(n) for the storage of the results array.
| Approach | Complexity |
|---|---|
| Iterative Binary Construction | Time Complexity: O(n) where n is the length of the input array. |
| Using Bitwise Operations | Time Complexity: O(n). |
LeetCode was HARD until I Learned these 15 Patterns • Ashish Pratap Singh • 1,002,144 views views
Watch 9 more video solutions →Practice Binary Prefix Divisible By 5 with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor