Re: [algogeeks] Re: Valid Array
@mohan, when the num of repeatation is bigger than 1, it may be wrong,please
check {1, 1, 2, 5, 6, 6}
On Fri, Dec 10, 2010 at 12:41 PM, mo...@ismu mohan...@gmail.com wrote:
i did nt get this xor part in adithya solution
check if this works
array is valid if satisfy 2 conditions
1.max-min=n-1
2.there should be no repeatations
first one can be done in O(n)
for second
check 1xor2xor...xorn=(a[1]-min+1)xor(a[2]-min+1)xor..
if both are equal there are no repeatations
--
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.
--
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.
[algogeeks] Re: Valid Array
I got the correct answer: If it is a valid array, sum of all elements in the array = value calculated using arithmetic progression formula In this case Sum of arithmetic progression = (n/2)[2*a+(n-1)*d} where a = min of the array n = number of elements d = 1 If this value is equal to sum of all the elements in the array then it is a valid array On Dec 10, 6:44 am, ADITYA KUMAR aditya...@gmail.com 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 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.- Hide quoted text - - Show quoted text - -- 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] Re: Valid Array
prims check for this case [1,1,4,4] -- 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.
[algogeeks] Re: Valid Array
my bad The solution i quoted works only in case of no repititions. Aditya solution is correct On Dec 10, 9:23 am, mo...@ismu mohan...@gmail.com wrote: prims check for this case [1,1,4,4] -- 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] Re: Valid Array
i did nt get this xor part in adithya solution check if this works array is valid if satisfy 2 conditions 1.max-min=n-1 2.there should be no repeatations first one can be done in O(n) for second check 1xor2xor...xorn=(a[1]-min+1)xor(a[2]-min+1)xor.. if both are equal there are no repeatations -- 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.
