Author |
Topic: Valid Array (Read 2008 times) |
|
sateesp
Newbie
Gender: 
Posts: 35
|
 |
Valid Array
« on: Jul 28th, 2010, 10:44pm » |
 Quote  Modify
|
Given array A with n elements, give an algorithm for finding whether it’s a valid array or not?
Array is called Valid if all the numbers appearing in A [1...N] are consecutive numbers.
Example: A={5,3,4} is a valid array
A={3,7,5,4,6} is a valid array
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Valid Array
« Reply #1 on: Jul 29th, 2010, 2:45am » |
Quote Modify
|
You could use a hash to check that each number is unique, and find the max and min to check whether the difference is N-1. Under those two conditions (uniqueness and max difference smaller than N), the array must be valid.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: Valid Array
« Reply #2 on: Jul 29th, 2010, 11:29am » |
Quote Modify
|
find minimum of the array
then
for( i=0; i<n; i++)
{
A[A[i]-min] *= -1;
}
for( i=0; i<n; i++)
{
if(A[i] > 0)
return false;
}
return true;
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Valid Array
« Reply #3 on: Jul 30th, 2010, 1:36am » |
Quote Modify
|
on Jul 29th, 2010, 11:29am, birbal wrote:
You might want to add an abs() on A[i] and check for array bounds.
|
|
IP Logged |
|
|
|
mvsknitw
Newbie
Posts: 1
|
|
Re: Valid Array
« Reply #4 on: Aug 2nd, 2010, 10:54am » |
Quote Modify
|
on Jul 29th, 2010, 2:45am, towr wrote:| You could use a hash to check that each number is unique. |
|
@Towr,
Could you please tell how a good hash function would be for the above? i tried implementing a hasharray[max-min+1] and store the each arr element at max - a[i] index. But i guess i would be wasting lot of space in case array is something like {2,3,1000,1002}.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Valid Array
« Reply #5 on: Aug 2nd, 2010, 12:16pm » |
Quote Modify
|
For these kind of things I'd pick something from a library. Creating hash functions is not really something you ought to attempt yourself unless you have the necessary knowledge and skills, because good hash functions are hard to make.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
sk
Newbie
Posts: 45
|
|
Re: Valid Array
« Reply #6 on: Mar 16th, 2011, 11:41pm » |
Quote Modify
|
Add all the numbers. Get the min and max in one pass. Summation = n(n+1)/2 for consecutive numbers (starting with 1). So compare the summation you got - min number * total numbers. This should be equal for valid array.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Valid Array
« Reply #7 on: Mar 17th, 2011, 2:29am » |
Quote Modify
|
I think you should subtract n*(min-1) instead. Or compare to n*(n-1)/2.
A formula for the expected sum would be (min+max)*n/2.
But this is a necessary condition, not a sufficient one. If the sum matches, it doesn't mean that the numbers are consecutive. The array [1 4 5 5] has a sum of 15, compatible with a sum from 1 to 5 (the min and the max), but it is not even an array of 5 number.
|
| « Last Edit: Mar 17th, 2011, 2:30am by Grimbal » |
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Valid Array
« Reply #8 on: Mar 17th, 2011, 2:40am » |
Quote Modify
|
A solution without a hash map:
int min = max = A[0];
boolean valid = true;
for( int i=0 ; i<n ; i++ ){
if( A[i]<min ) min = A[i];
if( A[i]>max ) max = A[i];
if( used[ A[i]%n ] ) valid = false;
used[ A[i]%n ] = true;
The array is valid if valid is true and max = min+n-1
|
| « Last Edit: Mar 17th, 2011, 2:46am by Grimbal » |
IP Logged |
|
|
|
Roman
Newbie
Posts: 2
|
|
Re: Valid Array
« Reply #9 on: Aug 15th, 2011, 5:26am » |
Quote Modify
|
We could avoid another array if two passes are allowed. In one pass, we can find min and max where
max = min + n - 1
Then one could xor all the array elements and numbers from min to max in one pass. It should come to zero.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Valid Array
« Reply #10 on: Aug 15th, 2011, 8:43am » |
Quote Modify
|
That wouldn't work, because 2,3,4,5,6,7,8,9,10 and 2,2,2,2,2,2,2,2,10 both XOR to 1, so you cannot distinguish them in this way.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
kart
Newbie
Gender:
Posts: 4
|
|
Re: Valid Array
« Reply #11 on: Sep 17th, 2011, 5:05am » |
Quote Modify
|
int min = intArr[0];
int sum = 0;
for (int i = 1; i < intArr.Length; i++)
{
if (intArr[i] < min)
{
sum += (min - intArr[i]) * i;
min = intArr[i];
}
else
{
sum += intArr[i] - min;
}
}
int exp = ((intArr.Length - 1)*(intArr.Length))/2;
if (sum == exp)
return true;
else
return false;
This should work
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Valid Array
« Reply #12 on: Sep 17th, 2011, 5:34am » |
Quote Modify
|
It doesn't. 1+2+3+4+5 = 1+3+3+3+5 and your algorithm can't distinguish the two even though the {1,2,3,4,5} would be valid and {1,3,3,3,5} wouldn't.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print