New ATM Design – TCS CodeVita

Design an ATM that dispenses maximum number of currency notes for student withdrawals with limited denominations and note counts.

Understand the Problem

Problem Statement

Automated Teller Machine (ATM) is an electronic device that enables people to withdraw cash from their bank account. Every ATM has a limit for number of currency notes (say N), it can give at a time.

A bank wants to design an ATM for school students. The unique feature of this ATM would be that it would always give maximum number of currency notes possible, to make the students happy. Available denomination of currency notes in the ATM are 100, 200, 500, 1000

Constraints

N < 100
Amount to withdraw is always in multiples of 100
Available notes for each denomination are non-negative integers
Maximum total notes that can be dispensed is N

Examples

Example 1

Input

Output

Explanation

We can use 7 notes of Rs 100 and 3 notes of Rs 200 to make 1300 (7×100 + 3×200 = 700 + 600 = 1300), which uses exactly 10 notes total. This is the maximum possible number of notes.

Example 2

Input

Output

Explanation

We can use 1 note of Rs 200, 1 note of Rs 500, and 1 note of Rs 1000 to make 1700 (1×200 + 1×500 + 1×1000 = 200 + 500 + 1000 = 1700), which uses exactly 3 notes total. This is the maximum possible number of notes given the constraints.

Solution

#include <stdio.h>

int main() {
    int n, amount, hundred, twohundred, fivehundred, thousand;
    int i, j, k, l;
    int max_notes = 0;
    
    // Read input
    scanf("%d", &n);
    scanf("%d", &amount);
    scanf("%d", &hundred);
    scanf("%d", &twohundred);
    scanf("%d", &fivehundred);
    scanf("%d", &thousand);
    
    // Try all possible combinations of notes
    for (i = 0; i <= hundred; i++) {
        for (j = 0; j <= twohundred; j++) {
            for (k = 0; k <= fivehundred; k++) {
                for (l = 0; l <= thousand; l++) {
                    // Check if this combination sums to the target amount
                    int total_value = i * 100 + j * 200 + k * 500 + l * 1000;
                    int total_notes = i + j + k + l;
                    
                    // Check if this is a valid solution
                    if (total_value == amount && total_notes <= n && total_notes > max_notes) {
                        max_notes = total_notes;
                    }
                }
            }
        }
    }
    
    printf("%d\n", max_notes);
    return 0;
}

Time:O(A × B × C × D) where A, B, C, D are the available counts of 100, 200, 500, 1000 rupee notes respectively

Space:O(1) - constant space used

Approach:

The C solution uses nested for loops to iterate through all possible combinations of available notes. For each combination, it calculates the total value and total number of notes. If the total value equals the target amount and the number of notes doesn't exceed the limit N, it updates the maximum count if this combination uses more notes than any previous valid combination.

The algorithm systematically checks every possible way to make the target amount using the available denominations, ensuring we find the combination that uses the maximum number of notes.

Visual Explanation

Loading diagram...

All Problems