Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Copy Arrays

Moderate

0/80

Average time to solve is 20m

Contributed by

0 upvote

Problem statement

Given an Array 'Arr' of size 'N', a subarray is called a copy array if it contains at least 1 element that occurs more than once.

Find the maximum number of copy arrays that can be formed by dividing the given array into its subarrays such that each element of the array belongs to exactly one subarray.

Example:

N = 4
Arr = [1, 1, 2, 2]

The array can be divided into 2 subarrays
The first one is [1, 1].
And the second one is [2, 2].

Detailed explanation ( Input/output format, Notes, Images )

Input Format :

The first line contains a single integer 'T' denoting the number of test cases, then the test case follows.

For each test case, the first line contains a single integer 'N', representing the number of elements in the Array 'Arr'.

The following line contains 'N' space-separated integers representing the array 'Arr'.

Output Format :

For each test case, return the maximum number of copy arrays that can be formed.

Note :

You are not required to print anything; it has already been taken care of. Just implement the function.

Constraints :

1 ≤ T ≤ 10
1 ≤ N ≤ 10^5
1 ≤ Arr[i] ≤ 10^9

The sum of N over all test cases does not exceed 10^5.

Time limit: 1 sec

Sample Input 1 :

2
5
1 2 1 2 2
8
4 5 4 2 4 2 4 4

Sample Output 1 :

2
3

Explanation For Sample Input 1 :

In the first test case:
The array can be divided into 2 copy arrays.
The first one is [1, 2, 1].
And, the second one is [2, 2].

In the second test case:
The array can be divided into 3 copy arrays.
The first one is [4, 5, 4].
The second one is [2, 4, 2].
And, the third one is [4, 4].

Sample Input 2 :

2
7
3 5 2 3 5 6 5
12
2 1 2 1 1 2 1 1 2 1 1 2

Sample Output 2 :

2
4

Hint 1

Greedily select the subarrays that satisfy the condition.

Approaches (1)

Approach 1

Greedy

Approach:

Iterate over the array keeping the frequency of each element that has occurred in the array;
Whenever the frequency of any element becomes greater than 1, increase the copy subarray count and clear the data structure in which the frequency is stored considering that a copy array has been formed and has been separated from the original array,

Algorithm:

Create a HashMap 'x' with key and value both as int.
Create a variable 'ans' for storing the final answer.
Iterate over the array, for every index 'i', increment the value of 'arr[i]' by 1 in HashMap.
If the value of 'arr[i]' becomes 2 in HashMap, increase the value of the 'ans' variable by 1 and clear the frequency HashMap.
Keep repeating the steps until the whole array is iterated.

Time Complexity

O(N), where 'N' is the length of the array 'arr'.

Since we need to iterate over the whole array which is of length 'N', while performing some operation on Hashmap on every step, the overall time complexity will be O(N).

Space Complexity

O(N), where 'N' is the length of the array 'arr'.

The memory required to store the Hashmap would be of the order of O(N).

(100% EXP penalty)