JavaScript Competitive Scripting(Part 1)

The most efficient way to calculate if a number is multiple of 3 or not.

Purpose of this post :

  • Intro to Bitwise Operation.
  • 32-Bit Floating Point Manipulation.
  • JS scripting and competitive programming introduction.

Really simple problem if you look at it like a simpleton but the problem arises when it comes to efficiency.When millions of calculations occur the time complexity if reduced even by a few milliseconds can boost the system exponentially.

TRY 1:You may be tempted to just check the remainder of the given number by dividing with zero that is the easy for you to comprehend but far complex for the machine.

TRY 2:Other less obvious way to do this is to separately add each of the number and check if that number is divisible by three more efficient but still takes heavy computation.

Solution: Did you know 11=3? no? That statement is true under certain condition.

Which is when 11(2)=3(10).
11 is in binary and decimal number system.

1) Make n positive if n is negative.
2) If number is 0 then return 1
3) If number is 1 then return 0
4) Initialize: odd_count = 0, even_count = 0
5) Loop while n != 0
    a) If rightmost bit is set then increment odd count.
    b) Right-shift n by 1 bit
    c) If rightmost bit is set then increment even count.
    d) Right-shift n by 1 bit
6) return isMutlipleOf3(odd_count - even_count)


Above can be proved by taking the example of 11 in decimal numbers.
 (In this context 11 in decimal numbers is same as 3 in binary numbers)
If difference between sum of odd digits and even digits is multiple of 
11 then decimal number is multiple of 11. Let’s see how.

Let’s take the example of 2 digit numbers in decimal
AB = 11A -A + B = 11A + (B – A)
So if (B – A) is a multiple of 11 then is AB.

Let us take 3 digit numbers.

ABC = 99A + A + 11B – B + C = (99A + 11B) + (A + C – B)
So if (A + C – B) is a multiple of 11 then is (A+C-B)

Let us take 4 digit numbers now.
ABCD = 1001A + D + 11C – C + 999B + B – A
= (1001A – 999B + 11C) + (D + B – A -C )
So, if (B + D – A – C) is a multiple of 11 then is ABCD.

This can be continued for all decimal numbers.

Above concept can be proved for 3 in binary numbers in the same way.

function ismul3(num) {
    if (num === 0)
        return 1;
    if (num === 1)
        return 0;
//Make the number(num) positive
    var counto = 0,
        counte = 0;
    while (num) {
//checks if the odd bit is 1 and increment odd counter
        if (num & 1)
        num = num >> 1;
//checks if the even bit is 1 and increment even counter
        if (num & 1)
        num = num >> 1;
    return ismul3(Math.abs(counto - counte));

var a = ismul3(45239453763899579837098437984379843054);
if (a)
    console.log("Not a Multiple");


Try the program here:

JS Bin on

credits to for algorithm.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s