Re: [algogeeks] array question

[sukran dhawan]

when u xor nos with odd number of times we will get back the same no.only
even occurences will give 0.question is to find the no with even
 occurence.how will you find that no?
On Tue, Aug 16, 2011 at 1:41 PM, MAC  wrote:

>
> Given an array of integers. Each number in the array repeats ODD number of
> times, but only 1 number repeated for EVEN number of times. Find that
> number.
>
>
> --
> thanks
> --mac
>
>  --
> You wreceived this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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 algogeeks@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] array question

[wujin chen]

i think XOR operator should be used to solve question.
Given the integers in the array A: n1,n2...nk,
we can do this recursively:
XOR all the integers in A, assume the result is F = n1^n2^...^nk,
F must not be 0.
for i-th bit in F from rightmost to left most:
 if the i-th bit is 1, halve A into 2 parts: A1 and A2, that elements in
A1 hold 1 in the i-th bit and A2 hold 0 in the i-th bit
 if XOR(A1) == 0
 A1 is the result
if  XOR(A2) == 0
 A2 is the result
 if the result has not been got, we will use the next non-zero bit in F
to halve A1 and A2

excepte the first pass,we can do some optimization so that there is no need
to compute the F with XOR one by one. we can compute F when halve the array.
but in this way , the time complexity may be not linear
if the question is like this:

> Given an array of integers. Each number in the array repeats 3 number of
> times, but only 1 number repeated for 2 number of times. Find that number.

it can be solved in O(n), because we can use the number to eliminate some
parts.









2011/8/16 Raghavan 

>
>- Sort the array - o(log n) based on the sorting strategy might be
>radix sort
>- check the numbers count have a counter o(1) space and again o(n) time
>- changing from one number to other check counter%2 == 0 if so then we
>get answer
>
> So consolidated time would be o(n) and space is o(1);
>
> On Tue, Aug 16, 2011 at 3:20 PM, MAC  wrote:
>
>> The question needed o(1) space and o(n)  time ...  o(n) map approach is
>> obviously fine but space is taken up ...
>>
>>
>> On Tue, Aug 16, 2011 at 2:38 PM, Raghavan  wrote:
>>
>>> @sukran:
>>> If you were asking for the map based solution
>>>
>>> space and time complexity would be o(n).
>>>
>>>
>>> On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan 
>>> wrote:
>>>
 what is the complexity in which it has been done ?

 On Tue, Aug 16, 2011 at 1:41 PM, MAC  wrote:

>
> Given an array of integers. Each number in the array repeats ODD number
> of times, but only 1 number repeated for EVEN number of times. Find that
> number.
>
>
> --
> thanks
> --mac
>
>  --
> 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.
> 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 algogeeks@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.

>>>
>>>
>>>
>>> --
>>> Thanks and Regards,
>>> Raghavan KL
>>>
>>>  --
>>> 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.
>>> 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.
>>>
>>
>>
>>
>> --
>> thanks
>> --mac
>>
>>  --
>> 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.
>> 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.
>>
>
>
>
> --
> Thanks and Regards,
> Raghavan KL
>
>  --
> 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.
> 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 algogeeks@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] array question

[Raghavan]

   - Sort the array - o(log n) based on the sorting strategy might be radix
   sort
   - check the numbers count have a counter o(1) space and again o(n) time
   - changing from one number to other check counter%2 == 0 if so then we
   get answer

So consolidated time would be o(n) and space is o(1);

On Tue, Aug 16, 2011 at 3:20 PM, MAC  wrote:

> The question needed o(1) space and o(n)  time ...  o(n) map approach is
> obviously fine but space is taken up ...
>
>
> On Tue, Aug 16, 2011 at 2:38 PM, Raghavan  wrote:
>
>> @sukran:
>> If you were asking for the map based solution
>>
>> space and time complexity would be o(n).
>>
>>
>> On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan wrote:
>>
>>> what is the complexity in which it has been done ?
>>>
>>> On Tue, Aug 16, 2011 at 1:41 PM, MAC  wrote:
>>>

 Given an array of integers. Each number in the array repeats ODD number
 of times, but only 1 number repeated for EVEN number of times. Find that
 number.


 --
 thanks
 --mac

  --
 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.
 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 algogeeks@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.
