SDE - 1

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.

Ninja got a very long summer vacation. Being very bored and tired about it, he indulges himself in solving some puzzles.

He encountered a problem in which he was given two arrays of integers of length ‘N’ and ‘M’ respectively and he had to find the longest common prime subsequence.

Ninja wants help in solving the problem as he is not getting the approach so he approaches you as he knows that you are very good at building logics. Help Ninja!

Note:

A subsequence is a sequence that can be derived from another sequence by zero or more elements, without changing the order of the remaining elements.

You have given an integer array/list ‘arr’ of size ‘N’. You have to split the array into the maximum number of subarrays such that the first and last occurrence of every distinct element lies in a single subarray.

You are required to return the number of maximum subarrays in which the array can be split.

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

For Example:

Let an array ‘arr’ = [2,2,1,1].

In this example, the array can be split like this [2,2], [1,1] in this 
case the first and last occurrence of 2 lies in a first subarray and 
similarly first and the last occurrence of 1 lies in a second 
subarray. 

You have given an integer array ‘arr’ size ‘N’. You have to split the array into ‘K’ consecutive non-overlapping subarrays of length ‘M’ such that every subarray contains a single distinct element.

You are required to check if it is possible to split the array with the above condition and print the answer in the binary format 1 if it is possible or 0 if it is not possible to split the array.

For Example:

Input:
N = 4 
M = 1 
K = 3
A[] = {5, 4, 1, 1}

Output 
1

The given array can be split like this [5], [4], [1] there are three consecutive non-overlapping subarrays. 

On a scale of 1 to 10 how would you rate yourself as a leader? 

What makes you angry?