[Solved] Copy Arrays Contest Problem

Copy Arrays: 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].

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

Solution

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

import java.util.HashMap;

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' denotes the length of the array 'Arr'.
*/

public class Solution {
	public static int solution(int[] arr)
	{
		// Declaring a variable in order to store the length of 'arr'.
		int n = arr.length;
	
		// Declaring the HashMap 'x'.
		HashMap<Integer, Integer> x = new HashMap<>();
	
		// Declaring 'ans' variable for storing the result.
		int ans = 0;
	
		for (int i = 0; i < n; i++) {
	
			/// Increasing the frequency of elements on every iteration.
			x.put(arr[i], x.getOrDefault(arr[i], 0)  + 1);
	
			// Whenever the frequency of any element becomes greater than 1, the subarray can be called a copy array.
			if (x.get(arr[i]) > 1) {

				// Incrementing the ans variable as a copy array is discovered.
				ans++;

				// Clearing the Hashmap in order to store frequency for the new subarray from next iteration.
				x.clear();
			}
		}
        
		return ans;
	}

}

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' denotes the length of the array 'Arr'.
*/

#include <vector>
#include <unordered_map>
using namespace std;

int solution(vector<int> &arr) {
    
    // Declaring a variable in order to store the length of 'arr'.
    int n = arr.size();

    // Declaring the HashMap 'x'.
    unordered_map<int, int> x;

    // Declaring 'ans' variable for storing the result.
    int ans = 0;

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

        // Increasing the frequency of elements on every iteration.
        x[arr[i]]++;

        // Whenever the frequency of any element becomes greater than 1, the subarray can be called a copy array.
        if(x[arr[i]] > 1) {

            // Incrementing the ans variable as a copy array is discovered.
            ans++;
            
            // Clearing the Hashmap in order to store frequency for the new subarray from next iteration.
            x.clear();  
        }
    }
    
    return ans;
}

"""
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' denotes the length of the array 'Arr'.
"""


def solution(arr):

    # Declaring a variable in order to store the length of 'arr'.
    n = len(arr)

    # Declaring the HashMap 'x'.
    x = dict()

    # Declaring 'ans' variable for storing the result.
    ans = 0

    for i in range(0, n):

        # Increasing the frequency of elements on every iteration.
        x[arr[i]] = x.get(arr[i], 0) + 1

        # Whenever the frequency of any element becomes greater than 1, the subarray can be called a copy array.
        if x[arr[i]] > 1:

            # Incrementing the ans variable as a copy array is discovered.
            ans += 1

            # Clearing the Hashmap in order to store frequency for the new subarray from next iteration.
            x.clear()
    
    return ans

Happy Learning – If you require any further information, feel free to contact me.