Problem
Input : array = {1, 2, 3, 1, 3, 6, 6}, n = 7
Output = 1,3,6
Solution
This problem is an extended version of following problem.
Find the two repeating elements in a given array
Method 1 and Method 2 of the above link are not applicable as the question says O(n) time complexity and O(1) constant space. Also, Method 3 and Method 4 cannot be applied here because there can be more than 2 repeating elements in this problem. Method 5 can be extended to work for this problem. Below is the solution that is similar to the Method 5.
Algorithm:
Note: The above program doesn’t handle 0 case (If 0 is present in array). The program can be easily modified to handle that also. It is not handled to keep the code simple.
Time Complexity: O(n)
Auxiliary Space: O(1)
Please write comments if you find the above codes/algorithms incorrect, or find better ways to solve the same problem.
References
http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/
Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times.Example
Follow UP - Find these repeating numbers in O(n) and using only constant memory space.
Input : array = {1, 2, 3, 1, 3, 6, 6}, n = 7
Output = 1,3,6
Solution
This problem is an extended version of following problem.
Find the two repeating elements in a given array
Method 1 and Method 2 of the above link are not applicable as the question says O(n) time complexity and O(1) constant space. Also, Method 3 and Method 4 cannot be applied here because there can be more than 2 repeating elements in this problem. Method 5 can be extended to work for this problem. Below is the solution that is similar to the Method 5.
Algorithm:
traverse the list for i= 0 to n-1 elements { check for sign of A[abs(A[i])] ; if positive then make it negative by A[abs(A[i])]=-A[abs(A[i])]; else // i.e., A[abs(A[i])] is negative this element (ith element of list) is a repetition }Implementation:
void printRepeating(int arr[], int size) { int i; printf("The repeating elements are: \n"); for (i = 0; i < size; i++) { if (arr[abs(arr[i])] >= 0) arr[abs(arr[i])] = -arr[abs(arr[i])]; else printf(" %d ", abs(arr[i])); } }
Note: The above program doesn’t handle 0 case (If 0 is present in array). The program can be easily modified to handle that also. It is not handled to keep the code simple.
Time Complexity: O(n)
Auxiliary Space: O(1)
Please write comments if you find the above codes/algorithms incorrect, or find better ways to solve the same problem.
References
http://www.geeksforgeeks.org/find-duplicates-in-on-time-and-constant-extra-space/
0 comments:
Post a Comment