Posts tagged as “sum”

花花酱 LeetCode 1648. Sell Diminishing-Valued Colored Balls

By zxi on November 7, 2020

You have an inventory of different colored balls, and there is a customer that wants orders balls of any color.

The customer weirdly values the colored balls. Each colored ball’s value is the number of balls of that color you currently have in your inventory. For example, if you own 6 yellow balls, the customer would pay 6 for the first yellow ball. After the transaction, there are only 5 yellow balls left, so the next yellow ball is then valued at 5 (i.e., the value of the balls decreases as you sell more to the customer).

You are given an integer array, inventory, where inventory[i] represents the number of balls of the i^th color that you initially own. You are also given an integer orders, which represents the total number of balls that the customer wants. You can sell the balls in any order.

Return the maximum total value that you can attain after selling orders colored balls. As the answer may be too large, return it modulo 10⁹+ 7.

Example 1:

Input: inventory = [2,5], orders = 4
Output: 14
Explanation: Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
The maximum total value is 2 + 5 + 4 + 3 = 14.

Example 2:

Input: inventory = [3,5], orders = 6
Output: 19
Explanation: Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2).
The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.

Example 3:

Input: inventory = [2,8,4,10,6], orders = 20
Output: 110

Example 4:

Input: inventory = [1000000000], orders = 1000000000
Output: 21
Explanation: Sell the 1st color 1000000000 times for a total value of 500000000500000000. 500000000500000000 modulo 10⁹+ 7 = 21.

Constraints:

1 <= inventory.length <= 10⁵
1 <= inventory[i] <= 10⁹
1 <= orders <= min(sum(inventory[i]), 10⁹)

Solution: Greedy

Sort the colors by # of balls in descending order.
e.g. 3 7 5 1 => 7 5 3 1
Sell the color with largest number of balls until it has the same number of balls of next color
1. 7 5 3 1 => 6 5 3 1 => 5 5 3 1 # value = 7 + 6 = 13
2. 5 5 3 1 => 4 4 3 1 => 3 3 3 1 # value = 13 + (5 + 4) * 2 = 31
3. 3 3 3 1 => 2 2 2 1 => 1 1 1 1 # value = 31 + (3 + 2) * 3 = 46
4. 1 1 1 1 => 0 0 0 0 # value = 46 + 1 * 4 = 50
Need to handle the case if orders < total balls…

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

C++

// Author: Huahua

class Solution {

public:

int maxProfit(vector<int>& inventory, int orders) {

constexpr int kMod = 1e9 + 7;

const int n = inventory.size();

sort(rbegin(inventory), rend(inventory));

long cur = inventory[0];

long ans = 0;

int c = 0;

while (orders) {

while (c < n && inventory[c] == cur) ++c;

int nxt = c == n ? 0 : inventory[c];

int count = min(static_cast<long>(orders), c * (cur - nxt));

int t = cur - nxt;

int r = 0;

if (orders < c * (cur - nxt)) {

t = orders / c;

r = orders % c;

}

ans = (ans + (cur + cur - t + 1) * t / 2 * c + (cur - t) * r) % kMod;

orders -= count;

cur = nxt;

}

return ans;

}

};

花花酱 LeetCode 1186. Maximum Subarray Sum with One Deletion

By zxi on September 7, 2019

Given an array of integers, return the maximum sum for a non-empty subarray (contiguous elements) with at most one element deletion. In other words, you want to choose a subarray and optionally delete one element from it so that there is still at least one element left and the sum of the remaining elements is maximum possible.

Note that the subarray needs to be non-empty after deleting one element.

Example 1:

Input: arr = [1,-2,0,3]
Output: 4
Explanation: Because we can choose [1, -2, 0, 3] and drop -2, thus the subarray [1, 0, 3] becomes the maximum value.

Example 2:

Input: arr = [1,-2,-2,3]
Output: 3
Explanation: We just choose [3] and it's the maximum sum.

Example 3:

Input: arr = [-1,-1,-1,-1]
Output: -1
Explanation: The final subarray needs to be non-empty. You can't choose [-1] and delete -1 from it, then get an empty subarray to make the sum equals to 0.

Constraints:

1 <= arr.length <= 10^5
-10^4 <= arr[i] <= 10^4

Solution: DP

First, handle the special case: all numbers are negative, return the max one.

s0 = max subarray sum ends with a[i]
s1 = max subarray sum ends with a[i] with at most one deletion

whenever s0 or s1 becomes negative, reset them to 0.

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

C++

// Author: Huahua

class Solution {

public:

int maximumSum(vector<int>& arr) {

int m = *max_element(begin(arr), end(arr));

if (m <= 0) return m;

int s0 = 0;

int s1 = 0;

int ans = 0;

for (int a : arr) {

s1 = max(s0, s1 + a);

s0 += a;

ans = max(ans, max(s0, s1));

if (s0 < 0) s0 = 0;

if (s1 < 0) s1 = 0;

}

return ans;

}

};

