2806. Account Balance After Rounded Purchase


Problem Description

The given problem scenario describes a situation where an individual has an initial bank account balance of $100. The individual intends to make a purchase with an amount specified by purchaseAmount. However, there is a unique rule at the store where the purchase is made; the actual amount paid, roundedAmount, must be a multiple of 10. To determine this amount, we find the nearest multiple of 10 to the purchaseAmount. If there is a tie between two multiples of 10 (meaning that the purchase amount is exactly halfway between them), we choose the larger multiple. The objective is to find out what the account balance will be after making a purchase according to these rules.

The task involves calculating the roundedAmount by finding the closest multiple of 10 to purchaseAmount. After the roundedAmount is determined, it is subtracted from the initial balance to obtain the final account balance, which is returned by the function.

Intuition

The solution aims to find the nearest multiple of 10 to the purchaseAmount such that the difference |roundedAmount - purchaseAmount| is minimized. If there are two equally close multiples, we select the larger one.

To arrive at the solution, we can iterate backward from the initial balance of $100 in decrements of 10, which are the potential candidates for roundedAmount. As we do this, we calculate the absolute difference between each candidate and the purchaseAmount. The candidate with the smallest difference is the roundedAmount we want to find. If there is a tie, the loop iterating in reverse ensures we choose the larger multiple.

By keeping track of the smallest difference seen so far and the associated candidate (roundedAmount), we can decide which multiple of 10 to select. Once we determine the roundedAmount, the final balance is obtained simply by subtracting this value from the initial balance of $100. The resulting balance after the purchase is what the function returns.

Learn more about Math patterns.

Solution Approach

The implementation of the solution adopts a straightforward approach to solve the problem. The algorithm does not make use of any complex data structures or algorithms, such as dynamic programming or memoization. Instead, it relies on simple iteration and comparison.

Here's a step-by-step breakdown of the solution process:

  1. Initialize two variables: diff, set to a high value (in this case, 100, as no absolute difference can exceed the initial balance), and x, which will represent our roundedAmount.

  2. Iterate backward from the initial balance of $100 to 0 in decrements of 10. Each of these numbers represents a potential roundedAmount.

  3. In each iteration, calculate the temporary difference t between the current multiple of 10 (y) and the purchaseAmount. This is done using the absolute difference function abs(y - purchaseAmount).

  4. Compare this temporary difference t with the smallest difference found so far (diff). If t is less than diff, it means we have found a closer multiple of 10 to purchaseAmount. Update diff to this new minimum difference and x to the current multiple of 10 (y).

  5. After the loop ends, x holds the value of the nearest (largest in the case of a tie) multiple of 10 to purchaseAmount. The final account balance is calculated by subtracting x from the initial balance of $100.

  6. Return the final account balance.

The algorithm uses a for-loop to execute the steps mentioned above. The tuple unpacking in if (t := abs(y - purchaseAmount)) is a Python 3.8 feature called the "walrus operator" (:=), which assigns values to variables as part of a larger expression.

Here, abs(y - purchaseAmount) is simultaneously assigned to t and then compared against diff. This helps in writing more compact and readable code. No additional data structures are needed since the problem can be solved by simply tracking the difference and the corresponding multiple of 10.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Example Walkthrough

Let's assume purchaseAmount is 74.Thegoalistoroundthisamounttothenearestmultipleof10,whichcanbeeither74. The goal is to round this amount to the nearest multiple of 10, which can be either 70 or 80,andthensubtractitfromtheinitialbalanceof80, and then subtract it from the initial balance of 100.

We start with the initial diff set to a high value, which here is 100. The roundedAmount (x) is what we're looking to find.

  1. We'll start checking from 100downwardsinstepsof10(100 downwards in steps of 10 (100, 90,90, 80, and so on) until we reach 0. These represent potential roundedAmount values.

  2. When we reach $80 (y = 80), we calculate the difference: t = abs(y - purchaseAmount) = abs(80 - 74) = 6.

    Since 6 is less than our initial diff (100), we update diff to 6 and x to 80.

  3. Continuing the iteration, we check the next multiple of 10, which is $70: t = abs(y - purchaseAmount) = abs(70 - 74) = 4.

    Now 4 is less than our current diff (6), so we update diff to 4 and x to 70.

  4. We proceed with the loop, but since all subsequent multiples of 10 will increase the difference (moving further away from $74), there will be no updates to diff or x.

  5. After completing the iterations, the nearest multiple of 10 is 70(whichisx),andthedifferencewevesettledonis70 (which is `x`), and the difference we've settled on is 4 (which is the final diff).

  6. The final account balance can now be calculated by subtracting x from the initial balance: finalBalance = initialBalance - x = 100 - 70 = 30.

Therefore, after the purchase with the purchaseAmount of 74thatgetsroundedto74 that gets rounded to 70, the final account balance would be $30.

Solution Implementation

