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

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

Divide the numbers into segments of 3 digits

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"

The End :)