title: Divisibility by 3
body: <p>I was reading an article on <a href="http://www.geeksforgeeks.org/write-an-efficient-method-to-check-if-a-number-is-multiple-of-3/" rel="nofollow">Writing an Efficient Method to Check if a Number is Multiple of 3</a>.</p>
  
  <p>The method explained here is to take the difference between <code>oddsum</code> and <code>evensum</code> of the number in binary representation. If the difference is divisible by 3 so is the number. I understood why we are doing this, but I am not able to understand why the time complexity is O(log n).</p>