>>>
>>
>>
>>
>> --
>> Thanks and Regards,
>> Raghavan KL
>>
>>  --
>> 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.
>> 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.
>>
>
>
>
> --
> thanks
> --mac
>
>  --
> 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.
> 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.
>



-- 
Thanks and Regards,
Raghavan KL

-- 
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.
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] array question

[MAC]

The question needed o(1) space and o(n)  time ...  o(n) map approach is
obviously fine but space is taken up ...

On Tue, Aug 16, 2011 at 2:38 PM, Raghavan  wrote:

> @sukran:
> If you were asking for the map based solution
>
> space and time complexity would be o(n).
>
>
> On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan wrote:
>
>> what is the complexity in which it has been done ?
>>
>> On Tue, Aug 16, 2011 at 1:41 PM, MAC  wrote:
>>
>>>
>>> Given an array of integers. Each number in the array repeats ODD number
>>> of times, but only 1 number repeated for EVEN number of times. Find that
>>> number.
>>>
>>>
>>> --
>>> thanks
>>> --mac
>>>
>>>  --
>>> 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.
>>> 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 algogeeks@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.
>>
>
>
>
> --
> Thanks and Regards,
> Raghavan KL
>
>  --
> 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.
> 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.
>



-- 
thanks
--mac

-- 
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.
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] array question

[Raghavan]

@sukran:
If you were asking for the map based solution

space and time complexity would be o(n).


On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan wrote:

> what is the complexity in which it has been done ?
>
> On Tue, Aug 16, 2011 at 1:41 PM, MAC  wrote:
>
>>
>> Given an array of integers. Each number in the array repeats ODD number of
>> times, but only 1 number repeated for EVEN number of times. Find that
>> number.
>>
>>
>> --
>> thanks
>> --mac
>>
>>  --
>> 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.
>> 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 algogeeks@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.
>



-- 
Thanks and Regards,
Raghavan KL

-- 
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.
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] array question

[Raghavan]

One easier thing would be to use a map to solve this.



On Tue, Aug 16, 2011 at 1:41 PM, MAC  wrote:

>
> Given an array of integers. Each number in the array repeats ODD number of
> times, but only 1 number repeated for EVEN number of times. Find that
> number.
>
>
> --
> thanks
> --mac
>
>  --
> 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.
> 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.
>



-- 
Thanks and Regards,
Raghavan KL

-- 
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.
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] array question

[sukran dhawan]

what is the complexity in which it has been done ?

On Tue, Aug 16, 2011 at 1:41 PM, MAC  wrote:

>
> Given an array of integers. Each number in the array repeats ODD number of
> times, but only 1 number repeated for EVEN number of times. Find that
> number.
>
>
> --
> thanks
> --mac
>
>  --
> 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.
> 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 algogeeks@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] array question

[shady]

doesnt matter Order will be (nlogn)
where n is max(elements in first set, elements in 2nd set)

PS : dont submit codes from next time

On Sun, Aug 14, 2011 at 7:43 PM, Nikhil Veliath  wrote:

