Press "Enter" to skip to content

Posts published in “Math”

花花酱 LeetCode 2652. Sum Multiples

Given a positive integer n, find the sum of all integers in the range [1, n] inclusive that are divisible by 35, or 7.

Return an integer denoting the sum of all numbers in the given range satisfying the constraint.

Example 1:

Input: n = 7
Output: 21
Explanation: Numbers in the range [1, 7] that are divisible by 3, 5, or 7 are 3, 5, 6, 7. The sum of these numbers is 21.

Example 2:

Input: n = 10
Output: 40
Explanation: Numbers in the range [1, 10] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9, 10. The sum of these numbers is 40.

Example 3:

Input: n = 9
Output: 30
Explanation: Numbers in the range [1, 9] that are divisible by 3, 5, or 7 are 3, 5, 6, 7, 9. The sum of these numbers is 30.

Constraints:

  • 1 <= n <= 103

Solution: Mod

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

C++

花花酱 LeetCode 2651. Calculate Delayed Arrival Time

You are given a positive integer arrivalTime denoting the arrival time of a train in hours, and another positive integer delayedTime denoting the amount of delay in hours.

Return the time when the train will arrive at the station.

Note that the time in this problem is in 24-hours format.

Example 1:

Input: arrivalTime = 15, delayedTime = 5 
Output: 20 
Explanation: Arrival time of the train was 15:00 hours. It is delayed by 5 hours. Now it will reach at 15+5 = 20 (20:00 hours).

Example 2:

Input: arrivalTime = 13, delayedTime = 11
Output: 0
Explanation: Arrival time of the train was 13:00 hours. It is delayed by 11 hours. Now it will reach at 13+11=24 (Which is denoted by 00:00 in 24 hours format so return 0).

Constraints:

  • 1 <= arrivaltime < 24
  • 1 <= delayedTime <= 24

Solution: Mod 24

C++

花花酱 LeetCode 2582. Pass the Pillow

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 nth person they pass it to the n - 1th person, then to the n - 2th 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 2nd 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 3rd 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++

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

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 <= 105
  • word.length == n
  • word consists of digits from 0 to 9
  • 1 <= m <= 109

Solution: Big Integer Math

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

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

C++

花花酱 LeetCode 2469. Convert the Temperature

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 ansAnswers 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++