Question: Given an array of n elements which contains elements from 0 to n-1, with any of these numbers appearing any number of times. Find these repeating numbers in O(n) and using only constant memory space.
For example, let n be 7 and array be {1, 2, 3, 1, 3, 6, 6}, the answer should be 1, 3 and 6.
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
}
{
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
}
Solution:
1
2
3
4
5
6
7
8
9
10
11
12
| 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])); } } |
No comments:
Post a Comment