[algogeeks] Re: find duplicate and missing element
@luckyzoner can post the c program of what u ave said above.. -- 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: find duplicate and missing element
In this method overflow will be there..if number is just bigger...so by doing XOR we can get missing number and repeated number . take xor of all element of array and take this xor with array[1...n] So we get xor of two numbers. now get set bit of this xor and proceed. On Thu, Sep 2, 2010 at 12:36 AM, bittu shashank7andr...@gmail.com wrote: @luckyzoner can post the c program of what u ave said above.. -- 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.
Re: [algogeeks] Re: Take 5 digit number and find 2 power that number.............
I think it will be 1x On Wed, Sep 1, 2010 at 10:53 PM, Yan Wang wangyanadam1...@gmail.com wrote: Maybe you misunderstand the question. The question is how to compute 2^X where 0 = X = 9? How? On Wed, Sep 1, 2010 at 10:48 PM, Ruturaj rutura...@gmail.com wrote: a 5 digit number is of order 10^5 which is 10^16 of which int in C is of size. Just multiply both numbers. On Sep 2, 10:39 am, prasad rao prasadg...@gmail.com wrote: Program that takes a 5 digit number and calculates 2 power that number and prints it and should not use the Big-integer and Exponential Function's. -- 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.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.
Re: [algogeeks] Re: Take 5 digit number and find 2 power that number.............
Suppose the number of shifts be x. Also let the integer be represented by 16 bits on that machine. Now take int n= (int)(x/16 + 0.5), to take the upper cap on result :) . SO having 2^x will be same as doing 2(x-1) so essentially if we represent the resultant number in a linked list of nodes, where each node can store an integer, then the bit position at 2+x-1=x+1 will be set as 1 and this (x+1)th nit will fall in (x+1)/16th node in linked list also in that node (x+1)%16 will give the position of bit to be set. On Thu, Sep 2, 2010 at 1:32 PM, ashish agarwal ashish.cooldude...@gmail.com wrote: I think it will be 1x On Wed, Sep 1, 2010 at 10:53 PM, Yan Wang wangyanadam1...@gmail.comwrote: Maybe you misunderstand the question. The question is how to compute 2^X where 0 = X = 9? How? On Wed, Sep 1, 2010 at 10:48 PM, Ruturaj rutura...@gmail.com wrote: a 5 digit number is of order 10^5 which is 10^16 of which int in C is of size. Just multiply both numbers. On Sep 2, 10:39 am, prasad rao prasadg...@gmail.com wrote: Program that takes a 5 digit number and calculates 2 power that number and prints it and should not use the Big-integer and Exponential Function's. -- 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.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.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards, Saurabh -- 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: Take 5 digit number and find 2 power that number.............
nice... -- 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: find duplicate and missing element
@ashish: cud u plzz explain a bit more... -- 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: Take 5 digit number and find 2 power that number.............
can post the c program of what u ave said above On 2 September 2010 16:06, vikash jain vikash.ro...@gmail.com wrote: nice... -- 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.
Re: [algogeeks] Re: find duplicate and missing element
this question can be sovled very easily 1.jus sum the given array...x 2.sum the squares of the given array..y 3.now use the AP.n(n+1)/2..for n=100 4.similarly compute n(n+1)(2n+1)/6 for n =100.. Now solve these eqns ...u get the missing and the dupicate.. -- 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: Amazon intern Question
trie will be the best choice for this.. -- 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: find duplicate and missing element
@Dhritiman, It's good algo man!!!The only thing is we are destroying the array but also that's mandatory as only o(n) complexity we are interested in. As Somebody wanted the code, here I am attaching below: - int a[SIZE_A] = {0,2,1,4,0}; int i = 0, dup = 0, pos = 0, t =0; while (i 5) { if (a[i] == i) i++; else if (a[a[i]] == a[i]) { dup = a[i]; printf (\nduplicated element is [%d], dup); pos = i; i++; } else { t= a[i]; a[i] = a[a[i]]; a[t] = t; } } printf (\nmissing element is [%d], pos); Cheers, Ankit Sinha On Thu, Sep 2, 2010 at 7:08 AM, Dhritiman Das dedhriti...@gmail.com wrote: @Dinesh, Yes, we can't apply this method, if that's not allowed. On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal bansal...@gmail.com wrote: On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das dedhriti...@gmail.com wrote: Given a array, A[1..n], do the following. Start from i=1 and try placing each number in its correct position in the array. If the number is already in its correct position, go ahead. if (A[i] == i) , i++ else if the number was already restored to its correct position, then it is a duplicate , so remember it and move ahead if (A[A[i]] == A[i]), dup = A[i], i++ ; else swap the elements at the current index i and that at A[i]'s correct position in the array. continue this until all numbers are placed in their correct position in the array Finally, A[missing] will be dup. O(n) @Dharitiman, good solution man. No expensive computation, no extra memory required. Only problem is it will change the input array to sorted order which may not be desired. On Wed, Sep 1, 2010 at 7:14 AM, Dave dave_and_da...@juno.com wrote: Suppose that x is duplicated and y is omitted. Then the sum of the numbers would be 5050 + x - y. Similarly, the sums of the squares of the numbers would be 338,350 + x^2 - y^2. Calculate the sum and sum of squares of the numbers and solve the resulting equations for x and y. Dave On Aug 31, 1:57 pm, Raj Jagvanshi raj.jagvan...@gmail.com wrote: There is an array having distinct 100 elements from 1 to 100 but by mistake some no is duplicated and a no is missed. Find the duplicate no and missing no. Thanks Raj Jagvanshi -- 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. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- 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. -- 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.