Posts tagged as “math”

花花酱 LeetCode 628. Maximum Product of Three Numbers

By zxi on August 17, 2018

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:

The length of the given array will be in range [3,10⁴] and all elements are in the range [-1000, 1000].
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)

// Author: Huahua

// Running time: 28 ms

class Solution {

public:

int maximumProduct(vector<int>& nums) {

int max1 = INT_MIN;

int max2 = INT_MIN;

int max3 = INT_MIN;

int min1 = INT_MAX;

int min2 = INT_MAX;

for (const int num: nums) {

if (num > max1) {

max3 = max2;

max2 = max1;

max1 = num;

} else if (num > max2) {

max3 = max2;

max2 = num;

} else if (num > max3) {

max3=num;

}

if (num < min1) {

min2 = min1;

min1 = num;

} else if (num < min2) {

min2=num;

}

return max(max1*max2*max3, max1*min1*min2);

}

};

Solution 2: Sorting

Time complexity: O(nlogn)

Space complexity: O(1)

// Author: Huahua

// Running time: 48 ms

class Solution {

public:

int maximumProduct(vector<int>& nums) {

int n = nums.size();

sort(nums.rbegin(), nums.rend());

return max(nums[0] * nums[1] * nums[2], nums[0] * nums[n - 1] * nums[n - 2]);

}

};

Solution 3: Two Heaps (Priority Queues)

Time complexity: O(nlog3)

Space complexity: O(2 + 3)

// Author: Huahua

// Running time: 40 ms

class Solution {

public:

int maximumProduct(vector<int>& nums) {

priority_queue<int, vector<int>, less<int>> min_q; // max_heap

priority_queue<int, vector<int>, greater<int>> max_q; // min_heap

for (int num : nums) {

max_q.push(num);

if (max_q.size() > 3) max_q.pop();

min_q.push(num);

if (min_q.size() > 2) min_q.pop();

}

int max3 = max_q.top(); max_q.pop();

int max2 = max_q.top(); max_q.pop();

int max1 = max_q.top(); max_q.pop();

int min2 = min_q.top(); min_q.pop();

int min1 = min_q.top(); min_q.pop();

return max(max1 * max2 * max3, max1 * min1 * min2);

}

};

花花酱 LeetCode 463. Island Perimeter

By zxi on August 17, 2018

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)

// Author: Huahua

// Running time: 148 ms

class Solution {

public:

int islandPerimeter(vector<vector<int>>& grid) {

if (grid.empty()) return 0;

int m = grid.size();

int n = grid[0].size();

int area = 0;

int conn = 0;

for (int y = 0; y < m; ++y)

for (int x = 0; x < n; ++x)

if (grid[y][x] == 1) {

++area;

if (y > 0 && grid[y - 1][x] == 1) ++conn;

if (x > 0 && grid[y][x - 1] == 1) ++conn;

}

return area*4 - conn*2;

}

};

花花酱 LeetCode 592. Fraction Addition and Subtraction

By zxi on August 6, 2018

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:

The input string only contains '0' to '9', '/', '+' and '-'. So does the output.
Each fraction (input and output) has format ±numerator/denominator. If the first input fraction or the output is positive, then '+' will be omitted.
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.
The number of given fractions will be in the range [1,10].
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++

// Author: Huahua

class Solution {

public:

string fractionAddition(string expression) {

int a = 0;

int b = 1;

int c;

int d;

char slash;

istringstream in(expression);

while (in >> c >> slash >> d) {

a = a * d + b * c;

b *= d;

int gcd = abs(__gcd(a, b));

a /= gcd;

b /= gcd;

}

return to_string(a) + "/" + to_string(b);

}

};

C++/class

// Author: Huahua

// Running time: 0 ms

class Fraction {

public:

Fraction(int a, int b): a_(a), b_(b) {}

Fraction& operator+=(const Fraction& f) {

a_ = a_ * f.b_ + b_ * f.a_;

b_ = b_ * f.b_;

int d = abs(__gcd(a_, b_));

a_ /= d;

b_ /= d;

return *this;

}

string toString() {

return to_string(a_) + "/" + to_string(b_);

}

private:

int a_; // hold the sign, e.g. can be +-.

int b_; // always > 0.

};