> i feel binary search idea is the best
>
> guys i am having problem in finding out complexity...here is my
> solution to the above problem...whats the complexity...
>
> sort the 2 arraysa and b
>
> l=0,i=0,flag=0;
> while(a[i] slightly greater than the first
> i++;  //element of second array
> for(i;i {
> j=l;
> while(a[i]>=b[j])
> {
> if(a[i]==b[j])
> {
> printf("Common element is %d",a[i]);
> flag=1
> break;
> }
> j++;
> l=j;
> }
> if(flag==1)
> break;
> }
>
>
> On Sun, Aug 14, 2011 at 6:55 PM, shady  wrote:
> > @sagar suppose numbers are very large( > 10^9) , how will you hash then ?
> > can you please state the hashing function in this case
> >
> > On Sun, Aug 14, 2011 at 6:50 PM, sagar pareek 
> wrote:
> >>
> >> Hashing
> >> O(n+m)
> >>
> >> On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro 
> >> wrote:
> >>>
> >>> how about binary search of each element from array 1 on array 2?
> >>> overall complexity : O(nlogn)
> >>>
> >>> On 14 August 2011 18:46, mohit verma  wrote:
> 
>  example:
>   array 1 :: 1 2 3 4 5 6 7  8 9 10 15
>   array 2::  23 34 56 13  "15"  57 432  348
> 
>  On Sun, Aug 14, 2011 at 6:44 PM, shady  wrote:
> >
> > meaning ? what is a common element ? example ???
> >
> > On Sun, Aug 14, 2011 at 6:37 PM, mohit verma 
> > wrote:
> >>
> >> given two arrays : with all distinct elements but one element in
> >> common. Find the common element in optimal time.
> >>
> >> --
> >> 
> >> MOHIT VERMA
> >>
> >> --
> >> 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.
> >> 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 algogeeks@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.
> 
> 
> 
>  --
>  
>  MOHIT VERMA
> 
>  --
>  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.
>  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.
> >>>
> >>>
> >>>
> >>> --
> >>>
> >>>
> ___
> >>>
> >>> Please do not print this e-mail until urgent requirement. Go Green!!
> >>> Save Papers <=> Save Trees
> >>>
> >>> --
> >>> 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.
> >>> 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.
> >>
> >>
> >>
> >> --
> >> Regards
> >> SAGAR PAREEK
> >> COMPUTER SCIENCE AND ENGINEERING
> >> NIT ALLAHABAD
> >>
> >> --
> >> 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.
> >> 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 algogeeks@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 algogeeks@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 mess

Re: [algogeeks] array question

[Nikhil Veliath]

i feel binary search idea is the best

guys i am having problem in finding out complexity...here is my
solution to the above problem...whats the complexity...

sort the 2 arraysa and b

l=0,i=0,flag=0;
while(a[i]=b[j])
{
if(a[i]==b[j])
{
printf("Common element is %d",a[i]);
flag=1
break;
}
j++;
l=j;
}
if(flag==1)
break;
}


On Sun, Aug 14, 2011 at 6:55 PM, shady  wrote:
> @sagar suppose numbers are very large( > 10^9) , how will you hash then ?
> can you please state the hashing function in this case
>
> On Sun, Aug 14, 2011 at 6:50 PM, sagar pareek  wrote:
>>
>> Hashing
>> O(n+m)
>>
>> On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro 
>> wrote:
>>>
>>> how about binary search of each element from array 1 on array 2?
>>> overall complexity : O(nlogn)
>>>
>>> On 14 August 2011 18:46, mohit verma  wrote:

 example:
  array 1 :: 1 2 3 4 5 6 7  8 9 10 15
  array 2::  23 34 56 13  "15"  57 432  348

 On Sun, Aug 14, 2011 at 6:44 PM, shady  wrote:
>
> meaning ? what is a common element ? example ???
>
> On Sun, Aug 14, 2011 at 6:37 PM, mohit verma 
> wrote:
>>
>> given two arrays : with all distinct elements but one element in
>> common. Find the common element in optimal time.
>>
>> --
>> 
>> MOHIT VERMA
>>
>> --
>> 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.
>> 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 algogeeks@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.



 --
 
 MOHIT VERMA

 --
 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.
 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.
>>>
>>>
>>>
>>> --
>>>
>>> ___
>>>
>>> Please do not print this e-mail until urgent requirement. Go Green!!
>>> Save Papers <=> Save Trees
>>>
>>> --
>>> 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.
>>> 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.
>>
>>
>>
>> --
>> Regards
>> SAGAR PAREEK
>> COMPUTER SCIENCE AND ENGINEERING
>> NIT ALLAHABAD
>>
>> --
>> 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.
>> 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 algogeeks@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 algogeeks@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] array question

