Largest Integer

Build the largest possible integer by drawing digits from vertical chutes, removing one digit at a time from any chute

Understand the Problem

Problem Statement

The casino has introduced a new game in which there are M vertical chutes each containing N single digit (possibly zero) numbers. You can choose any chute and draw the bottom number and when you do this all the other numbers in the chute descend by one slot. You need to build the largest integer using this process drawing all the numbers from the chutes.

For example, in the following example, we have three chutes of four numbers each and the largest number that can be drawn is 469534692781. Given the number of chutes and the numbers in each chute, write a program to find the largest integer that could be formed using the above process.

Constraints

1 ≤ M ≤ 20 (number of chutes)
1 ≤ N ≤ 50 (number of digits in each chute)
Each element in the chutes is a single digit (0-9)
All chutes have exactly N digits initially
The final result can be very large (up to M×N digits)

Examples

Example 1

Input

4,4
7,5,5,2
3,6,1,7
8,7,0,4
8,7,3,9

Output

9743782557163078

Explanation

Starting with the four chutes, the algorithm repeatedly selects the chute with the lexicographically largest remaining sequence. The first digit chosen is 9 from the last chute, then 7 from the third chute, then 4 from the third chute, and so on, resulting in the largest possible number 9743782557163078.

Example 2

Input

2,3
1,2,3
2,4,6

Output

Explanation

With two chutes [1,2,3] and [2,4,6], the algorithm chooses from the second chute first (6 > 3), then continues selecting the largest available leading digit at each step, resulting in 643221.

Solution

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    int r, c;
    scanf("%d,%d", &r, &c);
    
    char chutes[r][c];
    int positions[r]; // Track current bottom position for each chute
    
    // Read input
    for (int i = 0; i < r; i++) {
        positions[i] = c - 1;
        for (int j = 0; j < c; j++) {
            scanf(" %c", &chutes[i][j]);
            // Skip comma if not last element
            if (j < c - 1) {
                getchar(); // consume comma
            }
        }
    }
    
    // Build result
    for (int step = 0; step < r * c; step++) {
        int best_chute = -1;
        
        // Find chute with lexicographically largest remaining sequence
        for (int i = 0; i < r; i++) {
            if (positions[i] >= 0) {
                if (best_chute == -1) {
                    best_chute = i;
                } else {
                    // Compare sequences starting from current positions
                    int len1 = positions[best_chute] + 1;
                    int len2 = positions[i] + 1;
                    int min_len = (len1 < len2) ? len1 : len2;
                    
                    int found_diff = 0;
                    for (int k = 0; k < min_len; k++) {
                        if (chutes[i][positions[i] - k] != chutes[best_chute][positions[best_chute] - k]) {
                            if (chutes[i][positions[i] - k] > chutes[best_chute][positions[best_chute] - k]) {
                                best_chute = i;
                            }
                            found_diff = 1;
                            break;
                        }
                    }
                    
                    // If one sequence is prefix of another
                    if (!found_diff) {
                        if (len2 > len1) {
                            best_chute = i;
                        }
                    }
                }
            }
        }
        
        // Output the chosen digit and remove it
        printf("%c", chutes[best_chute][positions[best_chute]]);
        positions[best_chute]--;
    }
    
    return 0;
}

Time:O(M²×N²) - For each of M×N digits chosen, we compare up to M chutes, each comparison taking O(N) time

Space:O(M×N) - To store the chute data and track positions

Approach:

Algorithm:

Read M and N, then read M lines of N comma-separated digits
Store each chute as an array of characters
For each of the M×N steps:

Compare all non-empty chutes lexicographically from their current positions
Select the chute with the largest remaining sequence
Output its bottom digit and move up one position

Continue until all digits are consumed

Key Points:

Lexicographic comparison ensures we always pick the sequence that will yield the largest final number
The algorithm handles ties by looking ahead in the sequences
Time complexity: O(M²×N²) due to nested loops and string comparisons

Visual Explanation

Loading diagram...

All Problems