Algorithm: How to tell if an array is a permutation in O(n)?
Posted
by Iulian Serbanoiu
on Stack Overflow
See other posts from Stack Overflow
or by Iulian Serbanoiu
Published on 2010-05-20T10:44:42Z
Indexed on
2010/05/20
10:50 UTC
Read the original article
Hit count: 333
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
© Stack Overflow or respective owner
