Maximum Number

Easy
0/40
Average time to solve is 15m
profile
Contributed by
8 upvotes
Asked in companies
FacebookWalmartLrnEd

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.
Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1 :

4
4
3 2 1 4
3
0 9 7
7
3 2 1 1 2 3 9
5
9 8 1 8 7
Sample output 1 :
4 2 1 3
9 0 7
9 2 1 1 2 3 3
9 8 8 1 7
Explanation for sample output 1 :
(i) We can get the maximum number by swapping 1 and 4.
(ii) We can get the maximum number by swapping 1 and 2.
(iii) We can get the maximum number by swapping 1 and 7.
(iv) We can get the maximum number by swapping 3 and 4.
Sample input 2 :
4
5
9 8 7 6 5 
4
5 6 7 9
7
9 8 0 3 4 5 6
2
1 2
Sample output 2 :
9 8 7 6 5
9 6 7 5
9 8 6 3 4 5 0
2 1
Explanation for sample output 2 :
(i) We do not have a need to perform the operation as the number is already maximum.
(ii) We can get the maximum number by swapping 1 and 4.
(iii) We can get the maximum number by swapping 3 and 7.
(iv) We can get the maximum number by swapping 1 and 2.
Hint

Find out all the possible combinations by running two nested loops.

Approaches (2)
Brute Force

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.
Time Complexity

O(N^3) where N is the length of the array.

 

As we are iterating over an array of length N in two nested loops making time complexity as O(N^2) but along with this for each inner loop, we are comparing two arrays of size N thus multiplying time complexity by N.

So final time complexity is O(N^3).

Space Complexity

O(N).

 

As we are using an extra array of length N.

Code Solution
(100% EXP penalty)
Maximum Number
Full screen
Console