Last Updated: 15 Jan, 2021

Maximum Number

Easy

Asked in companies

Solve now

Problem statement

You are given an array of N elements. This array represents the digits of a number. In an operation, you can swap the value at any two indices. Your task is to find the maximum number by using operation at most once.

For Example :

Input array [1,3,2,7] so basically this array represents the number 1327.
All the possible combinations are :
1. [3 1 2 7] get by swapping indices 1 and 2.
2. [2 3 1 7] get by swapping indices 1 and 3.
3. [7 3 2 1] get by swapping indices 1 and 4.
4. [1 2 3 7] get by swapping indices  2 and 3.
5. [1 7 2 3] get by swapping indices 2 and 4.
6. [1 3 7 2] get by swapping indices 3 and 4.
Out of all the possible combinations, 3 give the maximum number as 7321, so we will return [7 3 2 1].

Note :

The input may have 0 before the most significant digit. e.g. [0,3,5,7] is a valid input and this represents number 357.

Input Format :

The first line of input contains a single integer T, representing the number of test cases. Then the T test cases follow.

The first line of each test case contains a number N denoting the size of the array.

The second line contains N space-separated distinct integers a1, a2, ..., aN — the array elements.

Output Format :

For each test case, print the output array where elements are separated by space.

The output of every test case will be printed in a separate line.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1<= T <=100
2 <= N <= 10^4
0 <= A[i] <= 9

Where 'A[i]' denotes the 'ith' element of the array.

Time limit: 1 sec

Solve now

Approaches

01 Approach

The idea is to generate all the possible numbers by trying all the possible combinations of indices. We will run two nested loops to generate all numbers and inside the inner loop with we will have to compare the array, we get after swapping with the maximum number we get till this step.

Let’s say we have a given array ARR.
Let’s take an integer array of size N say MAX initialized to ARR, MAX[N] = ARR.
Iterate over ARR[i] for each 0<= i < N and do:
1. Iterate over ARR[j] for each 0<= j < N and do:
2. Swap ARR[i] and ARR[j]
3. Compare MAX and ARR
  1. If MAX is greater than ARR set MAX to ARR.
4. Swap ARR[i] and ARR[j] to get the original array.
Return MAX.

Solve now

02 Approach

The idea is to find the rightmost indices of all the digits and we can do this in a single scan of the array. Then we will scan from left to right and for each index, we will check the indices of all digits greater than the current digit as we find out in the earlier step, and if we find then we will swap with the maximum digit available.

Let’s say we have a given array ARR.
Let’s take an integer array of size 10 say DIGITS initialized to 0.
Iterate over ARR[i] for each 0<= i < N and do:
1. DIGITS [ ARR[i] ] =i.
Iterate over ARR[i] for each 0<= i < N and do:
1. Iterate over DIGITS[j] for each 9>= j > ARR[i] and do:
2. If DIGITS[j] is greater than i.
Swap ARR[i] with ARR[ DIGITS[j] ] and return ARR.
Return ARR.

Solve now