Beauty Shuffle

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
4 upvotes
Asked in companies
Dell TechnologiesSAP Labs

Problem statement

You are given two arrays ‘arr1’ and ‘arr2’ of the same length. The beauty of ‘arr1’ is defined as the count of the total number of indices ‘i’ such that ‘arr1[i]’ > ‘arr2[i]’.

In order to maximize the beauty of ‘arr1’ you can reorder its element in any way you want i.e you can swap any possible pair of indexes in ‘arr1’ any number of times.

You need to return any array that is made from ‘arr1’ after reordering its element such that the beauty of the returned array is maximum possible.

Note :

There can be more than one possible array with maximum beauty. In that case, you can return any of them.
Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains an integer ‘N’ denoting the size of arrays.

The second line of each test case contains ‘N’ space-separated integers, representing the elements of the first array, ‘arr1’.

The last line of the test cases contains ‘N’ space-separated integers, representing the elements of the second array, ‘arr2’.

Output Format :

For each test case, the output will be “1” if you have returned the correct answer, else it will be “0”.

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

Note :

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 5
1 <= N <= 5000
1 <= arr1[i], arr2[i] <= 10 ^ 9

Time Limit: 1sec

Sample Input 1 :

2
3
5 7 13
1 10 6
4
7 22 5 32
13 25 35 10

Sample Output 1 :

1
1

Explanation Of Sample Input 1 :

Test case 1:
For the first test case given ‘arr1’ has beauty equal to 2 as ‘arr1[i]’ > ‘arr2[i]’ for ‘i’ = 0, 2. But after swapping index 2 with index 1 we get ‘arr1’ = [ 5, 13, 7 ] with the beauty = 3, as now ‘arr1[i]’ > ‘arr2[i]’ for i = 0, 1, 2. And 3 is the maximum possible beauty.

Test case 2:
For the second test case, given ‘arr1’ has beauty equal to 1. But after reordering its elements we get ‘arr1’ = [22, 32, 5, 7 ] with beauty = 2. ‘arr1’ = [ 22 , 32, 7, 5] is also a valid answer as its beauty is also 2, which is maximum possible.

Sample Input 2 :

1
1
6
2

Sample Output 2 :

1

Explanation of Sample Input 2 :

Test case 1:
There is only one element, we cannot reorder its elements, so the beauty of ‘arr1’ remains the same i.e 1.
Hint

Consider all possibilities.

Approaches (5)
Brute Force Approach

Check all the possible permutations of ‘arr1’ and return the one with maximum beauty.

 

Algorithm:

 

  • Let the given array be ‘arr1’ and ‘arr2’.
  • Sort the ‘arr1’
  • Declare a variable say ‘maxBeauty’.
  • Declare a 2-D array say ‘allPermutation’ to store all permutations of ‘arr1’.
  • Run a loop for each permutations of ‘arr1’
    • Declare a variable ‘temp’
    • Run a loop through ‘arr1’
      • If ‘arr1[i]’ > ‘arr2[i]’
        • Increment temp by 1 i.e. do ‘temp’ += 1
    • Update ‘maxBeauty’ i.e. do ‘maxBeauty’ := max( ‘maxBeauty’, ‘temp’)
    • Add ‘arr1’ to ‘allPermutation’
    • Update ‘arr1’ to next permutations of ‘arr1’.
  • Run a loop through each array ‘arr1’ in ‘allPermutation’
    • Declare a variable ‘temp’
    • Run a loop from i = 0 to length ‘arr1’ - 1
      • If ‘arr1[i]’ > ‘arr2[i]’
        • Increment temp by 1 i.e. do ‘temp’ += 1.
    • If ‘temp’ == ‘maxBeauty’
      • Return ‘arr1’
Time Complexity

O(N! * N), where ‘N’ is the size of the given array.

 

Here we are generating all permutations of given ‘arr1’, In the worst case a total number of all permutations array will be ‘N!’. We are iterating over each permutation and then calculating beauty that takes O(N) time for each array. Also generating the next permutation takes O(N) time. Hence the overall time complexity will be O(N! * N )

Space Complexity

O(N! * N), where ‘N’ is the size of the given array. 

 

In the worst case, We are using a 2-D array of size ‘N! * N’ to store all the permutations of array ‘arr1’. Hence the overall space complexity will be O(N! * N).

Code Solution
(100% EXP penalty)
Beauty Shuffle
Full screen
Console