Algorithm: How to tell if an array is a permutation in O(n)?
- by Iulian Serbanoiu
Hello,
Input: A read-only array of N elements containing integer values from 1 to N. And a memory zone of a fixed size (10, 100, 1000 etc - not depending on N).
How to tell in O(n) if the array represents a permutation?
--What I achieved so far:--
I use the limited memory area to store the sum and the product of the array.
I compare the sum with N*(N+1)/2 and the product with N!
I know that if condition (2) is true I might have a permutation. I'm wondering if there's a way to prove that condition (2) is sufficient to tell if I have a permutation. So far I haven't figured this out ...
Thanks,
Iulian