N-Repeated Element in Size 2n Array in Java
Given a size '2N' array 'arr', the resulting array has 'N + 1' unique elements, one of which occurs in 'N' time. Our task is to Return 'N' repeated entries in an array of size '2N'.
Example 1:
Input:
int N = 4 int arr = [1, 5, 8, 1, 1, 3, 5, 1]
Output:
The number that occurs N times is 1.
Explanation:
For the given array [1, 5, 8, 1, 1, 3, 5, 1], count the frequency of each element that occurred in the array (1 occurred 4 times; 5 occurred 2 times; 8 occurred 1 time; 3 occurred 1 time). The frequency of element '1' is equal to the 'N'. Hence, the number that occurred n times is 1.
Example 2:
Input:
int N = 3 int arr = [10, 5, 10, 5, 10, 5]
Output:
The number that occurs N times is 5.
Explanation:
For the given array [10, 5, 10, 5, 10, 5], count the frequency of each element that occurred in the array (10 occurred 3 times; 5 occurred 3 times). The frequency of both elements is equal. Hence, it returns the least number as an output. Thus, the number that occurred n times is 5.
Approach: Using HashMap
The simplest approach to the problem is to iterate through an unordered map, such as a hash map, and store the count of each element. Then, we can use this map to find the element with count 'N'.
Algorithm:
Step 1: Initialize a HashMap 'map' with the initial count of each element.
Step 2: Loop over each element x in the array iteratively.
Step 2.1: If the element x is not there in the hash map, add it to the map with an increment count of 1.
Step 2.2: If the element x is already present in the map, increment its count by 1.
Step 2.3: Check if the number of elements in the map, x, equals half the length of the array a (that is, a.length / 2).
Step 2.3.1: Return the element x if the statement is true.
Step 2.4: Return -1 if no element with a count equal to half the length of the array is found.
Step 3: End.
Implementation:
FileName: HashMapRepeatedN.java
import java.util.HashMap; import java.util.Scanner; import java.io.*; public class HashMapRepeatedN { static int RepeatedElement(int[] a) { int N = a.length / 2; HashMapmap = new HashMap<>(); // Count the number of times each element appears by iterating through the array's elements. for (int x : a) { map.put(x, map.getOrDefault(x, 0) + 1); } // Iterate over the hash map's elements to determine which number has a count of "N," then return that number. for (int keyele : map.keySet()) { if (map.get(keyele) == N) { return keyele; } } // If the element is not found, return -1. return -1; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("Enter the N value: "); int N = sc.nextInt(); int[] a = new int[2 * N]; System.out.print("Enter the elements of an array: "); for (int i = 0; i < 2 * N; i++) { a[i] = sc.nextInt(); } int result = RepeatedElement(a); System.out.println("The Number that occurred N times is: " + result); } }
Output:
Enter the N value: 4 Enter the elements of an array: 1 5 8 1 1 3 5 1 The Number that occurred N times is: 1
Complexity Analysis:
The Time Complexity is O(N), where N represents the size of an array. As we are performing the traversal of an array once and hash map once. The Space Complexity is O(N).
Approach: Using HashSet
Perhaps it is significant to note that there is a total of "2N" elements in the array, and since repeated elements occur "N" times, each element will only appear once. Thus, when an element appears more than once, we may identify it as the 'N' repeated element if we have a way to store the elements we have already seen. Java provides a hash set that we can use to store the previously visited element.
Algorithm:
Step 1: Declare RepeatedElement, which is a static method. RepeatedElement returns an integer after taking an array of integers as input.
Step 2: Divide N by the length of the input array to calculate its value.
Step 3: Initialise a set HashSet to store the visited elements.
Step 4: Iterate over the input array.
Step 4.1: If the current element has appeared more than once, return it if it has been added to the HashSet.
Step 4.2: Else, add the element to the HashSet.
Step 5: Return -1 if there are no elements that are found to be repeated N times.
Step 6: End.
Implementation:
FileName: HashSetRepeatedN.java
import java.util.HashSet; import java.util.Scanner; import java.io.*; public class HashSetRepeatedN { static int RepeatedElement(int[] a) { int N = a.length / 2; // Initialization of HashSet HashSets = new HashSet<>(); for (int x : a) { // Return the number if it arises over a second time. if (s.contains(x)) { return x; } // To assign a number as traversed, insert it into the set. s.add(x); } // return -1 if there are no 'N' repeated elements identified. return -1; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("Enter the N value: "); int N = sc.nextInt(); int[] a = new int[2 * N]; System.out.print("Enter the elements of an array: "); for (int i = 0; i < 2 * N; i++) { a[i] = sc.nextInt(); } int result = RepeatedElement(a); System.out.println("The Number that occurred N times is: " + result); } }
Output:
Enter the N value: 4 Enter the elements of an array: 1 5 8 1 1 3 5 1 The Number that occurred N times is: 1
Complexity Analysis:
The Time Complexity is O(N), where N represents the size of an array. As we are performing the traversal of an array once and insert, search operations are also performed, which remains constant. The Space Complexity is O(N).
Approach: Using Comparison Method
The count of the major element in the array is N / 2 + 1 since there is a total of 2N numbers, all of which occur exactly once, except the major element. Thus, if we take into account each subarray of length 4, at least one of them has to include a significant element.
Suppose a subarray of length 4 begins at a major element. In that case, it will have two major elements since a length of two subarrays has a major element, or every length of two subarrays has exactly one major element. Therefore, the elements we need to compare are only those that are 1, 2, or 3 distances distant from each other.
Algorithm:
Step 1: Declare a static method called RepeatedElement, which returns an integer after taking a Vector
Step 2: Calculate N by dividing the input vector a's size by half.
Step 3: Compare items with their neighbors at one, two, and three distances by looping from 1 to 3.
Step 3.1: Check the elements at positions i and x + i.
Step 3.2: Return the element if it has been found to be repeated.
Step 4: Return -1 if no element is found to be repeated N times.
Step 5: End.
Implementation:
FileName: ComparisonRepeated.java
import java.util.HashSet; import java.util.Scanner; import java.util.Vector; import java.io.*; public class Autoref { static int RepeatedElement(Vectora) { int N = a.size() / 2; // Comparing elements with their neighbors // at one, two, and three distances involves // looping through numbers one to three. for (int x = 1; x <= 3; x++) { for (int i = 0; i < (a.size() - x); i++) { // Return the element if it has been found to be repeated. if (a.get(i).equals(a.get(x + i))) { return a.get(i); } } } // If no ‘N’ repeated element is found, then return -1. return -1; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); System.out.print("Enter the N value: "); int N = sc.nextInt(); Vector a = new Vector<>(); System.out.print("Enter the elements of an array: "); for (int i = 0; i < 2 * N; i++) { a.add(sc.nextInt()); } int result = RepeatedElement(a); System.out.println("The Number that occurred N times is: " + result); } }
Output:
Enter the N value: 4 Enter the elements of an array: 1 5 8 1 1 3 5 1 The Number that occurred N times is: 1
Complexity Analysis:
The Time Complexity is O(N), where N represents the size of an array. Depending on the value of 'N', the outer loop only has a range of 1 to 3. We are going through the array one time. Consequently, O(3 * N) = O(N) is the total time complexity. The Space Complexity is O(1).