# Bits Manipulations

Ok, not really bits…but questions relating to number operations.

# Leet Code 29 Divide Two Integers

Given two integers `dividend` and `divisor`, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing `dividend` by `divisor`.

The integer division should truncate toward zero, which means losing its fractional part. For example, `truncate(8.345) = 8` and `truncate(-2.7335) = -2`.

Example 1:

`Input: dividend = 10, divisor = 3Output: 3Explanation: 10/3 = truncate(3.33333..) = 3.`

Example 2:

`Input: dividend = 7, divisor = -3Output: -2Explanation: 7/-3 = truncate(-2.33333..) = -2.`

Note:

• Both dividend and divisor will be 32-bit signed integers.
• The divisor will never be 0.
• Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

This problem seemed easy at first glance. Just do subtraction of divisor from dividend. But later on, you will see that the problem arises when the divisor or dividend is a negative value.

Tutorial Video:

## 1611. Minimum One Bit Operations to Make Integers Zero (Hard)

Given an integer `n`, you must transform it into `0` using the following operations any number of times:

• Change the rightmost (`0th`) bit in the binary representation of `n`.
• Change the `ith` bit in the binary representation of `n` if the `(i-1)th` bit is set to `1` and the `(i-2)th` through `0th` bits are set to `0`.

Return the minimum number of operations to transform `n` into `0`.

Example 1:

`Input: n = 0Output: 0`

Example 2:

`Input: n = 3Output: 2Explanation: The binary representation of 3 is "11"."11" -> "01" with the 2nd operation since the 0th bit is 1."01" -> "00" with the 1st operation.`

Example 3:

`Input: n = 6Output: 4Explanation: The binary representation of 6 is "110"."110" -> "010" with the 2nd operation since the 1st bit is 1 and 0th through 0th bits are 0."010" -> "011" with the 1st operation."011" -> "001" with the 2nd operation since the 0th bit is 1."001" -> "000" with the 1st operation.`

Example 4:

`Input: n = 9Output: 14`

Example 5:

`Input: n = 333Output: 393`

1 bit
1
0

2 bits
10
11
01 (1 bit case)
00

3 bits
100
101
110
010 (2 bits case)
011
001
000

4 bits
1000
1001
1011
1111
1101
1100
0100 (3 bits case)

`TODO`

## 50. Pow(x, n)

Implement pow(x, n), which calculates x raised to the power n (i.e. xn).

Example 1:

`Input: x = 2.00000, n = 10Output: 1024.00000`

Example 2:

`Input: x = 2.10000, n = 3Output: 9.26100`

Example 3:

`Input: x = 2.00000, n = -2Output: 0.25000Explanation: 2-2 = 1/22 = 1/4 = 0.25`

Copied from Leet Code solution:

The key is recognising line 22.

Instead of doing X * RESULTS (previously calculated products) for N times, we break up N into N/2 and do X*X for N/2 times. So it is faster.

# 172. Factorial Trailing Zeroes

Given an integer `n`, return the number of trailing zeroes in `n!`.

Follow up: Could you write a solution that works in logarithmic time complexity?

Example 1:

`Input: n = 3Output: 0Explanation: 3! = 6, no trailing zero.`

Example 2:

`Input: n = 5Output: 1Explanation: 5! = 120, one trailing zero.`

Example 3:

`Input: n = 0Output: 0`

## Leet Code Solution from Discussion

https://leetcode.com/problems/factorial-trailing-zeroes/discuss/355808/JavaScript-solution-with-explanation

First, let’s think about in what situation will we get a trailing zero. We get a trailing zero whenever we multiply a non zero number by 10.

Example: 1 * 10 = 10

Since 10 is made up of multiplying 2 by 5, another way to get a trailing zero is to multiply a non zero number by 2 and 5.

Example: 1 * 2 * 5 = 10

So, to count the number of trailing zeroes we just need to figure out how many times we multiply 2 by 5.

Example:
1 * (2 * 5) = 10 // one trailing zero
1 * (2 * 5) * (2 * 5) = 100 // two trailing zeroes

