# CVCE003 - Editorial

Largest Number - Practice

Author: Arvind
Tester: Chitturi Sai Suman
Editorialist: Muneeb Hussaini

Easy

# PREREQUISITES:

Comparator based Sorting

# PROBLEM:

Arvind loves playing with Numbers. He has a sequence [A_1,A_2,\dots,A_N] of N integers. He wants to reduce the length of the sequence to 1. To do that, he performs exactly Nā1 moves, where a move is defined as follows.

• Pick two Integers A_i and A_j, i \ne j, remove them from the sequence and append the result obtained by concatenating the Integers to the sequence.

He wonders what could be the Largest Integer he can obtain at the end. Can you help him in finding it?

# QUICK EXPLANATION:

The problem can be easily solved by sorting the elements of the array based on a Comparator. Refer to the explanation for Comparator based Sorting.

Note: Since the numbers are very large (10^{10^3}), we read them into strings.

# EXPLANATION:

Given an array A containing N integers, we need to output the largest number that can be obtained by concatenating these N integers.

This problem can be solved using Greedy Approach. Consider the array of Integers [a_1, a_2, a_3, \dots, a_n]. We sort the sequence by comparing two elements at a time.
Say (S_1,\ S_2) belong to the sequence. The two possible ways of ordering them are:

1. (S_1,\ S_2) => (S_1 comes before S_2) after rearranging.
2. (S_2,\ S_1) => (S_2 comes before S_1) after rearranging.

### Which ordering is optimal?

We can decide this by comparing them the following way:
If (S_1 + S_2) \gt (S_2 + S_1), then the ordering shall be (S_1,\ S_2). Otherwise, the ordering shall be (S_2,\ S_1).

We can prove that the ordering of elements in this way will always produce the largest Number.

# SOLUTIONS:

Setter's Solution
``````def largest(x) :
x = [str(i) for i in x]
for i in range(len(x)):
for j in range(i + 1, len(x)):
if (x[i] + x[j] < x[j] + x[i]):
x[i], x[j] = x[j], x[i]
return ("".join(x))
lis=[]
for i in range((int(input()))):
n=int(input())
x=[int(x) for x in input().split()]
lis.append(largest(x))
for i in range(len(lis)):
print(int(lis[i]))
``````
Tester's Solution
``````"""
Author: Chitturi Sai Suman
Created: 2021-05-17 19:26:35
Contest: Code with VCE
"""
## 57:69:74:68:20:4C:4F:56:45
##	  _____   _    _   __    __     ____     __    _
##	 / ____| | |  | | |  \  /  |   /    \   |  \  | |
##	 | |___  | |  | | |   \/   |  /   _  \  | . \ | |
##	 \____ \ | |  | | | |\__/| | |   /_\  | | |\ \| |
##	 ____| | | \__/ | | |    | | |   __   | | | \ ` |
##	 |_____/ \______/ |_|    |_| |__|  |__| |_|  \__|
##

from functools      import cmp_to_key, reduce
from fractions      import Fraction
from statistics     import mean, median, mode
from collections    import deque, OrderedDict, defaultdict
from re             import compile, findall, escape, search, match
from sys            import stdin, stdout, stderr, setrecursionlimit
from math           import pi, sqrt, gcd, ceil, floor, log2, log10, factorial
from random         import choice, getrandbits, randint, random, randrange, shuffle
from itertools      import combinations, combinations_with_replacement, permutations
from collections    import Counter, namedtuple, ChainMap, UserDict, UserList, UserString
from math           import cos, acos, tan, atan, atan2, sin, asin, radians, degrees, hypot
from bisect         import insort, insort_left, insort_right, bisect_left, bisect_right, bisect
from heapq          import heapify, heappop, heappush, heappushpop, heapreplace, merge, nlargest, nsmallest
# from numpy import dot, trace, argmax, argmin, array, cumprod, cumsum, matmul

size = 2 * (10 ** 6 + 1)

# Scope for Global Variables
#
#

class String:
def __init__(self, string: str):
self.string = string
def __str__(self):
return self.string
# def __cmp__(self, other):
#     a = self.string + other.string
#     b = other.string + self.string
#     a = a + "0" * (max(len(a), len(b)) - len(a))
#     b = b + "0" * (max(len(a), len(b)) - len(b))
#     return int(a) < int(b)
def __lt__(self, other):
a = self.string + other.string
b = other.string + self.string
a = a + "0" * (max(len(a), len(b)) - len(a))
b = b + "0" * (max(len(a), len(b)) - len(b))
return int(a) > int(b)

def preCompute():
# Precompute some values here
#
pass

def solve():
# Solve Test Cases here
#
N = io.Int()
if N not in range(1, 201):
abort("Invalid value of N")
l = list(map(String, io.String().split()))
for i in l:
if int(str(i)) not in range(1, 10**(10**3) + 1):
abort("Invalid Range of Array Elements")
l.sort()
io.write(''.join([str(i) for i in l]))

def main():

testcases = 0

# testcases += 1

if testcases == 0:
testcases = io.Int()

if testcases not in range(1, 10**3 + 1):
abort("Invalid Test Cases")

preCompute()

for test in range(testcases):

# io.write("Case #%d: "%(test+1), end="")
# Use the following lines to write any logic if needed
#
#
solve()

class IO:
def input(self):
def String(self):
return self.input()
def StringList(self):
return list(map(str, self.input().split()))
def Int(self):
return int(self.input())
def Float(self):
return float(self.input())
def List(self):
return list(map(int, self.input().split()))
def Tuple(self):
return tuple(map(int, self.input().split()))
def debug(self, *obj, sep = " ", end = "\n"):
string = sep.join([str(item) for item in obj]) + end
stderr.write(string)
def write(self, *obj, sep = " ", end = '\n'):
string = sep.join([str(item) for item in obj]) + end
stdout.write(string)
def put(self, val: str):
stdout.write(val + '\n')
def yes(self):
self.write("yes")
def Yes(self):
self.write("Yes")
def YES(self):
self.write("YES")
def no(self):
self.write("no")
def No(self):
self.write("No")
def NO(self):
self.write("NO")

io = IO()
shit = 998244353
mod = 10 ** 9 + 7
hell = 10 ** 9 + 9
inf = 10 ** 18 + 3
lcm = lambda x, y: ((x * y) // gcd(x, y))
add = lambda x, y, p: (x % p + y % p + p) % p
sub = lambda x, y, p: ((x % p - y % p) + p) % p
mul = lambda x, y, p: ((x % p) * (y % p)) % p
inverse = lambda x, p: (pow(x, p - 2, p))
setBitCount = lambda x: bin(x).count("1")
sumOfDigits = lambda x: sum([int(i) for i in str(x)])

dc = [1, 0, 0, -1, -1, -1, 1, 1]
dr = [0, 1, -1, 0, -1, 1, -1, 1]

def abort(s):
raise AssertionError(s)

setrecursionlimit(size)

main()
``````
1 Like

@muneebhussaini When will problems be available to submit in practice?

Hey