# Check Divisibility By 3

#### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. You are given a binary string which represents a number.2. You have to check whether this number is divisible by 3 or not.3. Print 'true' if it is divisible by 3, otherwise print 'false'.`
Input Format
`A binary string`
Output Format
`true or false`
Question Video
Constraints
`1 <= length of binary string <= 10000`
Sample Input
`10010101010001`
Sample Output
`false`

• Editorial

In this problem, we need to check whether the given input binary representation is divisible by 3(decimal) or not using bit manipulation.

As we are provided with a binary representation so if that representation would be divisible by 0b11 (binary representation of 3) then that number would be divisible by 3.

The result obtained is that if the sum of bits at even position subtracted by the sum of bits at odd position is divisible by 11 then the entire number is divisible by 3.

Say we have the given string as abcdef

105a + 104b + 103c + 102d  + 101e + 100f

100001a - a + 9999b + b + 1001c - c + 99d + d - 11e - e + f

100001a + 9999b + 1001c + 99d +11e - ((a + c + e) - (b + d + f))

11(9091a + 909b + 91c + 9d + e) - ((a + c + e) - (b + d + f))

So if ((a + c + e) - (b + d + f)) is a multiple of 11 then the entire expression will be divisible by 11.

As we know that 11 is the binary representation of 3 so if a binary number gets divisible by 11 then it is divisible by 3(decimal).

Henceforth in this problem we need to check whether ((a + c + e) - (b + d + f)) % 3 == 0 or not, if true then the string abcdef is divisible by 3.

Time Complexity: O(n)

The time complexity for the function is linear as we are traversing on every character of the input binary string.

Space Complexity: O(1)

The space complexity for the function is constant.

• Related Topics

Run

Run
Id Name