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.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name