Skip to main content

Is Binary Number Multiple Of 3

In this page, we will solve the problem of finding whether given binary number is divisible by 3 or not.

Problem Description​

Given a number in its binary form find if the given binary number is a multiple of 3. It is recommended to finish the task using one traversal of input binary number.

Examples​

Example 1:

Input: S = "0011"
Output: 1
Explanation: "0011" is 3, which is divisible by 3.

Example 2:

Input: S = "100"
Output: 0
Explanation: "100"'s decimal equivalent is 4, which is not divisible by 3.

Constraints​

  • 1≤1 \leq |S| ≤105\leq10^5

Solution​

Intuition and Approach​

The problem can be solved using two approaches one by converting the given binary string to decimal number and then find whether the given number is divisible by three or not and another approach is by using Bit manipulation

Approach: Binary to Decimal​

  1. The simplest approach is to convert the binary number into a decimal equivalent. And check if it is divisible by 3 or not.
  2. For converting the binary string to decimal we will traverse the given string backwards and then
    • if '1' we will add the power of 2 to the res
    • if '0' we will do nothing
  3. After traversing whole list we will check whether the decimal number res is divisible by 3 or not

Code in Python​

class Solution:
def isDivisible(self, s):
ans=0
for i in range(len(s)-1,-1,-1):
if s[i]=='1':
ans+=2**(len(s)-1-i)
return int(ans%3==0)

Complexity Analysis​

  • Time Complexity: O(S)O(S)
  • Space Complexity: O(1)O(1)