Morty and his array
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.

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

Question

Morty and his array

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.

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

Accepted Answer

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:

Recursively go through every possible split of the array Arr.
Store all the subarrays of one split into a vector> split.
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.
Return the minimum value from all of the splits.

Space Complexity: O(n^2)Explanation:

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).

Time Complexity: OtherExplanation:

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)

Accepted Answer

Bottom-Up Dynamic Programming

The basic idea of this approach is that we will compute the minimum cost of creating a subarray from 1 to i where i <= N and store the value of that in a dp array.

The steps are as follows:

Take an array dp of size ‘N’ and initialize every value of dp by INT_MAX except for dp[0]. As dp[0] will always be zero.
Now iterate through the array Arr from 1 to N(say iterator be i):
1. Take an array ‘F’ of size M where M is the maximum value present in the array Arr. In the array ‘F’ we will store the frequency of all the elements.
2. Iterate through the array Arr from i to N (say iterator be j):
  1. In every iteration increment the value of F[Arr[j]] by 1.
  2. Now take an int ‘Cost’ and find the total cost of constructing the subarray from i to j by iterating in the array F.
  3. Now, edit the value of dp[j]=min(dp[j], dp[i-1] + Cost + K);
Return the value of dp[n-1].

Space Complexity: OtherExplanation:

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

Since we are making an array dp and another array f for storing the frequency the overall space complexity is O(N + M).

Time Complexity: OtherExplanation:

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

Since We are iterating through the Array using a nested loop and for every inner loop, we are finding the frequency of every element present in the element so the total time complexity is O(M * N ^ 2).

Python (3.5)

'''
    Time Complexity : O(m*n^2)
    Space Complexity : O(m+n)
    
    Where, n is the size of the array and m is the maximum value in the array.
'''

def minCost(n, k, values):

    '''
            Compute the maximum value in the array 
            for determining the frequency array size.
    '''
    maxVal = values[0]
    
    for i in range(1, n):
        maxVal = max(maxVal, values[i])
        
    # Store all the previously computed values in a dp array.
    dp = [0 for i in range(n)]
    
    for i in range(n):        
        dp[i] = int(1e9)
        
    # Iterate in the array from 0 to n.
    for i in range(n):
        
        # Take an array freq to store the frequency.
        f = [0 for i in range(maxVal + 1)]
        
        # Iterate in the array from i to n.
        for j in range(i, n):
            
            # Update the frequency array.
            f[values[j]] += 1
            
            # Take a variable cost to store the cost due to non-unique elements.
            cost = 0
            
            '''
                    Iterate through frequency array to compute the additional 
                    cost i.e. due to non-unique elements.
            '''
            for t in range(maxVal + 1):
                if (f[t] > 1):
                    cost += f[t]
                    
            # Update the dp array.
            if i > 0:
                dp[j] = min(dp[i - 1] + cost + k, dp[j])
            else:
                dp[j] = min(cost + k, dp[j])
                 
    return dp[n - 1]

Java (SE 1.8)

/*

	Time Complexity : O(m*n^2)

	Space Complexity : O(m+n)

	

	Where, n is the size of the array and m is the maximum value in the array.

*/



import java.util.Arrays;



public class Solution {

	public static int minCost(int n, int k, int[] values) {

		

		/*

            Compute the maximum value in the array 

		    for determining the frequency array size.

        */

		int maxVal = values[0];



		for (int i = 1; i < n; i++) {

			maxVal = Math.max(maxVal, values[i]);

		}



		// Store all the previously computed values in a dp array.

		int dp[] = new int[n];



		// Initialize dp with maximum value.

		for (int i = 0; i < n; ++i) {

			dp[i] = (int) 1e9;

		}



		// Iterate in the array from 0 to n.

		for (int i = 0; i < n; ++i) {



			// Take an array freq to store the frequency.

			int f[] = new int[maxVal + 1];

			Arrays.fill(f, 0);



			// Iterate in the array from i to n.

			for (int j = i; j < n; ++j) {



				// Update the frequency array.

				f[values[j]]++;



				// Take a variable cost to store the cost due to non-unique elements.

				int cost = 0;



				/*

				    Iterate through frequency array to compute the additional 

				    cost i.e. due to non-unique elements.

				*/

				for (int t = 0; t <= maxVal; t++) {

					if (f[t] > 1)

						cost += f[t];

				}



				// Update the dp array.

				dp[j] = Math.min((i > 0 ? dp[i - 1] : 0) + cost + k, dp[j]);

			}

		}

		return dp[n - 1];

	}



}

C++ (g++ 5.4)

/*
    Time Complexity : O(m*n^2)
    Space Complexity : O(m+n)

    Where, n is the size of the array and m is the maximum value in the array.
*/

int minCost(int n, int k, vector &values) {

    // Compute the maximum value in the array for determining the frequency array size.
    int maxVal = values[0];
    for (int i = 1; i < n; i++) {
        maxVal = max(maxVal, values[i]);
    }

    // Store all the previously computed values in a dp array.
    int dp[n];

    // Initialize dp with maximum value.
    for (int i = 0; i < n; ++i) {
        dp[i] = 1e9;
    }

    // Iterate in the array from 0 to n.
    for (int i = 0; i < n; ++i) {

        // Take an array freq to store the frequency.
        int f[maxVal + 1] = {0};

        // Iterate in the array from i to n.
        for (int j = i; j < n; ++j) {

            // Update the frequency array.
            f[values[j]]++;

            // Take a variable cost to store the cost due to non-unique elements.
            int cost = 0;

            /*
                Iterate through frequency array to compute the additional cost
                i.e. due to non-unique elements.
            */
            for (int t = 0; t <= maxVal; t++) {
                if (f[t] > 1)
                    cost += f[t];
            }

            // Update the dp array.
            dp[j] = min((i > 0 ? dp[i - 1] : 0) + cost + k, dp[j]);
        }
    }
    return dp[n - 1];
}

