求合取余即可，余数就是答案。
Time complexity: O(n)
Space complexity: O(1)
|
1 2 3 4 5 6 |
class Solution { public: int minOperations(vector<int>& nums, int k) { return accumulate(begin(nums), end(nums), 0) % k; } }; |
Posts published in “Math”
Given a positive integer n, find the sum of all integers in the range [1, n] inclusive that are divisible by 3, 5, 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 by3,5,or7are3, 5, 6, 7. The sum of these numbers is21.
Example 2:
Input: n = 10 Output: 40 Explanation: Numbers in the range[1, 10] that aredivisible by3,5,or7are3, 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 by3,5, or7are3, 5, 6, 7, 9. The sum of these numbers is30.
Constraints:
1 <= n <= 103
Solution: Mod
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua class Solution { public: int sumOfMultiples(int n) { int ans = 0; for (int i = 1; i <= n; ++i) { if (i % 3 == 0 || i % 5 == 0 || i % 7 == 0) ans += i; } return ans; } }; |
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 < 241 <= delayedTime <= 24
Solution: Mod 24
C++
|
1 2 3 4 5 6 7 |
// Author: Huahua class Solution { public: int findDelayedArrivalTime(int arrivalTime, int delayedTime) { return (arrivalTime + delayedTime) % 24; } }; |
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
nthperson they pass it to then - 1thperson, then to then - 2thperson 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 <= 10001 <= 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++
|
1 2 3 4 5 6 7 8 |
// 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; } }; |
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] = 1if the numeric value ofword[0,...,i]is divisible bym, ordiv[i] = 0otherwise.
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 <= 105word.length == nwordconsists of digits from0to91 <= m <= 109
Solution: Big Integer Math
r = (r * 10 + word[i]) % m
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// 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; } }; |