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, 0, 6}, the answer should be 1 & 3.
#include<stdio.h>
#include<math.h>
int main()
{
int n,A[15],i,flage,cycle=0,j,temp;
printf("\nEnter size of array : ");
scanf("%d",&n);
printf("\nEnter elements of array( %d space saperated integer) : \n",n );
for(i=0;i<n;i++)
scanf("%d",&A[i]);
flage=0;j=0;
printf("\n OUTPUT : ");
for(i=0;i<n;i++)
{
if( A[abs(A[i])] >= 0)
A[abs(A[i])]=-A[abs(A[i])];
else
printf(" %d",abs(A[i]) );
}
return 0;
}
This comment has been removed by the author.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteThe idea is good, but this would fail if the index you're trying to inverse the sign for contains the value zero.
ReplyDeleteFor example [1,0,1]
Your code would try to do A[abs(A[i])]=-A[abs(A[i])]
on a zero value that would have no effect.
We can overcome this by adjusting the values of the array and incrementing each value by one. This way the range is always from 1 to n (instead of 0 to n-1).
For some reason I couldn't print the code (blogspot just deletes some of the code after publish), but the idea is simple.
Exactly your idea, just making sure that each value is incremented before we enter your for-loop, and then we adjust the values (make sure we subtract one after every abs we do) as we go inside the main for-loop.