class Solution {

public:

string fractionAddition(string expression) {

Fraction f(0, 1);

int a;

int b;

char op;

istringstream in(expression);

while (in >> a >> op >> b)

f += Fraction(a, b);

return f.toString();

}

};

花花酱 LeetCode 808. Soup Servings

By zxi on August 1, 2018

Problem

There are two types of soup: type A and type B. Initially we have N ml of each type of soup. There are four kinds of operations:

Serve 100 ml of soup A and 0 ml of soup B
Serve 75 ml of soup A and 25 ml of soup B
Serve 50 ml of soup A and 50 ml of soup B
Serve 25 ml of soup A and 75 ml of soup B

When we serve some soup, we give it to someone and we no longer have it. Each turn, we will choose from the four operations with equal probability 0.25. If the remaining volume of soup is not enough to complete the operation, we will serve as much as we can. We stop once we no longer have some quantity of both types of soup.

Note that we do not have the operation where all 100 ml’s of soup B are used first.

Return the probability that soup A will be empty first, plus half the probability that A and B become empty at the same time.

Example:
Input: N = 50
Output: 0.625
Explanation: 
If we choose the first two operations, A will become empty first. For the third operation, A and B will become empty at the same time. For the fourth operation, B will become empty first. So the total probability of A becoming empty first plus half the probability that A and B become empty at the same time, is 0.25 * (1 + 1 + 0.5 + 0) = 0.625.

Notes:

0 <= N <= 10^9.
Answers within 10^-6 of the true value will be accepted as correct.

Solution 1: Recursion with Memorization

Time complexity: O(N^2) N ~ 5000 / 25 = 200

Space complexity: O(N^2)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

double soupServings(int N) {

if (N >= 5000) return 1.0;

return prob(N, N);

}

private:

unordered_map<int, unordered_map<int, double>> m_;

double prob(int A, int B) {

static int ops[][2] = {{100, 0}, {75, 25}, {50, 50}, {25, 75}};

if (A <= 0 && B <= 0) return 0.5;

if (A <= 0) return 1.0;

if (B <= 0) return 0.0;

if (m_.count(A) && m_[A].count(B)) return m_[A][B];

m_[A][B] = 0.0;

for (int i = 0; i < 4; ++i)

m_[A][B] += 0.25 * prob(A - ops[i][0], B - ops[i][1]);

return m_[A][B];

}

};

花花酱 LeetCode 878. Nth Magical Number

By zxi on July 28, 2018

Problem

A positive integer is magical if it is divisible by either A or B.

Return the N-th magical number. Since the answer may be very large, return it modulo 10^9 + 7.

Example 1:

Input: N = 1, A = 2, B = 3
Output: 2

Example 2:

Input: N = 4, A = 2, B = 3
Output: 6

Example 3:

Input: N = 5, A = 2, B = 4
Output: 10

Example 4:

Input: N = 3, A = 6, B = 4
Output: 8

Note:

1 <= N <= 10^9
2 <= A <= 40000
2 <= B <= 40000

Solution: Math + Binary Search

Let n denote the number of numbers <= X that are divisible by either A or B.

n = X / A + X / B – X / lcm(A, B) = X / A + X / B – X / (A * B / gcd(A, B))

Binary search for the smallest X such that n >= N

Time complexity: O(log(1e9*4e5)

Space complexity: O(1)

// Author: Huahua

// Running time: 0 ms

class Solution {

public:

int nthMagicalNumber(int N, int A, int B) {

const int kMod = 1000000007;

long l = 2;

long r = static_cast<long>(1e9 * 4e5);

int d = gcd(A, B);

while (l < r) {

long m = (r - l) / 2 + l;

if (m / A + m / B - m / (A * B / d) < N)

l = m + 1;

else

r = m;

}

return l % kMod;

}

private:

int gcd(int a, int b) {

if (a % b == 0) return b;

return gcd(b, a % b);

}

};