Programming Geek
Rated 4.7/5 based on 1446 reviews

MockVita 2018 Problem: Largest Integer

Largest Integer

Problem Description

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.

to find the largest integer that could be formed using the above process.

Constraints
1 <= M <= 20, 1 <= N <= 50

Input Format
First line contains M,N two comma separated integers giving the number of chutes and the number of digits in each chute
The next M lines each contain N comma separated digits, giving the digits from top to bottom in each of the chutes.

Output
One line containing the largest integer that could be formed.

Test Case
TestCase 1 4,4 7,5,5,2 3,6,1,7 8,7,0,4 8,7,3,9 9743782557163078 TestCase 2 2,3 1,2,3 2,4,6 643221


     Explanation

Example 1
Input
2,3
1,2,3
2,4,6
Output
643221
Explanation
M is 2 and N is 3 (there are 2 chutes with 3 digits in each). The chutes look like this

The largest integer that can be formed is 643221
Example 2
Input
4,4
7,5,5,2
3,6,1,7
8,7,0,4
8,7,3,9
Output
9743782557163078
Explanation
M is 4 and N is 4. The chutes look like this

The largest integer that can be formed is 9743782557163078, and this is the output.