Posts tagged as “math”

花花酱 LeetCode 2582. Pass the Pillow

By zxi on March 5, 2023

There are n people standing in a line labeled from 1 to n. The first person in the line is holding a pillow initially. Every second, the person holding the pillow passes it to the next person standing in the line. Once the pillow reaches the end of the line, the direction changes, and people continue passing the pillow in the opposite direction.

For example, once the pillow reaches the n^th person they pass it to the n - 1^th person, then to the n - 2^th person and so on.

Given the two positive integers n and time, return the index of the person holding the pillow after time seconds.

Example 1:

Input: n = 4, time = 5
Output: 2
Explanation: People pass the pillow in the following way: 1 -> 2 -> 3 -> 4 -> 3 -> 2.
Afer five seconds, the pillow is given to the 2^nd person.

Example 2:

Input: n = 3, time = 2
Output: 3
Explanation: People pass the pillow in the following way: 1 -> 2 -> 3.
Afer two seconds, the pillow is given to the 3^r^d person.

Constraints:

2 <= n <= 1000
1 <= time <= 1000

Solution: Math

It takes n – 1 seconds from 1 to n and takes another n – 1 seconds back from n to 1.
So one around takes 2 * (n – 1) seconds. We can mod time with 2 * (n – 1).

After that if time < n – 1 answer is time + 1, otherwise answer is n – (time – (n – 1))

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

C++

// Author: Huahua

class Solution {

public:

int passThePillow(int n, int time) {

time %= (2 * (n - 1));

return time > n - 1 ? n - (time - (n - 1)) : time + 1;

}

};

花花酱 LeetCode 2575. Find the Divisibility Array of a String

By zxi on February 25, 2023

You are given a 0-indexed string word of length n consisting of digits, and a positive integer m.

The divisibility array div of word is an integer array of length n such that:

div[i] = 1 if the numeric value of word[0,...,i] is divisible by m, or
div[i] = 0 otherwise.

Return the divisibility array of word.

Example 1:

Input: word = "998244353", m = 3
Output: [1,1,0,0,0,1,1,0,0]
Explanation: There are only 4 prefixes that are divisible by 3: "9", "99", "998244", and "9982443".

Example 2:

Input: word = "1010", m = 10
Output: [0,1,0,1]
Explanation: There are only 2 prefixes that are divisible by 10: "10", and "1010".

Constraints:

1 <= n <= 10⁵
word.length == n
word consists of digits from 0 to 9
1 <= m <= 10⁹

Solution: Big Integer Math

r = (r * 10 + word[i]) % m

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

C++

// Author: Huahua

class Solution {

public:

vector<int> divisibilityArray(string word, int m) {

vector<int> ans;

long long r = 0;

for (char c : word) {

r = (r * 10 + c - '0') % m;

ans.push_back(r == 0);

}

return ans;

}

};

花花酱 LeetCode 2469. Convert the Temperature

By zxi on November 22, 2022

You are given a non-negative floating point number rounded to two decimal places celsius, that denotes the temperature in Celsius.

You should convert Celsius into Kelvin and Fahrenheit and return it as an array ans = [kelvin, fahrenheit].

Return the array ans. Answers within 10^-5 of the actual answer will be accepted.

Note that:

Kelvin = Celsius + 273.15
Fahrenheit = Celsius * 1.80 + 32.00

Example 1:

Input: celsius = 36.50
Output: [309.65000,97.70000]
Explanation: Temperature at 36.50 Celsius converted in Kelvin is 309.65 and converted in Fahrenheit is 97.70.

Example 2:

Input: celsius = 122.11
Output: [395.26000,251.79800]
Explanation: Temperature at 122.11 Celsius converted in Kelvin is 395.26 and converted in Fahrenheit is 251.798.

Constraints:

0 <= celsius <= 1000

Solution: Follow the formulas

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

C++

// Author: Huahua

class Solution {

public:

vector<double> convertTemperature(double celsius) {

return {celsius + 273.15, celsius * 1.80 + 32.00};

}

};

花花酱 LeetCode 2409. Count Days Spent Together

By zxi on September 17, 2022

Alice and Bob are traveling to Rome for separate business meetings.

You are given 4 strings arriveAlice, leaveAlice, arriveBob, and leaveBob. Alice will be in the city from the dates arriveAlice to leaveAlice (inclusive), while Bob will be in the city from the dates arriveBob to leaveBob (inclusive). Each will be a 5-character string in the format "MM-DD", corresponding to the month and day of the date.

Return the total number of days that Alice and Bob are in Rome together.

You can assume that all dates occur in the same calendar year, which is not a leap year. Note that the number of days per month can be represented as: [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31].

Example 1:

Input: arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"
Output: 3
Explanation: Alice will be in Rome from August 15 to August 18. Bob will be in Rome from August 16 to August 19. They are both in Rome together on August 16th, 17th, and 18th, so the answer is 3.

Example 2:

Input: arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31"
Output: 0
Explanation: There is no day when Alice and Bob are in Rome together, so we return 0.

Constraints:

All dates are provided in the format "MM-DD".
Alice and Bob’s arrival dates are earlier than or equal to their leaving dates.
The given dates are valid dates of a non-leap year.

Solution: Math

Convert date to days of the year.

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

C++

// Author: Huahua

class Solution {

public:

int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {

array<int, 12> days{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

auto getDay = [&](string date) {

int mm = (date[0] - '0') * 10 + (date[1] - '0');

int dd = (date[3] - '0') * 10 + (date[4] - '0');

return accumulate(begin(days), begin(days) + mm - 1, dd);

};

int s = max(getDay(arriveAlice), getDay(arriveBob));

int e = min(getDay(leaveAlice), getDay(leaveBob));

return e >= s ? e - s + 1 : 0;

}

};

花花酱 LeetCode 2396. Strictly Palindromic Number

By zxi on September 7, 2022

An integer n is strictly palindromic if, for every base b between 2 and n - 2 (inclusive), the string representation of the integer n in base b is palindromic.

Given an integer n, return true if n is strictly palindromic and false otherwise.

A string is palindromic if it reads the same forward and backward.

Example 1:

Input: n = 9
Output: false
Explanation: In base 2: 9 = 1001 (base 2), which is palindromic.
In base 3: 9 = 100 (base 3), which is not palindromic.
Therefore, 9 is not strictly palindromic so we return false.
Note that in bases 4, 5, 6, and 7, n = 9 is also not palindromic.

Example 2:

Input: n = 4
Output: false
Explanation: We only consider base 2: 4 = 100 (base 2), which is not palindromic.
Therefore, we return false.

Constraints:

4 <= n <= 10⁵

Solution: Just return false

No such number.

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

C++

// Author: Huahua

class Solution {

public:

bool isStrictlyPalindromic(int n) {

return false;

}

};