On Aug 1, 6:25 pm, Deepak <deepakthegi...@gmail.com> wrote:
> Given an array of elements 'n'. some k<n elements are replaced by
> elements such that the repalced elements are <n. with o(n) find the
> missing elements, without wasting any extra memory.
I think you did not phrase the question correctly. I am assuming you
meant an array of n-numbers from [1,n]. Here, k<n numbers are replaced
by numbers are replaced. We need to find the missing numbers. I
assume, we can take the space for a loop counter, even if we can't we
can do the same thing by hard-coding, which will be just a little
messy.
Pseudocode:
for i from 1 to n
if(arr[i]!=i):
arr[arr[i]]^=arr[i]
arr[i]^=arr[arr[i]]
arr[arr[i]]^=arr[i]
for i from 1 to n
if(arr[i]!=i)
print i
The logic being here is, whenever a number is found out of place, say,
the number 2 is found at position 4, arr[4] and arr[2] are swapped
(without the use of temp variables). Then another pass is made to
check if i exists at arr[i]. If it does not, that implies, i was not
present in arr, otherwise it would have been placed at arr[i].
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