花花酱 LeetCode 1184. Distance Between Bus Stops

By zxi on September 7, 2019

A bus has n stops numbered from 0 to n - 1 that form a circle. We know the distance between all pairs of neighboring stops where distance[i] is the distance between the stops number i and (i + 1) % n.

The bus goes along both directions i.e. clockwise and counterclockwise.

Return the shortest distance between the given start and destination stops.

Example 1:

Input: distance = [1,2,3,4], start = 0, destination = 1
Output: 1
Explanation: Distance between 0 and 1 is 1 or 9, minimum is 1.

Example 2:

Input: distance = [1,2,3,4], start = 0, destination = 2
Output: 3
Explanation: Distance between 0 and 2 is 3 or 7, minimum is 3.

Example 3:

Input: distance = [1,2,3,4], start = 0, destination = 3
Output: 4
Explanation: Distance between 0 and 3 is 6 or 4, minimum is 4.

Constraints:

1 <= n <= 10^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4

Solution: Summation

compute the total sum
compute the sum from s to d, c
ans = min(c, sum – c)

Time complexity: O(d-s)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int distanceBetweenBusStops(vector<int>& ds, int s, int d) {

if (s > d) swap(s, d);

int sum = accumulate(begin(ds), end(ds), 0);

int d1 = accumulate(begin(ds) + s, begin(ds) + d, 0);

return min(d1, sum - d1);

}

};

花花酱 LeetCode 985. Sum of Even Numbers After Queries

By zxi on February 2, 2019

Problem

We have an array A of integers, and an array queries of queries.

For the i-th query val = queries[i][0], index = queries[i][1], we add val to A[index]. Then, the answer to the i-th query is the sum of the even values of A.

(Here, the given index = queries[i][1] is a 0-based index, and each query permanently modifies the array A.)

Return the answer to all queries. Your answer array should have answer[i] as the answer to the i-th query.

Example 1:

Input: A = [1,2,3,4], queries = [[1,0],[-3,1],[-4,0],[2,3]]
Output: [8,6,2,4]
Explanation: 
At the beginning, the array is [1,2,3,4].
After adding 1 to A[0], the array is [2,2,3,4], and the sum of even values is 2 + 2 + 4 = 8.
After adding -3 to A[1], the array is [2,-1,3,4], and the sum of even values is 2 + 4 = 6.
After adding -4 to A[0], the array is [-2,-1,3,4], and the sum of even values is -2 + 4 = 2.
After adding 2 to A[3], the array is [-2,-1,3,6], and the sum of even values is -2 + 6 = 4.

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
1 <= queries.length <= 10000
-10000 <= queries[i][0] <= 10000
0 <= queries[i][1] < A.length

Solution: Simulation

Time complexity: O(n + |Q|)
Space complexity: O(n)

C++

// Author: Huahua, Running time: 100 ms / 6.5 MB

class Solution {

public:

vector<int> sumEvenAfterQueries(vector<int>& A, vector<vector<int>>& queries) {

int sum = 0;

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

if (A[i] % 2 == 0)

sum += A[i];

vector<int> ans;

for (const auto& query : queries) {

int& a = A[query[1]];

if (a % 2 == 0)

sum -= a;

a += query[0];

if (a % 2 == 0)

sum += a;

ans.push_back(sum);

}

return ans;

}

};

Python3

# Author: Huahua, running time: 188 ms / 16.4MB

class Solution:

def sumEvenAfterQueries(self, A: 'List[int]', queries: 'List[List[int]]') -> 'List[int]':

s = sum(x for x in A if x % 2 == 0)

ans = []

for val, index in queries:

if A[index] % 2 == 0: s -= A[index]

A[index] += val

if A[index] % 2 == 0: s += A[index]

ans.append(s)

return ans

花花酱 LeetCode 404. Sum of Left Leaves

By zxi on August 16, 2018

Solution: Recursion

Time complexity: O(n)

Space complexity: O(h)

C++

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int sumOfLeftLeaves(TreeNode* root) {

if (!root) return 0;

if (root->left && !root->left->left && !root->left->right)

return root->left->val + sumOfLeftLeaves(root->right);

return sumOfLeftLeaves(root->left) + sumOfLeftLeaves(root->right);

}

};

Iterative

// Author: Huahua

// Running time: 4 ms

class Solution {

public:

int sumOfLeftLeaves(TreeNode* root) {

if (!root) return 0;

queue<TreeNode*> q;

q.push(root);

int sum = 0;

while (!q.empty()) {

TreeNode* n = q.front();

q.pop();

TreeNode* l = n->left;

if (l) {

if (!l->left && !l->right)

sum += l->val;

else

q.push(l);

}

if (n->right) q.push(n->right);

}

return sum;

}

};