Press "Enter" to skip to content

Posts tagged as “math”

花花酱 LeetCode 66. Plus One

By zxi on April 10, 2019

Given a non-empty array of digits representing a non-negative integer, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit.

You may assume the integer does not contain any leading zero, except the number 0 itself.

Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

Solution: Big Integer

Process from right to left (lest significant to most signification). Use carry to indicate whether need +1 for next digit or not.

Time complexity: O(n)
Space complexity: O(n)

c++

花花酱 LeetCode 1006. Clumsy Factorial

By zxi on March 9, 2019

Normally, the factorial of a positive integer n is the product of all positive integers less than or equal to n.  For example, factorial(10) = 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.

We instead make a clumsy factorial: using the integers in decreasing order, we swap out the multiply operations for a fixed rotation of operations: multiply (*), divide (/), add (+) and subtract (-) in this order.

For example, clumsy(10) = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1.  However, these operations are still applied using the usual order of operations of arithmetic: we do all multiplication and division steps before any addition or subtraction steps, and multiplication and division steps are processed left to right.

Additionally, the division that we use is floor division such that 10 * 9 / 8 equals 11.  This guarantees the result is an integer.

Implement the clumsy function as defined above: given an integer N, it returns the clumsy factorial of N.

Example 1:

Input: 4
Output: 7
Explanation: 7 = 4 * 3 / 2 + 1

Example 2:

Input: 10
Output: 12
Explanation: 12 = 10 * 9 / 8 + 7 - 6 * 5 / 4 + 3 - 2 * 1

Note:

  1. 1 <= N <= 10000
  2. -2^31 <= answer <= 2^31 - 1  (The answer is guaranteed to fit within a 32-bit integer.)

Solution: Simulation

Time complexity: O(n)
Space complexity: O(1)

C++

花花酱 LeetCode 991. Broken Calculator

By zxi on February 10, 2019

On a broken calculator that has a number showing on its display, we can perform two operations:

  • Double: Multiply the number on the display by 2, or;
  • Decrement: Subtract 1 from the number on the display.

Initially, the calculator is displaying the number X.

Return the minimum number of operations needed to display the number Y.

Example 1:

Input: X = 2, Y = 3
Output: 2
Explanation: Use double operation and then decrement operation {2 -> 4 -> 3}.

Example 2:

Input: X = 5, Y = 8
Output: 2
Explanation: Use decrement and then double {5 -> 4 -> 8}.

Example 3:

Input: X = 3, Y = 10
Output: 3
Explanation:  Use double, decrement and double {3 -> 6 -> 5 -> 10}.

Example 4:

Input: X = 1024, Y = 1
Output: 1023
Explanation: Use decrement operations 1023 times.

Note:

  1. 1 <= X <= 10^9
  2. 1 <= Y <= 10^9

Solution: Greedy

Thinking backwards, making Y <= X by adding 1 or dividing 2.

If Y is even, (Y + 1) // 2 == Y // 2, there is no need to do the extra step
If Y is odd (Y + 1) // 2 = (Y // 2) + 1, so only do + 1 when Y is odd

Time complexity: O(log(Y-X))
Space complexity: O(1)

C++

花花酱 LeetCode 989. Add to Array-Form of Integer

By zxi on February 10, 2019

For a non-negative integer X, the array-form of X is an array of its digits in left to right order.  For example, if X = 1231, then the array form is [1,2,3,1].

Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.

Example 1:

Input: A = [1,2,0,0], K = 34
Output: [1,2,3,4]
Explanation: 1200 + 34 = 1234

Example 2:

Input: A = [2,7,4], K = 181
Output: [4,5,5]
Explanation: 274 + 181 = 455

Example 3:

Input: A = [2,1,5], K = 806
Output: [1,0,2,1]
Explanation: 215 + 806 = 1021

Example 4:

Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1
Output: [1,0,0,0,0,0,0,0,0,0,0]
Explanation: 9999999999 + 1 = 10000000000

Note：

  1. 1 <= A.length <= 10000
  2. 0 <= A[i] <= 9
  3. 0 <= K <= 10000
  4. If A.length > 1, then A[0] != 0

Solution: Simulation

Time complexity: O(n) Space complexity: O(n)

C++

花花酱 LeetCode 781. Rabbits in Forest

By zxi on February 9, 2019

In a forest, each rabbit has some color. Some subset of rabbits (possibly all of them) tell you how many other rabbits have the same color as them. Those answers are placed in an array.

Return the minimum number of rabbits that could be in the forest.

Examples:
Input: answers = [1, 1, 2]
Output: 5
Explanation:
The two rabbits that answered "1" could both be the same color, say red.
The rabbit than answered "2" can't be red or the answers would be inconsistent.
Say the rabbit that answered "2" was blue.
Then there should be 2 other blue rabbits in the forest that didn't answer into the array.
The smallest possible number of rabbits in the forest is therefore 5: 3 that answered plus 2 that didn't.

Input: answers = [10, 10, 10]
Output: 11

Input: answers = []
Output: 0

Note:

  1. answers will have length at most 1000.
  2. Each answers[i] will be an integer in the range [0, 999].

Solution: Math

Say there n rabbits answered x.
if n <= x: they can have the same color
if n > x: they must be divided into groups, each group has x + 1 rabbits, and there are at least ceil(n / (x+1)) groups.
So there will be ceil(n / (x + 1)) * (x + 1) rabbits. This expression can be expressed as (n + x) / (x + 1) * (x + 1) in programming languages. (n + x) // (x + 1) * (x + 1) for Python3.

C++

Python3