[shady]

@sagar suppose numbers are very large( > 10^9) , how will you hash then ?
can you please state the hashing function in this case

On Sun, Aug 14, 2011 at 6:50 PM, sagar pareek  wrote:

> Hashing
> O(n+m)
>
>
> On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro wrote:
>
>> how about binary search of each element from array 1 on array 2?
>>
>> overall complexity : O(nlogn)
>>
>> On 14 August 2011 18:46, mohit verma  wrote:
>>
>>> example:
>>>  array 1 :: 1 2 3 4 5 6 7  8 9 10 15
>>>  array 2::  23 34 56 13  "15"  57 432  348
>>>
>>>
>>> On Sun, Aug 14, 2011 at 6:44 PM, shady  wrote:
>>>
 meaning ? what is a common element ? example ???

 On Sun, Aug 14, 2011 at 6:37 PM, mohit verma wrote:

> given two arrays : with all distinct elements but one element in
> common. Find the common element in optimal time.
>
> --
> 
> *MOHIT VERMA*
>
>  --
> 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.
> 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 algogeeks@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.

>>>
>>>
>>>
>>> --
>>> 
>>> *MOHIT VERMA*
>>>
>>>  --
>>> 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.
>>> 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.
>>>
>>
>>
>>
>> --
>>
>> ___
>>
>> Please do not print this e-mail until urgent requirement. Go Green!!
>> Save Papers <=> Save Trees
>>
>> --
>> 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.
>> 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.
>>
>
>
>
> --
> **Regards
> SAGAR PAREEK
> COMPUTER SCIENCE AND ENGINEERING
> NIT ALLAHABAD
>
>  --
> 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.
> 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 algogeeks@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] array question

[Dipankar Patro]

@ Sagar:
What if extra space in not allowed?
I think then we have to use the binary search method...

On 14 August 2011 18:50, sagar pareek  wrote:

> Hashing
> O(n+m)
>
>
> On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro wrote:
>
>> how about binary search of each element from array 1 on array 2?
>>
>> overall complexity : O(nlogn)
>>
>> On 14 August 2011 18:46, mohit verma  wrote:
>>
>>> example:
>>>  array 1 :: 1 2 3 4 5 6 7  8 9 10 15
>>>  array 2::  23 34 56 13  "15"  57 432  348
>>>
>>>
>>> On Sun, Aug 14, 2011 at 6:44 PM, shady  wrote:
>>>
 meaning ? what is a common element ? example ???

 On Sun, Aug 14, 2011 at 6:37 PM, mohit verma wrote:

> given two arrays : with all distinct elements but one element in
> common. Find the common element in optimal time.
>
> --
> 
> *MOHIT VERMA*
>
>  --
> 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.
> 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 algogeeks@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.

>>>
>>>
>>>
>>> --
>>> 
>>> *MOHIT VERMA*
>>>
>>>  --
>>> 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.
>>> 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.
>>>
>>
>>
>>
>> --
>>
>> ___
>>
>> Please do not print this e-mail until urgent requirement. Go Green!!
>> Save Papers <=> Save Trees
>>
>> --
>> 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.
>> 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.
>>
>
>
>
> --
> **
> Regards
> SAGAR PAREEK
> COMPUTER SCIENCE AND ENGINEERING
> NIT ALLAHABAD
>
>  --
> 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.
> 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.
>



-- 
___

Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees

-- 
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.
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] array question

[sagar pareek]

Hashing
O(n+m)

On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro  wrote:

