Huahua’s Tech Road

花花酱 LeetCode 2241. Design an ATM Machine

By zxi on April 16, 2022

There is an ATM machine that stores banknotes of 5 denominations: 20, 50, 100, 200, and 500 dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw any amount of money.

When withdrawing, the machine prioritizes using banknotes of larger values.

For example, if you want to withdraw $300 and there are 2 $50 banknotes, 1 $100 banknote, and 1 $200 banknote, then the machine will use the $100 and $200 banknotes.
However, if you try to withdraw $600 and there are 3 $200 banknotes and 1 $500 banknote, then the withdraw request will be rejected because the machine will first try to use the $500 banknote and then be unable to use banknotes to complete the remaining $100. Note that the machine is not allowed to use the $200 banknotes instead of the $500 banknote.

Implement the ATM class:

ATM() Initializes the ATM object.
void deposit(int[] banknotesCount) Deposits new banknotes in the order $20, $50, $100, $200, and $500.
int[] withdraw(int amount) Returns an array of length 5 of the number of banknotes that will be handed to the user in the order $20, $50, $100, $200, and $500, and update the number of banknotes in the ATM after withdrawing. Returns [-1] if it is not possible (do not withdraw any banknotes in this case).

Example 1:

Input
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]
Output
[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]

Explanation
ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // Deposits 1 $100 banknote, 2 $200 banknotes,
                          // and 1 $500 banknote.
atm.withdraw(600);        // Returns [0,0,1,0,1]. The machine uses 1 $100 banknote
                          // and 1 $500 banknote. The banknotes left over in the
                          // machine are [0,0,0,2,0].
atm.deposit([0,1,0,1,1]); // Deposits 1 $50, $200, and $500 banknote.
                          // The banknotes in the machine are now [0,1,0,3,1].
atm.withdraw(600);        // Returns [-1]. The machine will try to use a $500 banknote
                          // and then be unable to complete the remaining $100,
                          // so the withdraw request will be rejected.
                          // Since the request is rejected, the number of banknotes
                          // in the machine is not modified.
atm.withdraw(550);        // Returns [0,1,0,0,1]. The machine uses 1 $50 banknote
                          // and 1 $500 banknote.

Constraints:

banknotesCount.length == 5
0 <= banknotesCount[i] <= 10⁹
1 <= amount <= 10⁹
At most 5000 calls in total will be made to withdraw and deposit.
At least one call will be made to each function withdraw and deposit.

Solution:

Follow the rules. Note: total count can be very large, use long instead.

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

C++

// Author: Huahua

constexpr int kNotes = 5;

constexpr long notes[kNotes] = {20, 50, 100, 200, 500};

class ATM {

public:

ATM(): counts(kNotes) {}

void deposit(vector<int> banknotesCount) {

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

counts[i] += banknotesCount[i];

}

vector<int> withdraw(int amount) {

vector<int> ans(kNotes);

vector<long> tmp(counts);

for (int i = kNotes - 1; i >= 0; --i)

if (amount >= notes[i]) {

int c = min(counts[i], amount / notes[i]);

ans[i] = c;

amount -= c * notes[i];

tmp[i] -= c;

}

if (amount != 0) return {-1};

counts.swap(tmp);

return ans;

}

private:

vector<long> counts;

};

花花酱 LeetCode 2240. Number of Ways to Buy Pens and Pencils

By zxi on April 16, 2022

You are given an integer total indicating the amount of money you have. You are also given two integers cost1 and cost2 indicating the price of a pen and pencil respectively. You can spend part or all of your money to buy multiple quantities (or none) of each kind of writing utensil.

Return the number of distinct ways you can buy some number of pens and pencils.

Example 1:

Input: total = 20, cost1 = 10, cost2 = 5
Output: 9
Explanation: The price of a pen is 10 and the price of a pencil is 5.
- If you buy 0 pens, you can buy 0, 1, 2, 3, or 4 pencils.
- If you buy 1 pen, you can buy 0, 1, or 2 pencils.
- If you buy 2 pens, you cannot buy any pencils.
The total number of ways to buy pens and pencils is 5 + 3 + 1 = 9.

Example 2:

