Ancient Tome Organizer — Problem Statement & Solution Guide

GreedyMediumMixed

TimeO(n log n)

SpaceO(1) additional (or O(n) if the language’s sort isn’t in‑place)

Problem Description

Ancient Tome Organizer

You are tasked with arranging a collection of ancient tomes on a single shelf. Each tome has a known page count, and the shelf can hold at most a given number of pages. You may reorder the tomes arbitrarily before placing them on the shelf. Your goal is to determine the maximum number of tomes that can be placed on the shelf without exceeding its page capacity.

Input format:

- The first line contains two integers, N (the number of tomes) and C (the shelf capacity in pages).

- The second line contains N integers, where the i-th integer represents the page count of the i-th tome.

Output format:

- Output a single integer: the maximum number of tomes that can be placed on the shelf.

The problem reduces to selecting as many tomes as possible such that the sum of their page counts does not exceed C. Since all tomes are identical in value except for their page counts, the optimal strategy is to choose the smallest tomes first.

Examples

Example 1

Input:

5 10

2 3 5 4 1

Output:

Explanation:

Sorting the page counts gives [1,2,3,4,5]. Adding them sequentially: 1+2+3+4 = 10, which fits exactly. Adding the next tome would exceed the capacity, so the maximum number of tomes is 4.

Example 2

Input:

3 5

6 7 8

Output:

Explanation:

All tomes individually exceed the shelf capacity, so none can be placed.

Example 3

Input:

6 15

5 5 5 5 5 5

Output:

Explanation:

The smallest three tomes sum to 15, which fits. Adding a fourth tome would exceed the capacity.

Example 4

Input:

4 100

20 30 40 50

Output:

Explanation:

The sorted list is [20,30,40,50]. The first three sum to 90, which is within the capacity. Adding the fourth tome would exceed the capacity.

Constraints

- 1 ≤ N ≤ 100000

- 1 ≤ C ≤ 10^14

- 1 ≤ page count of each tome ≤ 10^9

DSA Pattern Breakdown

"Ancient Tome Organizer"

medium

WHY DOES IT MATTER?

The greedy‑by‑smallest pattern is a cornerstone for optimization problems where items share identical profit. Recognizing this pattern lets you replace costly combinatorial searches with simple sorts, dramatically improving scalability.

OPTIMIZATION CHALLENGE

The key insight is the exchange argument that proves any optimal solution can be transformed into the sorted‑prefix solution without losing feasibility, allowing the reduction from exponential subset enumeration to a single sort plus linear scan.

REAL-WORLD CONNECTION

Think of loading a delivery truck: you want to load as many packages as possible without exceeding weight limits. Loading the lightest packages first ensures you maximize the count, mirroring the tome‑organizer scenario.

During an interview, sort the array first, then keep a running sum; break as soon as the sum exceeds the capacity. This early‑exit pattern saves time and clearly demonstrates your understanding of greedy optimality.

COMPLEXITY AT A GLANCE

⏱ Time:O(n log n)

💾 Space:O(1) additional (or O(n) if the language’s sort isn’t in‑place)

Core Theory — Why This Approach?

The problem reduces to selecting the largest possible subset of items whose total weight (page count) does not exceed a given capacity. This is a classic instance of the *knapsack* problem where each item has equal value (one tome) and we only care about maximizing the count, not the total pages. A naive exhaustive search would try all subsets, leading to exponential time, which is infeasible for typical input sizes (n up to 10^5). The optimal paradigm leverages the greedy choice property: when all items have the same value, picking the lightest items first always yields an optimal solution because any heavier item can be swapped with a lighter one without decreasing the count and without violating the capacity constraint. Sorting the page counts in non‑decreasing order and then iterating until the cumulative sum exceeds the shelf limit gives the maximum number of tomes in O(n log n) time.

Why the greedy approach works can be proven by exchange argument: assume an optimal solution that does not contain the smallest remaining tome; replace the heaviest tome in that solution with the smaller one – the total pages can only decrease, preserving feasibility while keeping the count unchanged. Repeating this exchange leads to the sorted‑prefix solution, confirming optimality. Thus the problem is solved by a single sort followed by a linear scan.

Interview Questions on This Problem