> how about binary search of each element from array 1 on array 2?
>
> overall complexity : O(nlogn)
>
> On 14 August 2011 18:46, mohit verma  wrote:
>
>> example:
>>  array 1 :: 1 2 3 4 5 6 7  8 9 10 15
>>  array 2::  23 34 56 13  "15"  57 432  348
>>
>>
>> On Sun, Aug 14, 2011 at 6:44 PM, shady  wrote:
>>
>>> meaning ? what is a common element ? example ???
>>>
>>> On Sun, Aug 14, 2011 at 6:37 PM, mohit verma wrote:
>>>
 given two arrays : with all distinct elements but one element in common.
 Find the common element in optimal time.

 --
 
 *MOHIT VERMA*

  --
 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.
 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 algogeeks@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.
>>>
>>
>>
>>
>> --
>> 
>> *MOHIT VERMA*
>>
>>  --
>> 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.
>> 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.
>>
>
>
>
> --
>
> ___
>
> Please do not print this e-mail until urgent requirement. Go Green!!
> Save Papers <=> Save Trees
>
> --
> 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.
> 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.
>



-- 
**Regards
SAGAR PAREEK
COMPUTER SCIENCE AND ENGINEERING
NIT ALLAHABAD

-- 
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.
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] array question

[Dipankar Patro]

how about binary search of each element from array 1 on array 2?

overall complexity : O(nlogn)

On 14 August 2011 18:46, mohit verma  wrote:

> example:
>  array 1 :: 1 2 3 4 5 6 7  8 9 10 15
>  array 2::  23 34 56 13  "15"  57 432  348
>
>
> On Sun, Aug 14, 2011 at 6:44 PM, shady  wrote:
>
>> meaning ? what is a common element ? example ???
>>
>> On Sun, Aug 14, 2011 at 6:37 PM, mohit verma wrote:
>>
>>> given two arrays : with all distinct elements but one element in common.
>>> Find the common element in optimal time.
>>>
>>> --
>>> 
>>> *MOHIT VERMA*
>>>
>>>  --
>>> 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.
>>> 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 algogeeks@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.
>>
>
>
>
> --
> 
> *MOHIT VERMA*
>
>  --
> 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.
> 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.
>



-- 
___

Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers <=> Save Trees

-- 
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.
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] array question

[mohit verma]

example:
 array 1 :: 1 2 3 4 5 6 7  8 9 10 15
 array 2::  23 34 56 13  "15"  57 432  348

On Sun, Aug 14, 2011 at 6:44 PM, shady  wrote:

> meaning ? what is a common element ? example ???
>
> On Sun, Aug 14, 2011 at 6:37 PM, mohit verma wrote:
>
>> given two arrays : with all distinct elements but one element in common.
>> Find the common element in optimal time.
>>
>> --
>> 
>> *MOHIT VERMA*
>>
>>  --
>> 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.
>> 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 algogeeks@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.
>



-- 

*MOHIT VERMA*

-- 
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.
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] array question

[shady]

meaning ? what is a common element ? example ???

On Sun, Aug 14, 2011 at 6:37 PM, mohit verma  wrote:

> given two arrays : with all distinct elements but one element in common.
> Find the common element in optimal time.
>
> --
> 
> *MOHIT VERMA*
>
>  --
> 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.
> 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 algogeeks@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] Array question: Detect whether a circular chain with all elements can be formed

[Piyush Kapoor]

Maybe you are looking for this:http://www.codechef.com/problems/WORDS1

On Sat, Aug 13, 2011 at 10:25 PM, Kamakshii Aggarwal
wrote:

> i got error,my sol will not work for all cases
>
>
> On Sat, Aug 13, 2011 at 10:22 PM, Kamakshii Aggarwal <
> kamakshi...@gmail.com> wrote:
>
>> see the following example:
>> *a*kdhd*a* ,*b*hdgd*c*, *c*hdjd*b*
>>
>>
>> On Sat, Aug 13, 2011 at 10:20 PM, Yasir  wrote:
>>
>>> why following?
>>>
>>> if(first==last)
>>> return false;
>>>
>>>
>>> example:
>>> axxa,  ayyb, bzza  ===>  ayybbzzaaxxa
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To view this discussion on the web visit
>>> https://groups.google.com/d/msg/algogeeks/-/iONquZUgbPkJ.
>>>
>>> To post to this group, send email to algogeeks@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.
>>>
>>
>>
>>
>> --
>> Regards,
>> Kamakshi
>> kamakshi...@gmail.com
>>
>
>
>
> --
> Regards,
> Kamakshi
> kamakshi...@gmail.com
>
> --
> 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.
> 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.
>