1class Solution:
2    def accountBalanceAfterPurchase(self, purchase_amount: int) -> int:
3        # Initialize the closest difference to the maximum possible value (100)
4        # and the closest rounded amount to 0
5        closest_difference = 100
6        closest_rounded_amount = 0
7
8        # Iterate backward from 100 to 0 with a step of -10
9        for rounded_amount in range(100, -1, -10):
10            # Calculate the absolute difference between the purchase amount and
11            # the current rounded amount
12            current_difference = abs(rounded_amount - purchase_amount)
13
14            # Determine if the current difference is smaller than the closest
15            # difference we have found so far
16            if current_difference < closest_difference:
17                # If so, update the closest difference and the corresponding
18                # rounded amount
19                closest_difference = current_difference
20                closest_rounded_amount = rounded_amount
21
22        # Return the adjusted account balance after the purchase, which is
23        # 100 subtracted by the closest rounded amount
24        return 100 - closest_rounded_amount
25
1class Solution {
2
3    // This method calculates the account balance after a purchase with an initial balance of 100.
4    // It finds the closest decrement of 10 from the purchase amount and subtracts it from 100.
5    public int accountBalanceAfterPurchase(int purchaseAmount) {
6        // Initialize the minimum difference found to 100 (which can be the max difference as per the logic below)
7        int minDifference = 100;
8        // This will hold the closest matching decrement value
9        int closestMatch = 0;
10      
11        // Loop through decrements of 10 starting from 100 to 0
12        for (int currentDecrement = 100; currentDecrement >= 0; currentDecrement -= 10) {
13            // Calculate the absolute difference between the purchase amount and the current decrement
14            int currentDifference = Math.abs(currentDecrement - purchaseAmount);
15            // If the current difference is smaller than any previously recorded difference
16            if (currentDifference < minDifference) {
17                // Update the minimum difference
18                minDifference = currentDifference;
19                // Update the closest matching decrement which we might subtract from the balance
20                closestMatch = currentDecrement;
21            }
22        }
23        // Return the balance after subtracting the closest matching decrement
24        return 100 - closestMatch;
25    }
26}
27
1class Solution {
2public:
3    // Function to calculate account balance after a purchase is made.
4    // The function finds the nearest multiple of 10 to the purchase amount
5    // and subtracts it from the starting balance, which is assumed to be 100.
6    int accountBalanceAfterPurchase(int purchaseAmount) {
7        int minDifference = 100;    // Initialize the minimum difference to the highest value possible (100).
8        int closestMultiple = 0;    // This will hold the closest multiple of 10 to purchaseAmount.
9
10        // Iterate over possible multiples of 10, from 100 down to 0, decremented by 10.
11        for (int currentMultiple = 100; currentMultiple >= 0; currentMultiple -= 10) {
12            // Calculate the absolute difference between currentMultiple and purchaseAmount.
13            int currentDifference = abs(currentMultiple - purchaseAmount);
14
15            // If the current difference is less than the minimum difference found so far,
16            // update minDifference and closestMultiple.
17            if (currentDifference < minDifference) {
18                minDifference = currentDifference;
19                closestMultiple = currentMultiple;
20            }
21        }
22
23        // The new balance is the original balance (100) minus the closest multiple of 10 to purchaseAmount.
24        return 100 - closestMultiple;
25    }
26};
27
1/**
2 * Calculates the new account balance after a purchase is made.
3 * This function assumes the account starts with a balance of 100,
4 * and subtracts the nearest multiple of 10 to the purchase amount from it.
5 * 
6 * @param {number} purchaseAmount - The amount of the purchase made.
7 * @return {number} The account balance after the purchase.
8 */
9function accountBalanceAfterPurchase(purchaseAmount: number): number {
10    // Initialize the closest difference to the purchase amount and its multiple of 10.
11    let closestDifference: number = 100;
12    let closestMultiple: number = 0;
13
14    // Iterate through multiples of 10 from 100 down to 0.
15    for (let multiple = 100; multiple >= 0; multiple -= 10) {
16        // Calculate the absolute difference from the current multiple to the purchase amount.
17        const currentDifference: number = Math.abs(multiple - purchaseAmount);
18
19        // If the current difference is smaller than the closest one, update the closest values.
20        if (currentDifference < closestDifference) {
21            closestDifference = currentDifference;
22            closestMultiple = multiple;
23        }
24    }
25
26    // Return the difference between the initial balance and the closest multiple of 10 found.
27    return 100 - closestMultiple;
28}
29

Time and Space Complexity

The time complexity of the given code snippet is O(1) because the code contains a single for-loop that always iterates a constant number of times (10 iterations exactly, from 100 down to 0 in steps of 10).

The space complexity of the code is also O(1) because the code only uses a fixed amount of additional space regardless of the input size. The variables diff, x, and t are the only extra variables that are used, and they do not depend on the size of the input.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