Maximum Number

Posted: 15 Jan, 2021
Difficulty: Easy


Try Problem

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
Approach 1

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.

  1. Let’s say we have a given array ARR.
  2. Let’s take an integer array of size N say MAX initialized to ARR, MAX[N] = ARR.
  3. 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.
  4. Return MAX.
Try Problem