Q1How would you modify the solution if each tome also had a monetary value and you needed to maximize total value while staying within the page limit?

The problem becomes the classic 0/1 knapsack where items have weight (pages) and value (money). The greedy by weight no longer guarantees optimality; you would need dynamic programming O(n·capacity) or meet‑in‑the‑middle for large capacities, or use a value‑based DP if total value is smaller.

Q2Can you solve the original problem in O(n) time without sorting? Under what constraints?

If the page counts are bounded by a small constant (e.g., ≤10^3), you can use counting sort or a frequency array to achieve linear time. Otherwise, sorting is required for arbitrary values.

Q3Explain how you would handle the case where the shelf can hold multiple rows, each with its own page capacity, and you must maximize the total number of tomes placed across all rows.

This becomes a bin‑packing variant. A common heuristic is First‑Fit‑Decreasing: sort tomes descending and place each in the first row that fits. It does not guarantee optimality but runs in O(n log n). Exact solution requires exponential search or integer programming.

Examples

Example 1

Input

5 10
2 3 5 4 1

Output

Explanation: Sorted pages: [1,2,3,4,5]. Cumulative sums: 1,3,6,10,15. The first four sums (10) are ≤10; the fifth sum (15) exceeds 10. Thus, 4 tomes fit.

Example 2

Input

3 5
6 7 8

Output

Explanation: Each tome individually exceeds the capacity of 5, so no tome can be placed.

Example 3

Input

6 15
5 5 5 5 5 5

Output

Explanation: Sorted pages: [5,5,5,5,5,5]. Cumulative sums: 5,10,15,20,... The first three sums (15) are ≤15; the fourth sum (20) exceeds 15. Thus, 3 tomes fit.

Example 4

Input

4 100
20 30 40 50

Output

Explanation: Sorted pages: [20,30,40,50]. Cumulative sums: 20,50,90,140. The first three sums (90) are ≤100; the fourth sum (140) exceeds 100. Thus, 3 tomes fit.

Constraints

1 <= N <= 100000
1 <= C <= 10^14
1 <= page count of each tome <= 10^9

Optimal Approach & Strategy

Sort the page counts ascending and greedily take tomes from the smallest until the cumulative pages exceed the limit.

Brute Force Approach

Enumerate every subset of tomes, compute its total pages, and keep the largest subset whose sum ≤ capacity.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n log n)

'use strict';
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = data[idx++];
const limit = data[idx++];
const arr = data.slice(idx, idx + n);
arr.sort((a, b) => a - b);
let sum = 0;
let cnt = 0;
for (const x of arr) {
    if (sum + x > limit) break;
    sum += x;
    cnt++;
}
console.log(cnt.toString());

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long limit;
    if (!(cin >> n >> limit)) return 0;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a.begin(), a.end());
    long long sum = 0;
    int cnt = 0;
    for (long long x : a) {
        if (sum + x > limit) break;
        sum += x;
        ++cnt;
    }
    cout << cnt << '\n';
    return 0;
}

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        long limit = Long.parseLong(st.nextToken());
        long[] arr = new long[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(arr);
        long sum = 0;
        int cnt = 0;
        for (long x : arr) {
            if (sum + x > limit) break;
            sum += x;
            cnt++;
        }
        System.out.println(cnt);
    }
}

import sys

def main():
    tokens = sys.stdin.read().strip().split()
    if not tokens:
        return
    it = iter(tokens)
    n = int(next(it))
    limit = int(next(it))
    pages = [int(next(it)) for _ in range(n)]
    pages.sort()
    total = 0
    cnt = 0
    for p in pages:
        if total + p > limit:
            break
        total += p
        cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

'use strict';
const fs = require('fs');
const data = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number);
let idx = 0;
const n = data[idx++];
const limit = data[idx++];
const arr = data.slice(idx, idx + n);
arr.sort((a, b) => a - b);
let sum = 0;
let cnt = 0;
for (const x of arr) {
    if (sum + x > limit) break;
    sum += x;
    cnt++;
}
console.log(cnt.toString());

Asked in Top Tech Interviews

uncategorizedmediumgeneric

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Ancient Tome Organizer Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Greedy

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Ancient Tome Organizer — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor