Posts tagged as “math”

花花酱 LeetCode 168. Excel Sheet Column Title

By zxi on November 28, 2021

Given an integer columnNumber, return its corresponding column title as it appears in an Excel sheet.

For example:

A -> 1
B -> 2
C -> 3
...
Z -> 26
AA -> 27
AB -> 28 
...

Example 1:

Input: columnNumber = 1
Output: "A"

Example 2:

Input: columnNumber = 28
Output: "AB"

Example 3:

Input: columnNumber = 701
Output: "ZY"

Example 4:

Input: columnNumber = 2147483647
Output: "FXSHRXW"

Constraints:

1 <= columnNumber <= 2³¹ - 1

Solution: Base conversion

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

C++

// Author: Huahua

class Solution {

public:

string convertToTitle(int n) {

string ans;

do {

n--;

ans += 'A' + (char)(n % 26);

n /= 26;

} while (n);

reverse(begin(ans), end(ans));

return ans;

}

};

花花酱 LeetCode 69. Sqrt(x)

By zxi on November 26, 2021

Given a non-negative integer x, compute and return the square root of x.

Since the return type is an integer, the decimal digits are truncated, and only the integer part of the result is returned.

Note: You are not allowed to use any built-in exponent function or operator, such as pow(x, 0.5) or x ** 0.5.

Example 1:

Input: x = 4
Output: 2

Example 2:

Input: x = 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Constraints:

0 <= x <= 2³¹ - 1

Solution 1: Binary Search

Find the smallest l such that l * l > x, sqrt(x) = l – 1.

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

C++

// Author: Huahua

