# 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 = 3

**Output:** 3

**Explanation:** 10/3 = truncate(3.33333..) = 3.

**Example 2:**

**Input:** dividend = 7, divisor = -3

**Output:** -2

**Explanation:** 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 = 0

**Output:** 0

**Example 2:**

**Input:** n = 3

**Output:** 2

**Explanation:** 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 = 6

**Output:** 4

**Explanation:** 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 = 9

**Output:** 14

**Example 5:**

**Input:** n = 333

**Output:** 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 = 10

**Output:** 1024.00000

**Example 2:**

**Input:** x = 2.10000, n = 3

**Output:** 9.26100

**Example 3:**

**Input:** x = 2.00000, n = -2

**Output:** 0.25000

**Explanation:** 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 = 3

**Output:** 0

**Explanation:** 3! = 6, no trailing zero.

**Example 2:**

**Input:** n = 5

**Output:** 1

**Explanation:** 5! = 120, one trailing zero.

**Example 3:**

**Input:** n = 0

**Output:** 0

## Leet Code Solution from Discussion

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 = 123

**Output:** "One Hundred Twenty Three"

**Example 2:**

**Input:** num = 12345

**Output:** "Twelve Thousand Three Hundred Forty Five"

**Example 3:**

**Input:** num = 1234567

**Output:** "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

**Example 4:**

**Input:** num = 1234567891

**Output:** "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** **Value**

I 1

V 5

X 10

L 50

C 100

D 500

M 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 = 3

**Output:** "III"

**Example 2:**

**Input:** num = 4

**Output:** "IV"

**Example 3:**

**Input:** num = 9

**Output:** "IX"

**Example 4:**

**Input:** num = 58

**Output:** "LVIII"

**Explanation:** L = 50, V = 5, III = 3.

**Example 5:**

**Input:** num = 1994

**Output:** "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 = 2

**Output:** "0.5"

**Example 2:**

**Input:** numerator = 2, denominator = 1

**Output:** "2"

**Example 3:**

**Input:** numerator = 2, denominator = 3

**Output:** "0.(6)"

**Example 4:**

**Input:** numerator = 4, denominator = 333

**Output:** "0.(012)"

**Example 5:**

**Input:** numerator = 1, denominator = 5

**Output:** "0.2"