# 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: 00012: 00104: 01008: 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

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

--

--