class Solution {

public:

int mySqrt(int x) {

unsigned l = 1;

unsigned r = 1u + x;

while (l < r) {

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

if (m > x / m) {

r = m;

} else {

l = m + 1;

}

return l - 1;

}

};

花花酱 LeetCode 2073. Time Needed to Buy Tickets

By zxi on November 15, 2021

There are n people in a line queuing to buy tickets, where the 0^th person is at the front of the line and the (n - 1)^th person is at the back of the line.

You are given a 0-indexed integer array tickets of length n where the number of tickets that the i^th person would like to buy is tickets[i].

Each person takes exactly 1 second to buy a ticket. A person can only buy 1 ticket at a time and has to go back to the end of the line (which happens instantaneously) in order to buy more tickets. If a person does not have any tickets left to buy, the person will leave the line.

Return the time taken for the person at position k(0-indexed) to finish buying tickets.

Example 1:

Input: tickets = [2,3,2], k = 2
Output: 6
Explanation: 
- In the first pass, everyone in the line buys a ticket and the line becomes [1, 2, 1].
- In the second pass, everyone in the line buys a ticket and the line becomes [0, 1, 0].
The person at position 2 has successfully bought 2 tickets and it took 3 + 3 = 6 seconds.

Example 2:

Input: tickets = [5,1,1,1], k = 0
Output: 8
Explanation:
- In the first pass, everyone in the line buys a ticket and the line becomes [4, 0, 0, 0].
- In the next 4 passes, only the person in position 0 is buying tickets.
The person at position 0 has successfully bought 5 tickets and it took 4 + 1 + 1 + 1 + 1 = 8 seconds.

Constraints:

n == tickets.length
1 <= n <= 100
1 <= tickets[i] <= 100
0 <= k < n

Solution 1: Simulation

Time complexity: O(n * tickets[k])
Space complexity: O(n) / O(1)

C++

// Author: huahua

class Solution {

public:

int timeRequiredToBuy(vector<int>& tickets, int k) {

const int n = tickets.size();

queue<pair<int, int>> q;

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

q.emplace(i, tickets[i]);

int ans = 0;

while (!q.empty()) {

++ans;

auto [i, t] = q.front(); q.pop();

if (--t == 0 && k == i) return ans;

if (t) q.emplace(i, t);

}

return -1;

}

};

Solution 2: Math

Each person before k will have tickets[k] rounds, each person after k will have tickets[k] – 1 rounds.

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

C++

// Author: huahua

class Solution {

public:

int timeRequiredToBuy(vector<int>& tickets, int k) {

int ans = 0;

for (int i = 0; i < tickets.size(); ++i)

ans += min(tickets[i], tickets[k] - (i > k));

return ans;

}

};

花花酱 LeetCode 2063. Vowels of All Substrings

By zxi on November 7, 2021

Given a string word, return the sum of the number of vowels ('a', 'e', 'i', 'o', and 'u') in every substring of word.

A substring is a contiguous (non-empty) sequence of characters within a string.

Note: Due to the large constraints, the answer may not fit in a signed 32-bit integer. Please be careful during the calculations.

Example 1:

Input: word = "aba"
Output: 6
Explanation: 
All possible substrings are: "a", "ab", "aba", "b", "ba", and "a".
- "b" has 0 vowels in it
- "a", "ab", "ba", and "a" have 1 vowel each
- "aba" has 2 vowels in it
Hence, the total sum of vowels = 0 + 1 + 1 + 1 + 1 + 2 = 6.

Example 2:

Input: word = "abc"
Output: 3
Explanation: 
All possible substrings are: "a", "ab", "abc", "b", "bc", and "c".
- "a", "ab", and "abc" have 1 vowel each
- "b", "bc", and "c" have 0 vowels each
Hence, the total sum of vowels = 1 + 1 + 1 + 0 + 0 + 0 = 3.

Example 3:

Input: word = "ltcd"
Output: 0
Explanation: There are no vowels in any substring of "ltcd".

Example 4:

Input: word = "noosabasboosa"
Output: 237
Explanation: There are a total of 237 vowels in all the substrings.

Constraints:

1 <= word.length <= 10⁵
word consists of lowercase English letters.

Solution: Math

For a vowel at index i,
we can choose 0, 1, … i as starting point
choose i, i+1, …, n -1 as end point.
There will be (i – 0 + 1) * (n – 1 – i + 1) possible substrings that contains word[i].

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

C++

class Solution {

public:

long long countVowels(string word) {

const long long n = word.size();

long long ans = 0;

for (long long i = 0; i < n; ++i) {

switch (word[i]) {

case 'a':

case 'e':

case 'i':

case 'o':

case 'u':

ans += (i + 1) * (n - 1 - i + 1);

break;

}

return ans;

}

};

LeetCode 2033. Minimum Operations to Make a Uni-Value Grid

By zxi on October 21, 2021

You are given a 2D integer grid of size m x n and an integer x. In one operation, you can add x to or subtract x from any element in the grid.

A uni-value grid is a grid where all the elements of it are equal.

Return the minimum number of operations to make the grid uni-value. If it is not possible, return -1.

Example 1:

Input: grid = [[2,4],[6,8]], x = 2
Output: 4
Explanation: We can make every element equal to 4 by doing the following: 
- Add x to 2 once.
- Subtract x from 6 once.
- Subtract x from 8 twice.
A total of 4 operations were used.

Example 2:

Input: grid = [[1,5],[2,3]], x = 1
Output: 5
Explanation: We can make every element equal to 3.

Example 3:

Input: grid = [[1,2],[3,4]], x = 2
Output: -1
Explanation: It is impossible to make every element equal.

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 10⁵
1 <= m * n <= 10⁵
1 <= x, grid[i][j] <= 10⁴

Solution: Median

To achieve minimum operations, the uni-value must be the median of the array.

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

C++

// Author; Huahua

class Solution {

public:

int minOperations(vector<vector<int>>& grid, int x) {

const int mn = grid.size() * grid[0].size();

vector<int> nums;

nums.reserve(mn);

for (const auto& row : grid)

nums.insert(end(nums), begin(row), end(row));

nth_element(begin(nums), begin(nums) + mn / 2, end(nums));

const int median = nums[mn / 2];

int ans = 0;

for (int v : nums) {

if (abs(v - median) % x) return -1;

ans += abs(v - median) / x;

}

return ans;

}

};

Posts tagged as “math”

花花酱 LeetCode 168. Excel Sheet Column Title

Solution: Base conversion

C++

Related Problems

花花酱 LeetCode 69. Sqrt(x)

Solution 1: Binary Search

C++

花花酱 LeetCode 2073. Time Needed to Buy Tickets

Solution 1: Simulation

C++

Solution 2: Math

C++

花花酱 LeetCode 2063. Vowels of All Substrings

Solution: Math

C++

LeetCode 2033. Minimum Operations to Make a Uni-Value Grid

Solution: Median

C++