Posts tagged as “math”

花花酱 LeetCode 1201. Ugly Number III

By zxi on September 22, 2019

Write a program to find the n-th ugly number.

Ugly numbers are positive integers which are divisible by a or b or c.

Example 1:

Input: n = 3, a = 2, b = 3, c = 5
Output: 4
Explanation: The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.

Example 2:

Input: n = 4, a = 2, b = 3, c = 4
Output: 6
Explanation: The ugly numbers are 2, 3, 4, 6, 8, 9, 12... The 4th is 6.

Example 3:

Input: n = 5, a = 2, b = 11, c = 13
Output: 10
Explanation: The ugly numbers are 2, 4, 6, 8, 10, 11, 12, 13... The 5th is 10.

Example 4:

Input: n = 1000000000, a = 2, b = 217983653, c = 336916467
Output: 1999999984

Constraints:

1 <= n, a, b, c <= 10^9
1 <= a * b * c <= 10^18
It’s guaranteed that the result will be in range [1, 2 * 10^9]

Solution: Binary Search

Number of ugly numbers that are <= m are:

m / a + m / b + m / c – (m / LCM(a,b) + m / LCM(a, c) + m / LCM(b, c) + m / LCM(a, LCM(b, c))

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

C++

// Author: Huahua

class Solution {

public:

int nthUglyNumber(int n, long a, long b, long c) {

long l = 1;

long r = INT_MAX;

long ab = lcm(a, b);

long ac = lcm(a, c);

long bc = lcm(b, c);

long abc = lcm(a, bc);

while (l < r) {

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

long k = m / a + m / b + m / c - m / ab - m / ac - m / bc + m / abc;

if (k >= n) r = m;

else l = m + 1;

}

return l;

}

};

花花酱 LeetCode 1185. Day of the Week

By zxi on September 7, 2019

Given a date, return the corresponding day of the week for that date.

The input is given as three integers representing the day, month and year respectively.

Return the answer as one of the following values {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}.

Example 1:

Input: day = 31, month = 8, year = 2019
Output: "Saturday"

Example 2:

Input: day = 18, month = 7, year = 1999
Output: "Sunday"

Example 3:

Input: day = 15, month = 8, year = 1993
Output: "Sunday"

Constraints:

The given dates are valid dates between the years 1971 and 2100.

Solution: LeapYear

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

C++

// Author: Huahua

inline bool leapYear(int y) {

return (y % 4 == 0 && y % 100 != 0) || (y % 400 == 0);

}

class Solution {

public:

string dayOfTheWeek(int day, int month, int year) {

vector<string> names = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};

vector<int> days = {31, 28 + leapYear(year), 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int sum = 0;

for (int i = 1970; i < year; ++i)

sum += 365 + leapYear(i);

for (int i = 1; i < month; ++i)

sum += days[i - 1];

sum += day;

return names[(sum + 3) % 7];

}

};

花花酱 LeetCode 1109. Corporate Flight Bookings

By zxi on July 11, 2019

There are n flights, and they are labeled from 1 to n.

We have a list of flight bookings. The i-th booking bookings[i] = [i, j, k] means that we booked kseats from flights labeled i to j inclusive.

Return an array answer of length n, representing the number of seats booked on each flight in order of their label.

Example 1:

Input: bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
Output: [10,55,45,25,25]

Constraints:

1 <= bookings.length <= 20000
1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000
1 <= bookings[i][2] <= 10000

Solution: Marking start and end

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

C++

// Author: Huahua

class Solution {

public:

vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {

vector<int> ans(n + 1);

for (const auto& b : bookings) {

ans[b[0] - 1] += b[2];

ans[b[1]] -= b[2];

}

for (int i = 1; i < n; ++i)

ans[i] += ans[i - 1];

ans.pop_back();

return ans;

}

};

花花酱 LeetCode 1104. Path In Zigzag Labelled Binary Tree

By zxi on July 1, 2019

In an infinite binary tree where every node has two children, the nodes are labelled in row order.

In the odd numbered rows (ie., the first, third, fifth,…), the labelling is left to right, while in the even numbered rows (second, fourth, sixth,…), the labelling is right to left.

Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.

Example 1:

Input: label = 14
Output: [1,3,4,14]

Example 2:

Input: label = 26
Output: [1,2,6,10,26]

Constraints:

1 <= label <= 10^6

Solution: Math

Time complexity: O(logn)
Space complexity: O(logn)

C++

// Author: Huahua

class Solution {

public:

vector<int> pathInZigZagTree(int label) {

deque<int> ans;

while (label) {

ans.push_front(label);

int h = 31 - __builtin_clz(label);

label = ((1 << h) + (1 << (h + 1)) - 1 - label) / 2;

}

return {begin(ans), end(ans)};

}

};

花花酱 LeetCode 640. Solve the Equation

By zxi on May 10, 2019

Solve a given equation and return the value of x in the form of string “x=#value”. The equation contains only ‘+’, ‘-‘ operation, the variable x and its coefficient.

If there is no solution for the equation, return “No solution”.

If there are infinite solutions for the equation, return “Infinite solutions”.

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"

Solution: Parse the equation

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

C++

// Author: Huahua, 0 ms, 8.5 MB

class Solution {

public:

string solveEquation(const string& equation) {

auto parse = [](string_view s) -> vector<int> {

int a{0}, b{0};

int sign = 1;

long t = 0;

bool d = false;

for (char c : s) {

if (isdigit(c)) {

d = true;

t = t * 10 + c - '0';

} else {

if (c == 'x')

a += (d ? t : 1) * sign;

else {

b += t * sign;

sign = c == '+' ? 1 : -1;

}

d = false;

t = 0;

}

b += t * sign;

return {a, b};

};

auto pos = equation.find('=');

auto l = parse(string_view(equation).substr(0, pos));

auto r = parse(string_view(equation).substr(pos + 1));

l[0] -= r[0];

l[1] -= r[1];

if (l[0] == 0)

return l[1] == 0 ? "Infinite solutions" : "No solution";

return "x=" + to_string(-l[1] / l[0]);

}

};