Math part 3

Is a power of two

Given a positive integer, write a function to find if it is a power of two or not.

Naive solution

In the naive solution, we just keep dividing the number by two unless the number becomes 1 and every time we do so, we check that remainder after division is always 0. Otherwise, the number can't be a power of two.

Bitwise solution

Powers of two in binary form always have just one bit set. The only exception is with a signed integer (e.g. an 8-bit signed integer with a value of -128 looks like: 10000000)

1: 0001
2: 0010
4: 0100
8: 1000

So after checking that the number is greater than zero, we can use a bitwise hack to test that one and only one bit is set.

number & (number - 1)

For example for the number 8 that operation will look like:

1000
- 0001
  ----
  0111
  1000
& 0111
  ----
  0000
/** 
* @param {number} number 
* @return {boolean} 
*/
export default function isPowerOfTwo(number) 
{  // 1 (2^0) is the smallest power of two.  
  if (number < 1) {    return false;  }   
  // Let's find out if we can divide the number by two  
  // many times without remainder.  
  
  let dividedNumber = number;  
  while (dividedNumber !== 1) {    
    if (dividedNumber % 2 !== 0) {      
    // For every case when remainder isn't zero we can say 
    // that this number      
    // couldn't be a result of power of two.      
      return false;    
    }     
    dividedNumber /= 2;  
  }   
  return true;
}

Pascal’s Triangle

In mathematics, Pascal’s triangle is a triangular array of the binomial coefficients.

The rows of Pascal’s triangle are conventionally enumerated starting with row n = 0 at the top (the 0th row). The entries in each row are numbered from the left beginning with k = 0 and are usually staggered relative to the numbers in the adjacent rows. The triangle may be constructed in the following manner: In row 0 (the topmost row), there is a unique nonzero entry 1. Each entry of each subsequent row is constructed by adding the number above and to the left with the number above and to the right, treating blank entries as 0. For example, the initial number in the first (or any other) row is 1 (the sum of 0 and 1), whereas the numbers 1 and 3 in the third row are added to produce the number 4 in the fourth row.

Formula

The entry in the nth row and kth column of Pascal's triangle is denoted

. For example, the unique nonzero entry in the topmost row is

With this notation, the construction of the previous paragraph may be written as follows:

for any non-negative integer n and any integer k between 0 and n, inclusive.

Calculating triangle entries in O(n) time

We know that i-th entry in a line number lineNumber is Binomial Coefficient C(lineNumber, i) and all lines start with value 1. The idea is to calculate C(lineNumber, i) using C(lineNumber, i-1). It can be calculated in O(1) time using the following:

C(lineNumber, i)   = lineNumber! / ((lineNumber - i)! * i!)
C(lineNumber, i - 1) = lineNumber! / ((lineNumber - i + 1)! * (i - 1)!)

We can derive the following expression from the above two expressions:

C(lineNumber, i) = C(lineNumber, i - 1) * (lineNumber - i + 1) / i

So C(lineNumber, i) can be calculated from C(lineNumber, i - 1) in O(1) time.

References:

Math

Math part 2

trekhleb/javascript-algorithms

https://github.com/trekhleb/javascript-algorithms/tree/master/src/algorithms/math/pascal-triangle