Morty and his array

Hard
0/120
profile
Contributed by
9 upvotes
Asked in company
Adobe

Problem statement

Rick gave Morty an array 'Arr' of length ‘N’ and an integer ‘K’ and asked him to find the minimum possible cost to split the array into non-empty sub-arrays such that the following conditions can be achieved:

1. If every element in the sub-array is unique, then the cost of the sub-array is K.

2. If some elements are not unique, then the cost will be ‘K’ + the number of elements that are not unique i.e. frequencies of repeated elements.

An array ‘C’ is a sub-array of array ‘D’ if ‘C’ can be obtained from ‘D’ by deleting several elements from the beginning and several elements from the end.

Example : let ‘arr’ = [1,0,0] then the possible sub-arrays of ‘arr’ will be- {1}, {0}, {0}, {1,0}, {0,0}, {1,0,0}.

For Example 
Let Arr[] = {1, 1, 1, 4, 1, 2, 4}, K=2

The given array can be split into two sub-arrays {1, 1, 1, 4}, {1, 2, 4}. The total cost will be for the first sub-array - 2+ 3(frequency of 1 is 3 in the first sub-array) + for the second sub-array - 2, Hence total cost is 7.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.

The first line of each test case contains two integers, ‘N’ and ‘K’, denoting the length of the array and cost of each subarray, respectively.

The second line of the test case contains an array ‘Arr’ of ‘N’ integers.
Output Format : 
For each test case, print a single integer ‘ANS’ representing the minimum cost of splitting the array. 

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.
Constraints : 
1 <= T <= 10
1 <= N <= 500
1 <= K <= 500
1 <= Arr[i] <= 500

Time limit: 1 sec
Sample Input 1 :
2
7 2
1 1 1 4 1 2 4
5 3
1 2 3 3 5
Sample Output 1 :
7
5
Explanation For Sample Output 1 :
For the first test case, we can divide the array into two subarrays {1, 1, 1, 4} and {1, 2, 4} so the answer will be 7.

For the second test case, we have to keep the whole array to minimize the cost, so the answer will be the cost of 1 subarray i.e. 3, plus the frequency of non-unique numbers i.e. 2.
Sample Input 2 :
2
11 5
1 5 1 1 1 1 7 5 1 2 4
7 3
1 2 3 2 1 2 3
Sample Output 2 :
13
8
Hint

Find the cost for every possible split.

Approaches (3)
Naive Approach

The basic idea is to generate all the possible subarrays and find the cost of every possible split and then returning the minimum cost from all of them. 

The steps are as follows:

 

  1. Recursively go through every possible split of the array Arr.
  2. Store all the subarrays of one split into a vector<vector<int>> split.
  3. Now go through every subarray of that split and find the frequency of every element in that subarray and calculate the cost of that split.
  4. Return the minimum value from all of the splits.
Time Complexity

O(M * N * 2^N), where ‘N’ is the length of the given array and M is the maximum value of the array.

 

Since we are finding all the possible splits of the array which is a 2^N task and then for every split we are finding the cost of every subarray which can be done in N*M. so the total complexity is O(M * N * 2^N)

Space Complexity

O(N^2), where ‘N’ is the length of the given array.

 

Since we are storing every subarray so the maximum number of splits in an array can be N and the maximum element in each subarray can also be N, so the total space required is O(N^2).

Code Solution
(100% EXP penalty)
Morty and his array
Full screen
Console