Input: total = 5, cost1 = 10, cost2 = 10
Output: 1
Explanation: The price of both pens and pencils are 10, which cost more than total, so you cannot buy any writing utensils. Therefore, there is only 1 way: buy 0 pens and 0 pencils.

Constraints:

1 <= total, cost1, cost2 <= 10⁶

Solution:

Enumerate all possible ways to buy k pens, e.g. 0 pen, 1 pen, …, total / cost1.
The way to buy pencils are (total – k * cost1) / cost2 + 1.
ans = sum((total – k * cost1) / cost2 + 1)) for k = 0 to total / cost1.

Time complexity: O(total / cost1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

long long waysToBuyPensPencils(int total, int cost1, int cost2) {

long long ans = 0;

for (long long k = 0; k <= total / cost1; ++k)

ans += (total - k * cost1) / cost2 + 1;

return ans;

}

};

花花酱 LeetCode 2239. Find Closest Number to Zero

By zxi on April 16, 2022

Given an integer array nums of size n, return the number with the value closest to 0 in nums. If there are multiple answers, return the number with the largest value.

Example 1:

Input: nums = [-4,-2,1,4,8]
Output: 1
Explanation:
The distance from -4 to 0 is |-4| = 4.
The distance from -2 to 0 is |-2| = 2.
The distance from 1 to 0 is |1| = 1.
The distance from 4 to 0 is |4| = 4.
The distance from 8 to 0 is |8| = 8.
Thus, the closest number to 0 in the array is 1.

Example 2:

Input: nums = [2,-1,1]
Output: 1
Explanation: 1 and -1 are both the closest numbers to 0, so 1 being larger is returned.

Constraints:

1 <= n <= 1000
-10⁵ <= nums[i] <= 10⁵

Solution: ABS

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

C++

// Author: Huahua

class Solution {

public:

int findClosestNumber(vector<int>& nums) {

return *min_element(begin(nums), end(nums), [](int a, int b){

return abs(a) < abs(b) || (abs(a) == abs(b) && a > b);

});

}

};

花花酱 LeetCode 2236. Root Equals Sum of Children

By zxi on April 16, 2022

You are given the root of a binary tree that consists of exactly 3 nodes: the root, its left child, and its right child.

Return true if the value of the root is equal to the sum of the values of its two children, or false otherwise.

Example 1:

Input: root = [10,4,6]
Output: true
Explanation: The values of the root, its left child, and its right child are 10, 4, and 6, respectively.
10 is equal to 4 + 6, so we return true.

Example 2:

Input: root = [5,3,1]
Output: false
Explanation: The values of the root, its left child, and its right child are 5, 3, and 1, respectively.
5 is not equal to 3 + 1, so we return false.

Constraints:

The tree consists only of the root, its left child, and its right child.
-100 <= Node.val <= 100

Solution:

Just want to check whether you know binary tree or not.

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

C++

// Author: Huahua

class Solution {

public:

bool checkTree(TreeNode* root) {

return root->val == root->left->val + root->right->val;

}

};

花花酱 LeetCode 2235. Add Two Integers

By zxi on April 16, 2022

Given two integers num1 and num2, return the sum of the two integers.

Example 1:

Input: num1 = 12, num2 = 5
Output: 17
Explanation: num1 is 12, num2 is 5, and their sum is 12 + 5 = 17, so 17 is returned.

Example 2:

Input: num1 = -10, num2 = 4
Output: -6
Explanation: num1 + num2 = -6, so -6 is returned.

Constraints:

-100 <= num1, num2 <= 100

Solution: Just sum them up

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

C++

// Author: Huahua

class Solution {

public:

int sum(int num1, int num2) {

return num1 + num2;

}

};

Huahua's Tech Road

花花酱 LeetCode 2241. Design an ATM Machine

Solution:

C++

花花酱 LeetCode 2240. Number of Ways to Buy Pens and Pencils

Solution:

C++

花花酱 LeetCode 2239. Find Closest Number to Zero

Solution: ABS

C++

花花酱 LeetCode 2236. Root Equals Sum of Children

Solution:

C++

花花酱 LeetCode 2235. Add Two Integers

Solution: Just sum them up

C++