-- 
*Regards,*
*Piyush Kapoor,*
*2nd year,CSE
IT-BHU*

-- 
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.
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] Array question: Detect whether a circular chain with all elements can be formed

[Kamakshii Aggarwal]

i got error,my sol will not work for all cases

On Sat, Aug 13, 2011 at 10:22 PM, Kamakshii Aggarwal
wrote:

> see the following example:
> *a*kdhd*a* ,*b*hdgd*c*, *c*hdjd*b*
>
>
> On Sat, Aug 13, 2011 at 10:20 PM, Yasir  wrote:
>
>> why following?
>>
>> if(first==last)
>> return false;
>>
>>
>> example:
>> axxa,  ayyb, bzza  ===>  ayybbzzaaxxa
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/iONquZUgbPkJ.
>>
>> To post to this group, send email to algogeeks@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.
>>
>
>
>
> --
> Regards,
> Kamakshi
> kamakshi...@gmail.com
>



-- 
Regards,
Kamakshi
kamakshi...@gmail.com

-- 
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.
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] Array question: Detect whether a circular chain with all elements can be formed

[Kamakshii Aggarwal]

see the following example:
*a*kdhd*a* ,*b*hdgd*c*, *c*hdjd*b*


On Sat, Aug 13, 2011 at 10:20 PM, Yasir  wrote:

> why following?
>
> if(first==last)
> return false;
>
>
> example:
> axxa,  ayyb, bzza  ===>  ayybbzzaaxxa
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/iONquZUgbPkJ.
>
> To post to this group, send email to algogeeks@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.
>



-- 
Regards,
Kamakshi
kamakshi...@gmail.com

-- 
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.
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] Array question: Detect whether a circular chain with all elements can be formed

[Yasir]

why following? 

if(first==last)
return false;

 
example: 
axxa,  ayyb, bzza  ===>  ayybbzzaaxxa

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/iONquZUgbPkJ.
To post to this group, send email to algogeeks@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] Array question: Detect whether a circular chain with all elements can be formed

[Kamakshii Aggarwal]

