Re: [algogeeks] Valid Array
No. You made the same mistake as I.
Try this case: {1, 2, 2, 5, 5}.
Actually, this case defeats the solution of Manmeet's, yours, and mine.
(same min/max, same sum, same xor result)
I think the key point is that the N variable cannot be determined by 1
or 2 equation constraint.
On 2010-12-10 9:44, ADITYA KUMAR wrote:
@jai
yeah, it can be done using count sort logic
but that will take O(n) extra space
which can be avoided by using XOR.
On Fri, Dec 10, 2010 at 3:34 AM, jai gupta sayhelloto...@gmail.com
mailto:sayhelloto...@gmail.com wrote:
Algo:
In first traverse find the min and the max values.
if (max-min) not equals (N-1)
return false
In next traverse map each in a hashtable of size N where
index=key-min. Now in case of collision return false
return true
--
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
mailto:algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
mailto:algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Aditya Kumar
B-tech 3rd year
Computer Science Engg.
MNNIT, Allahabad.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@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.
--
You received this message because you are subscribed to the Google Groups Algorithm
Geeks group.
To post to this group, send email to algoge...@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.
Re: [algogeeks] Valid Array
O(2n) algo
1st traversal
calculate min
calculate sx=1^2^.^N
where N= no of elements
2nd traversal
fx=(A[1]-min+1)^(A[2]-min+1)...^(A[N]-min+1)
Now if sx=fx
Array is valid otherwise 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
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Aditya Kumar
B-tech 3rd year
Computer Science Engg.
MNNIT, Allahabad.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@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.
Re: [algogeeks] Valid Array
Algo: In first traverse find the min and the max values. if (max-min) not equals (N-1) return false In next traverse map each in a hashtable of size N where index=key-min. Now in case of collision return false return true -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
Re: [algogeeks] Valid Array
@jai yeah, it can be done using count sort logic but that will take O(n) extra space which can be avoided by using XOR. On Fri, Dec 10, 2010 at 3:34 AM, jai gupta sayhelloto...@gmail.com wrote: Algo: In first traverse find the min and the max values. if (max-min) not equals (N-1) return false In next traverse map each in a hashtable of size N where index=key-min. Now in case of collision return false return true -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Aditya Kumar B-tech 3rd year Computer Science Engg. MNNIT, Allahabad. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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.
