# 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`)

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.

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

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

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

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

Full Stack SE. I love to build beautiful web apps and learn new technologies.

## More from Huy Do

Full Stack SE. I love to build beautiful web apps and learn new technologies.