Re: [algogeeks] Re: find duplicate and missing element

@ashish aggarwal good solution but my problem is ex. i have n array of element 1,2,3,3,4; XOR of (1,2,3,3,4)with (1,2,3,4,5). finally i have XOR of 3 nd 5 (3^5) is 110 now what pls explan me in detail On Thu, Sep 2, 2010 at 1:30 PM, ashish agarwal wrote: > In this method overflow will be there..

[algogeeks] Re: find duplicate and missing element

what do u think about this ...its O(n) program.. #include #include # include "malloc.h" # include bool bRemoveDuplicates(int array[], int iSize){ if(iSize <1) return false; if(array == NULL) return false; if(iSize == 1) return true; int left_comp = 0; int right_comp = 1;

Re: [algogeeks] Re: find duplicate and missing element

@ankit Yup I got your point. I didn't see the algo given by dhritiman previously. I think that is better than my solution , where it fits in all cases. Cheers Kartheek On Fri, Sep 3, 2010 at 1:32 PM, Ankit Sinha wrote: > @kartheek, thanks for ur input!! Certainly, ur soln is fine but only > w

Re: [algogeeks] Re: find duplicate and missing element

@kartheek, thanks for ur input!! Certainly, ur soln is fine but only will cater when array is 1...n but what if it ranges for 0...n-1. The algo given by dhritiman fits in all the scenario. but ofcourse for given question ( 1 to 100) your mathematical approach is good. :)... Cheers, Ankit Sinha!!!

Re: [algogeeks] Re: find duplicate and missing element

Yeah The solution given by Ankit is gr8. But inorder to not destroy the array we need to go by the geek method where Suppose x is the duplicated element and y is the missing element in the array. Multiply all the elements in the array to prod and sum all the elements in the array to sum. Divid

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; whi

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 becaus

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.

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

[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

Re: [algogeeks] Re: find duplicate and missing element

@Dinesh, Yes, we can't apply this method, if that's not allowed. On Thu, Sep 2, 2010 at 10:31 AM, dinesh bansal wrote: > > > On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das wrote: > >> >> Given a array, A[1..n], do the following. >> Start from i=1 and try placing each number in its correct positi

Re: [algogeeks] Re: find duplicate and missing element

On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das 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 alr

[algogeeks] Re: find duplicate and missing element

@Raj: It is just algebra. Dave On Sep 1, 11:50 am, Raj Jagvanshi wrote: > in ur algo i confuse in solving eqn > > > > On Wed, Sep 1, 2010 at 6:31 PM, Dave wrote: > > @Raj: Best what? > > > Dave > > > On Sep 1, 12:08 am, Raj Jagvanshi wrote: > > > Thanks Dave > > > but i want best > > > > On We

[algogeeks] Re: find duplicate and missing element

According to me we can apply the equatin method : Let the missing number be y. Let the duplicated no. be x. 1. then find the product of the 1 to 100 and the sum 1 to 100 :A Product would be of the form...1 *2*3x*..y*100 : B Sum : 1+2+3.+x+y.+100 2. find the prduct

Re: [algogeeks] Re: find duplicate and missing element

1. First find the sum of all given elements.: sum 2. find the sum of elements in the given range. : sum_1 3. Find the duplicates.: d 4. Missing Number: sum-sum_1+d. http://codepad.org/77Nr9Hay On Wed, Sep 1, 2010 at 9:50 AM, Raj Jagvanshi wrote: > in ur algo i conf

Re: [algogeeks] Re: find duplicate and missing element

in ur algo i confuse in solving eqn On Wed, Sep 1, 2010 at 6:31 PM, Dave wrote: > @Raj: Best what? > > Dave > > On Sep 1, 12:08 am, Raj Jagvanshi wrote: > > Thanks Dave > > but i want best > > > > > > > > On Wed, Sep 1, 2010 at 7:14 AM, Dave wrote: > > > Suppose that x is duplicated and y is o

Re: [algogeeks] Re: find duplicate and missing element

can you explain on your algorithm. Are you using any extra array. On Wed, Sep 1, 2010 at 11:08 AM, Dhritiman Das 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 posi

[algogeeks] Re: find duplicate and missing element

@Raj: Best what? Dave On Sep 1, 12:08 am, Raj Jagvanshi wrote: > Thanks Dave > but i want best > > > > On Wed, Sep 1, 2010 at 7:14 AM, Dave 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 > >

Re: [algogeeks] Re: find duplicate and missing element

Thanks Dave but i want best On Wed, Sep 1, 2010 at 7:14 AM, Dave 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 o

Re: [algogeeks] Re: find duplicate and missing element

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 re

[algogeeks] Re: find duplicate and missing element

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