Check Divisibility By 3
Try First, Check Solution later1. 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.Input Format
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'.
A binary stringOutput Format
true or falseQuestion Video Constraints
1 <= length of binary string <= 10000Sample Input
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