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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

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:

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.
Iterate backward from the initial balance of $100 to 0 in decrements of 10. Each of these numbers represents a potential roundedAmount.
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).
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).
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.
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:

Example Walkthrough

Let's assume purchaseAmount is $74. The goal is to round this amount to the nearest multiple of 10, which can be either$ 70 or $80, 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.

We'll start checking from $100 downwards in steps of 10 ($ 100, $90,$ 80, and so on) until we reach 0. These represent potential roundedAmount values.
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.
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.
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.
After completing the iterations, the nearest multiple of 10 is $70 (which is `x`), and the difference we've settled on is$ 4 (which is the final diff).
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 $74 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

Not Sure What to Study? Take the 2-min Quiz：

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:

Which of these properties could exist for a graph but not a tree?

Contain cyclesThere are multiple ways to traverseConnectedHas no cycle

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2806. Account Balance After Rounded Purchase

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Recommended Readings