Press "Enter" to skip to content

Posts published in “Math”

花花酱 LeetCode 9. Palindrome Number

Problem

Determine whether an integer is a palindrome. An integerĀ isĀ aĀ palindrome when itĀ reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Could you solveĀ it without converting the integer to a string?

Solution 1: Convert to string (cheating)

Time complexity: O(log10(x))

Space complexity: O(log10(x))

C++

Solution 2: Digit by Digit

Every time we compare the first and last digits of x, if they are not the same, return false. Otherwise, remove first and last digit and continue this process.

How can we achieve that via int math?

e.g. x = 9999, t = pow((10, int)log10(x)) = 1000

first digit: x / t, last digit: x % 10

then x = (x – x / t * t) / 10 removes first and last digits.

t /= 100 since we removed two digits.

x / t = 9 = 9 = x % 10, 9999 => 99

9 = 9, 99 => “”

Time complexity: O(log10(x) / 2)

Space complexity: O(1)

C++

花花酱 LeetCode 891. Sum of Subsequence Widths

Problem

Given an array of integersĀ A, consider all non-empty subsequences ofĀ A.

For any sequence S, let theĀ widthĀ of S be the difference between the maximum and minimum element of S.

Return the sum of the widths of all subsequences of A.

As the answer may be very large,Ā return the answer modulo 10^9 + 7.

Example 1:

Input: [2,1,3]
Output: 6
Explanation:
Subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].
The corresponding widths are 0, 0, 0, 1, 1, 2, 2.
The sum of these widths is 6.

Note:

  • 1 <= A.length <= 20000
  • 1 <= A[i] <= 20000

Ā 

Solution: Math

Sort the array, for A[i]:

  • i numbers <= A[i]. A[i] is the upper bound of 2^i subsequences.
  • n – i – 1 numbers >= A[i]. A[i] is the lower bound of 2^(n – i – 1) subsequences.
  • A[i] contributesĀ A[i] * 2^i –Ā A[i] * 2^(n – i – 1) to the ans.
\(ans = \sum\limits_{i=0}^{n-1}A_{i}2^{i} – A_{i}2^{n – i – 1} =\sum\limits_{i=0}^{n-1}(A_i – A_{n-i-1})2^{i}\)

Time complexity: O(nlogn)

Space complexity: O(1)

Time complexity: O(n)

Space complexity: O(n)

Counting sort

 

花花酱 LeetCode 628. Maximum Product of Three Numbers

Problem

Given an integer array, find three numbers whose product is maximum and output the maximum product.

Example 1:

Input: [1,2,3]
Output: 6

Example 2:

Input: [1,2,3,4]
Output: 24

Note:

  1. The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
  2. Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.

Idea:

Find the top 3 numbers t1, t2, t3, and bottom 2 numbers, b1, b2.

If all numbers are positives,Ā  answer must be t1 * t2 * t3.

Since the number can go negative, the answer must be either t1*t2*t3 or b1 * b2 * t1, if b1 and b2 are both negatives.

ex. nums: [5, 1, -6, 3, -1]

t1, t2, t3: 5, 3, 1

b1, b2: -6, -1

t1 * t2 * t3 = 15

t1 * b1 * b2 = 30

Solution 1: Manual Tracking

Time complexity: O(n)

Space complexity: O(1)

Solution 2: Sorting

Time complexity: O(nlogn)

Space complexity: O(1)

Solution 3: Two Heaps (Priority Queues)

Time complexity: O(nlog3)

Space complexity: O(2 + 3)

 

花花酱 LeetCode 463. Island Perimeter

Problem

You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn’t have “lakes” (water inside that isn’t connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don’t exceed 100. Determine the perimeter of the island.

Example:

[[0,1,0,0],
 [1,1,1,0],
 [0,1,0,0],
 [1,1,0,0]]

Answer: 16
Explanation: The perimeter is the 16 yellow stripes in the image below:

Solution: Counting

If a land has 0 neighbour, it contributes 4 to theĀ perimeter

If a land has 1 neighbour, it contributes 3 to theĀ perimeter

If a land has 2 neighbours, it contributes 2 to theĀ perimeter

If a land has 3 neighbours, it contributes 1 to the perimeter

If a land has 4 neighbours, it contributes 0 to the perimeter

perimeter = area * 4 – total_neighbours

Time complexity: O(mn)

Space complexity: O(1)

 

花花酱 LeetCode 592. Fraction Addition and Subtraction

Problem

Given a string representing an expression of fraction addition and subtraction, you need to return the calculation result in string format. The final result should beĀ irreducible fraction. If your final result is an integer, sayĀ 2, you need to change it to the format of fraction that has denominatorĀ 1. So in this case,Ā 2Ā should be converted toĀ 2/1.

Example 1:

Input:"-1/2+1/2"
Output: "0/1"

Example 2:

Input:"-1/2+1/2+1/3"
Output: "1/3"

Example 3:

Input:"1/3-1/2"
Output: "-1/6"

Example 4:

Input:"5/3+1/3"
Output: "2/1"

Note:

  1. The input string only containsĀ '0'Ā toĀ '9',Ā '/',Ā '+'Ā andĀ '-'. So does the output.
  2. Each fraction (input and output) has formatĀ Ā±numerator/denominator. If the first input fraction or the output is positive, thenĀ '+'Ā will be omitted.
  3. The input only contains validĀ irreducible fractions, where theĀ numeratorĀ andĀ denominatorĀ of each fraction will always be in the range [1,10]. If the denominator is 1, it means this fraction is actually an integer in a fraction format defined above.
  4. The number of given fractions will be in the range [1,10].
  5. The numerator and denominator of theĀ final resultĀ are guaranteed to be valid and in the range of 32-bit int.

Solution: Math

a/b+c/d = (a*d + b * c) / (b * d)

Time complexity: O(n)

Space complexity: O(1)

C++

C++/class