# 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:

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