Accepted Answer

Top-down Dynamic Programming

The basic idea of this approach is that we will compute the minimum cost of creating a subarray from 1 to i where i <= N but using a top-down dp such that we don’t have to calculate the frequency every time.

The steps are as follows:

Take an array dp of size ‘N’ and initialize every value of dp by -1.
Make another function ‘solve’ from start=0 to end=n by which we will find the value of dp[n-1] to dp[0].
1. Base case for this function will be if start==end then we have to return 0 or if dp[start]!=-1 then we will return dp[start].
2. Now if the above condition is not satisfied then we will iterate from start to end and for every iteration, we will increase the frequency of the current element ie frequency[arr[i]]++.
3. And we will set the dp at current element to be the minimum of dp at current element or the cost for splitting the array at that element + the cost of remaining element(i.e i to end) which can be written as dp[i]=min(dp[i], cost + solve(i+1));
Return the value of dp[0].

Space Complexity: OtherExplanation:

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

Since we are making an array dp and another array f for storing the frequency, the overall space complexity will be O(N + M)

Time Complexity: O(n^2)Explanation:

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

Since We are calling the solve function for every i from 1 to n so the total time complexity is O(N^2).

Python (3.5)

'''
    Time Complexity : O(n^2)
    Space Complexity : O(n+m)
    
    Where, n is the size of the array and m is the maximum value in the array.
'''

def minCost(n, k, values):

    dp = [-1 for i in range(n)]
    
    maxVal = values[0]
    
    for i in range(1, n):
        
        maxVal = max(maxVal, values[i])
        
    ans = solve(0, n, k, values, dp, maxVal)
    return k + ans

def solve(start, n, k, values, dp, maxVal):
    
    if start >= n:
        return 0
    
    ans = dp[start]
    
    if ans != -1:
        return ans
    
    ans = int(1e9)
    
    g = 0
    tmp = 0
    
    f = [0 for i in range(maxVal + 1)]
    
    for i in range(start, n):
        
        if (f[values[i]] == 1):
            tmp += 1
            
        f[values[i]] += 1
        
        if (f[values[i]] > 1):
            g += 1
            
        if i + 1 < n:
            ans = min(ans, g + tmp + k + solve(i + 1, n, k, values, dp, maxVal))
        else:
            ans = min(ans, g + tmp + solve(i + 1, n, k, values, dp, maxVal))
        dp[start]=ans
        
    return ans

Java (SE 1.8)


/*
	Time Complexity : O(n^2)
	Space Complexity : O(n+m)
	
	Where, n is the size of the array and m is the maximum value in the array.
*/

import java.util.Arrays;

public class Solution {

	public static int minCost(int N, int K, int[] values) {

		int dp[] = new int[N];
		for (int i = 0; i < N; i++) {
			dp[i] = -1;
		}
		int maxVal = values[0];
		for (int i = 1; i < N; i++) {
			maxVal = Math.max(maxVal, values[i]);
		}
		int ans = solve(0, N, K, values, dp, maxVal);
		return K + ans;
	}

	private static int solve(int start, int n, int k, int[] values, int[] dp, int maxVal) {
		if (start >= n)
			return 0;

		int ans = dp[start];

		if (ans != -1) {
			return ans;
		}
		ans = (int) 1e9;
		int g = 0, tmp = 0;
		int f[] = new int[maxVal + 1];
		Arrays.fill(f, 0);

		for (int i = start; i < n; i++) {
			if (f[values[i]] == 1)
				tmp++;

			f[values[i]]++;

			if (f[values[i]] > 1)
				g++;

			ans = Math.min(ans, g + tmp + ((i + 1 < n) ? k : 0) + solve(i + 1, n, k, values, dp, maxVal));
			dp[start]=ans;
		}

		return ans;

	}

}

C++ (g++ 5.4)

/*
    Time Complexity : O(n^2)
    Space Complexity : O(n+m)

    Where, n is the size of the array and m is the maximum value in the array.
*/

int solve(int start, int n, int k, vector &values, vector& dp, int maxVal) {

    // Base case, if start is greater than or equal to n return 0.
    if (start >= n)
        return 0;

    // Take a pointer ans for updating dp.
    int &ans = dp[start];

    if (ans != -1)
        return ans;

    ans = 1e9;
    int cost = 0;

    // Take an array freq to store the frequency.
    int freq[maxVal + 1] = {0};

    for (int i = start; i < n; i++) {

        // Increament the frequency of current element.
        freq[values[i]]++;

        // Increase the value of cost accordingly.
        if (freq[values[i]] == 2)
            cost += 2;
        else if (freq[values[i]] > 2)
            cost++;

        // Update the ans with the minimum value.
        ans = min(ans, cost + ((i + 1 < n) ? k : 0) + solve(i + 1, n, k, values, dp, maxVal));
    }

    return ans;
}


int minCost(int n, int k, vector &values) {

    // Take a vector dp.
    vector dp;
    dp.resize(n);

    // Initialise dp with -1.
    for (int i = 0; i < n; i++) {
        dp[i] = -1;
    }

    // Compute the maximum value in the array for determining the frequency array size.
    int maxVal = values[0];
    for (int i = 1; i < n; i++) {
        maxVal = max(maxVal, values[i]);
    }

    // Function Call.
    solve(0, n, k, values, dp, maxVal);
    return k + dp[0];
}

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

Input Format :

Output Format :

Note :

Constraints :

Top Adobe Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Adobe Software Developer