Now let’s look at factorial.

The factorial of 5 is:
1 * 2 * 3 * 4 * 5 = 120
Since we have multiplied 2 and 5 once, there is one trailing zero.

The factorial of 10 is:
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 10 = 3628800
Another way to write this is:
1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9 * 2 * 5 = 3628800
As you can see, we have multiplied 2 and 5 twice, so there are two trailing zeroes.

Instead of keeping track of the number of 2s and 5s, we really just need to keep track of the number of 5s. This is because in any factorial calculation there are always going to be more multiples of 2 than 5.

Example: From the numbers 1 to 10, there are five multiples of 2 but only two multiples of 5.

Question: How many 5s are there in the factorial of 25?
You may guess the answer is 25 / 5 = 5, however there are actually 6.

Here are all the multiples of 5 in the factorial of 25:
5, 10, 15, 20, 25
Another way to write this is:
(5 * 1), (5 * 2), (5 * 3), (5 * 4), (5 * 5)
As you can see, 5 is actually multiplied 6 times.

We can simplify the answer to the Factorial Trailing Zeroes question to the following:
(n / 5) + (n / 5²) + (n / 5³)… (n / 5^x)
We continue until 5^x is greater than n.

# Leet Code 273. Integer to English Words

Convert a non-negative integer `num` to its English words representation.

Example 1:

`Input: num = 123Output: "One Hundred Twenty Three"`

Example 2:

`Input: num = 12345Output: "Twelve Thousand Three Hundred Forty Five"`

Example 3:

`Input: num = 1234567Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"`

Example 4:

`Input: num = 1234567891Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"`

Leet Code Solution from Discussion

# Leet Code 12. Integer to Roman

Roman numerals are represented by seven different symbols: `I`, `V`, `X`, `L`, `C`, `D` and `M`.

`Symbol       ValueI             1V             5X             10L             50C             100D             500M             1000`

For example, `2` is written as `II` in Roman numeral, just two one's added together. `12` is written as `XII`, which is simply `X + II`. The number `27` is written as `XXVII`, which is `XX + V + II`.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not `IIII`. Instead, the number four is written as `IV`. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as `IX`. There are six instances where subtraction is used:

• `I` can be placed before `V` (5) and `X` (10) to make 4 and 9.
• `X` can be placed before `L` (50) and `C` (100) to make 40 and 90.
• `C` can be placed before `D` (500) and `M` (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral.

Example 1:

`Input: num = 3Output: "III"`

Example 2:

`Input: num = 4Output: "IV"`

Example 3:

`Input: num = 9Output: "IX"`

Example 4:

`Input: num = 58Output: "LVIII"Explanation: L = 50, V = 5, III = 3.`

Example 5:

`Input: num = 1994Output: "MCMXCIV"Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.`

Constraints:

• `1 <= num <= 3999`

## 166. Fraction to Recurring Decimal

Given two integers representing the `numerator` and `denominator` of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than `104` for all the given inputs.

Example 1:

`Input: numerator = 1, denominator = 2Output: "0.5"`

Example 2:

`Input: numerator = 2, denominator = 1Output: "2"`

Example 3:

`Input: numerator = 2, denominator = 3Output: "0.(6)"`

Example 4:

`Input: numerator = 4, denominator = 333Output: "0.(012)"`

Example 5:

`Input: numerator = 1, denominator = 5Output: "0.2"`

--

--

--

## More from LiveRunGrow

This is a repository of my thoughts on my personal life, my random interests & notes taken down as I navigate my way through the tech world!

Love podcasts or audiobooks? Learn on the go with our new app.

## Build Crud App with Laravel and Vue.js ## Optimize Twilio IVR for Multi market contact centre ## Automated Testing with Cypress ## A JavaScript error occurred in the main process. (how to solve this) ## Cross Platform Mobile Development with Expo React Native ## Playing around with React Navigation   ## LiveRunGrow

This is a repository of my thoughts on my personal life, my random interests & notes taken down as I navigate my way through the tech world!

## What you should know about Cronos. ## Let Freedom Ring ## 1.3 The Ego Matrix 