maintain an array indexed on alphabets 'a' to  'z'.
now count the occurence of each character taking *last character* of each
string
{"asdsb","csasaa", "bc", bc"}
in this case
arr[a]=1;
arr[b]=1;
arr[c]=2;

now start with each sting let first character be first and last character be
last
while (strings)
{
if(arr[first ]==0)
return false;

if(arr[first]==1)
{
if(first==last)
return false;
}

else{
arr[first--];
}
}/*end while
if at the end all elements of arr =0 then return true
 else
return false;








On Sat, Aug 13, 2011 at 9:44 PM, Yasir  wrote:

> An array of strings is given and you have to find out whether a circular
> chain with all character can be formed or not?
> Circular chain is formed in way that:   if last char of a string is equal
> to first char of another string then it can be joined.:
> like ab  bxc  ===>   axbbxc  (Notice that it got joined at
> b)
>
> example
>  {"asdsb","csasaa", "bc"}
> Answer:   TRUE
>
>  {"asdsb","csasaa", "bc", bc"}
> Answer: FALSE
>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/WGN5GLyIP_QJ.
> To post to this group, send email to algogeeks@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.
>



-- 
Regards,
Kamakshi
kamakshi...@gmail.com

-- 
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.
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] Array question

[ankit sambyal]

The O/P of ur example should be 2,2,1,1,1,-1,-1
or am I getting it wrong ??

-- 
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.
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] Array question

[Piyush Sinha]

Sorry for the above mistakeits not O(n)

On Tue, Jul 26, 2011 at 5:29 PM, Piyush Sinha wrote:

> Use stack
>
>
> On Tue, Jul 26, 2011 at 5:22 PM, Shikhar  wrote:
>
>> Given an array of integers, for each element of the array, print the
>> first number on the right side of the element which is smaller than
>> it. print -1 is there is no such element.
>>
>> eg: 3,4,2,18,19,1,10
>>
>> Ans: 2,2,1,10,10,-1,-1
>> O(n^2) solution is trivial.
>>
>> One solution could be:
>> Insert the elements of the array in a binary search tree. The moment a
>> node in the binary tree gets a left child, it is the element we are
>> looking for. All the nodes in the right subtree of a node which has
>> just received a left child can be assigned the value of the parents'
>> left child as the first smaller element to the right.
>> Thus, this solution is O(nlogn).
>>
>> Does this solution work for all possible cases of input?
>>
>> Is an O(n) solution possible?
>>
>> --
>> 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.
>> 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.
>>
>>
>
>
> --
> *Piyush Sinha*
> *IIIT, Allahabad*
> *+91-7483122727*
> *  "NEVER SAY
> NEVER"
> *
>
>


-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-7483122727*
*  "NEVER SAY
NEVER"
*

-- 
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.
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] Array question

[Piyush Sinha]

Use stack

On Tue, Jul 26, 2011 at 5:22 PM, Shikhar  wrote:

> Given an array of integers, for each element of the array, print the
> first number on the right side of the element which is smaller than
> it. print -1 is there is no such element.
>
> eg: 3,4,2,18,19,1,10
>
> Ans: 2,2,1,10,10,-1,-1
> O(n^2) solution is trivial.
>
> One solution could be:
> Insert the elements of the array in a binary search tree. The moment a
> node in the binary tree gets a left child, it is the element we are
> looking for. All the nodes in the right subtree of a node which has
> just received a left child can be assigned the value of the parents'
> left child as the first smaller element to the right.
> Thus, this solution is O(nlogn).
>
> Does this solution work for all possible cases of input?
>
> Is an O(n) solution possible?
>
> --
> 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.
> 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.
>
>


-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-7483122727*
*  "NEVER SAY
NEVER"
*

-- 
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.
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] Array Question

[Balaji Ramani]

Here are two methods to do in O(n^2)

1) Insert elements of first array in hash and then for every pair of
elements in (Bj, Ck) find if -(Bj + Ck) is in hash

2) Without extra space:

sort arrays A and B

now for each element in Ck find a pair (Ai, Bj) which sums to -Ck as below

let p1 point to first element in A
let p2 point to last element in B

if p1 + p2 < -Ck move p1 one step to right
if p1 + p2 > -Ck move p2 one step left
if ( p1 + p2 == -Ck ) return triplet

Thanks,
Balaji.

On Thu, Feb 17, 2011 at 11:42 PM, jalaj jaiswal
wrote:

> i have a n^2logn solution
>
> sort the third array,.. then for every pair in a and b search for the
> number which makes the sum zero using binary search
>
>
> but guess a better soln must exist
>
>
> On Thu, Feb 17, 2011 at 11:38 PM, bittu wrote:
>
>> We have three arrays
>> A=[a1,a2,...an]
>> B=[b1,b2,...bn]
>> C=[c1,c2,...cn]
>>
>> Write a method which takes these three arrays as input and return true
>> if there is a combination [ai,bj,ck] such that ai+bj+ck = 0.
>>
>> O(n^3) solution is obvious. The questions is can we do better than
>> this?
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>>
>> Thanks & Regards
>> Shashank Mani
>>
>> --
>> 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.
>> 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.
>>
>>
>
>
> --
> With Regards,
> *Jalaj Jaiswal* (+919019947895)
> Software developer, Cisco Systems
> B.Tech IIIT ALLAHABAD
>
>  --
> 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.
> 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 algogeeks@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] Array Question

[jalaj jaiswal]

i have a n^2logn solution

sort the third array,.. then for every pair in a and b search for the number
which makes the sum zero using binary search


but guess a better soln must exist

On Thu, Feb 17, 2011 at 11:38 PM, bittu  wrote:

> We have three arrays
> A=[a1,a2,...an]
> B=[b1,b2,...bn]
> C=[c1,c2,...cn]
>
> Write a method which takes these three arrays as input and return true
> if there is a combination [ai,bj,ck] such that ai+bj+ck = 0.
>
> O(n^3) solution is obvious. The questions is can we do better than
> this?
>
>
>
>
>
>
>
>
>
>
>
> Thanks & Regards
> Shashank Mani
>
> --
> 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.
> 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.
>
>


-- 
With Regards,
*Jalaj Jaiswal* (+919019947895)
Software developer, Cisco Systems
B.Tech IIIT ALLAHABAD

-- 
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.
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] array question

[Sathaiah Dontula]

I think you can use heap.

Thanks,
Sathaiah

On Wed, Jul 21, 2010 at 12:06 PM, divya  wrote:

> Given an array A of N elements, where N approaches infinity, there are
> S elements in it where S< does not exist in A[0S-1].
>
> --
> 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] array question

[sharad kumar]

#include
#include
#include
using namespace std;
int main()
{
int arr[5]={12,3,4,3,3};
mapmp;
int i=0;
for(i=0;i<5;++i)
{
if(!(mp[arr[i]]))
mp[arr[i]]=i;
else
continue;
}
  map::iterator it;
  for(it=mp.begin();it!=mp.end();++it)
  cout @sharad
> while storing each element in hash by your approach u ll check if its
> already there in hash. so the complexity here will be O(n2). correct me if i
> m wrong. isnt there ny better algo..?
>
> On 6 June 2010 06:28, sharad kumar  wrote:
>
>> @dhivya:keep storing the first occurance element index in hash map and
>> then start insertin eleement based on index position
>>
>>
>> On Sun, Jun 6, 2010 at 12:31 AM, divya  wrote:
>>
>>> Given an array with some repeating numbers. Like 12,6,5,12,6
>>>
>>> output: 12,12,6,6,5
>>> 12 shud come before 6 since it is earlier in list. So cant use a
>>> dictionary.
>>>
>>> --
>>> 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.
>>>
>>>
>>
>>
>> --
>> yezhu malai vaasa venkataramana Govinda Govinda
>>
>>  --
>> 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.
>



-- 
yezhu malai vaasa venkataramana Govinda Govinda

-- 
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] array question

[Rohit Saraf]

No it will be O(n).

--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14



>

-- 
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] array question

[divya jain]

@sharad
while storing each element in hash by your approach u ll check if its
already there in hash. so the complexity here will be O(n2). correct me if i
m wrong. isnt there ny better algo..?

On 6 June 2010 06:28, sharad kumar  wrote:

> @dhivya:keep storing the first occurance element index in hash map and then
> start insertin eleement based on index position
>
>
> On Sun, Jun 6, 2010 at 12:31 AM, divya  wrote:
>
>> Given an array with some repeating numbers. Like 12,6,5,12,6
>>
>> output: 12,12,6,6,5
>> 12 shud come before 6 since it is earlier in list. So cant use a
>> dictionary.
>>
>> --
>> 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.
>>
>>
>
>
> --
> yezhu malai vaasa venkataramana Govinda Govinda
>
>  --
> 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] array question

[sharad kumar]

@dhivya:keep storing the first occurance element index in hash map and then
start insertin eleement based on index position

On Sun, Jun 6, 2010 at 12:31 AM, divya  wrote:

> Given an array with some repeating numbers. Like 12,6,5,12,6
>
> output: 12,12,6,6,5
> 12 shud come before 6 since it is earlier in list. So cant use a
> dictionary.
>
> --
> 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.
>
>


-- 
yezhu malai vaasa venkataramana Govinda Govinda

-- 
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.