Java Coding Test Course, Calculating ATM Withdrawal Time

Problem Description

You are standing at an ATM machine. To withdraw money from the ATM, you must go through several processes.
The time it takes for each user to complete the withdrawal varies, and this time is how long it takes the user to perform operations at the ATM.
There are `n` users, and when the withdrawal times for each user are given, you need to write a function that calculates the total time it takes for all users to complete their withdrawals.

Input

  • First line: an integer `n` representing the number of users (1 ≤ n ≤ 1000)
  • Second line: `n` integers representing each user’s withdrawal time (1 ≤ time ≤ 10000)

Output

Output the total time taken for all users to complete their withdrawals.

Example Input

    5
    3 1 4 3 2

Example Output

    32

Problem Analysis

The total time taken for all users to finish their withdrawals at the ATM includes the waiting times of other users until each user completes their withdrawal.
That is, the time it takes for a specific user to finish their withdrawal is the sum of their withdrawal time and the times of all previous users who have completed their withdrawals.
This allows us to calculate the withdrawal completion time for all users.

Solution Approach

  1. Read the withdrawal times of users and store them in an array.
  2. Sort the input withdrawal times in ascending order.
  3. To calculate the total withdrawal time, compute the cumulative withdrawal completion time for each user.
  4. Sum the withdrawal completion times of all users to find the final total time.

Java Code Implementation

        import java.util.Arrays;
        import java.util.Scanner;

        public class ATMWithdrawal {
            public static void main(String[] args) {
                Scanner sc = new Scanner(System.in);
                
                // Input number of users
                int n = sc.nextInt();
                int[] times = new int[n];
                
                // Input withdrawal times
                for (int i = 0; i < n; i++) {
                    times[i] = sc.nextInt();
                }
                
                // Sort time array
                Arrays.sort(times);
                
                // Cumulative time variable
                int totalTime = 0;
                int accumulatedTime = 0;
                
                // Calculate cumulative time for each user
                for (int time : times) {
                    accumulatedTime += time; // Add current user's withdrawal time
                    totalTime += accumulatedTime; // Add accumulated time to total time
                }
                
                // Output result
                System.out.println(totalTime);
                
                sc.close();
            }
        }

Code Explanation

The above Java code is structured to solve the ATM withdrawal time calculation problem in the following way:

  1. First, a Scanner object is created to receive input, and the number of users n is read.
  2. Next, each user's withdrawal time is read and stored in the array times.
  3. Arrays.sort(times) sorts the withdrawal times in ascending order. This is important for minimizing each user's waiting time.
  4. Two variables are used to calculate the total withdrawal time: totalTime holds the total time taken for all users to complete their withdrawals, and accumulatedTime stores the current cumulative time.
  5. As we iterate through the withdrawal times, the current user's withdrawal time is added to the accumulated time, which is then added to the total time.
  6. Finally, the total withdrawal time is printed.

Time Complexity Analysis

The time complexity of this algorithm primarily depends on sorting the array of withdrawal times.
The average time complexity of the most common sorting algorithm, quicksort, is O(n log n), so the overall time complexity of the algorithm is O(n log n).
After that, the task of accumulating the withdrawal times is solved in a single iteration, resulting in O(n).
Therefore, the overall time complexity is O(n log n).

Summary

In this lecture, we practiced basic array sorting and cumulative summation through the ATM withdrawal time calculation problem.
Most algorithmic problems can be solved using basic data structures and algorithms.
When withdrawal times are optimized, waiting times reduce, and consequently, it will be more efficient for all users to use the ATM.
Problems like this can be used to practice various algorithms and data structures, which can help in job preparation.