Re: [algogeeks] Array of intergers with repeating elements

[Kalyanasundaram]

Check this out. The first answer is the most efficient one. You find each
bit of the number, by using modulo operator.

http://stackoverflow.com/questions/9442958/find-the-element-occurring-b-times-in-an-an-array-of-size-nkb


On Wed, May 8, 2013 at 2:40 PM, Nishant Pandey  wrote:

> i think u should utilize the property of XOR, this would help.
>
>
> On Wed, May 8, 2013 at 12:02 AM, MAC  wrote:
>
>>
>> I was asked this in recent amazon onsite interview and asked o write code
>>
>> Given an Array of integers . N elements occur k times and one element
>> occurs b times, in other words there are n+1 distinct Elements. Given
>> that 0 < b < k find the element occurring b times.
>>
>> We know k is NOT even .
>>
>>
>> thanks
>> --mac
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>>
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>



-- 
*
**
*

*Kalyan*

*Don't take life seriously as it isn't permanent!*
*
*

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Array of intergers with repeating elements

[bharat b]

@ Jatin : N elements occur k times -> there are N distinct elements and
total of N*k elements..
one element occurs b times -> there are b elements and one distinct element
..
 totally N+1 distinct elements and N*k + b elements are there ...

On Wed, May 8, 2013 at 1:14 AM, jatin luthra wrote:

> "N elements occur k times and one element occurs b times, in other words
> there are n+1 distinct Elements"
> didn't get this statement
>
>
> On Wed, May 8, 2013 at 12:02 AM, MAC  wrote:
>
>>
>> I was asked this in recent amazon onsite interview and asked o write code
>>
>> Given an Array of integers . N elements occur k times and one element
>> occurs b times, in other words there are n+1 distinct Elements. Given
>> that 0 < b < k find the element occurring b times.
>>
>> We know k is NOT even .
>>
>>
>> thanks
>> --mac
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To unsubscribe from this group and stop receiving emails from it, send an
>> email to algogeeks+unsubscr...@googlegroups.com.
>>
>>
>>
>
>
>
> --
>
>
>
>
>
> ---jatin
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Array of intergers with repeating elements

[Ankit Sambyal]

Are these n+1 elements range from 1 to n+1 ?



On Wed, May 8, 2013 at 12:02 AM, MAC  wrote:

>
> I was asked this in recent amazon onsite interview and asked o write code
>
> Given an Array of integers . N elements occur k times and one element
> occurs b times, in other words there are n+1 distinct Elements. Given
> that 0 < b < k find the element occurring b times.
>
> We know k is NOT even .
>
>
> thanks
> --mac
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Array of intergers with repeating elements

[Nishant Pandey]

i think u should utilize the property of XOR, this would help.


On Wed, May 8, 2013 at 12:02 AM, MAC  wrote:

>
> I was asked this in recent amazon onsite interview and asked o write code
>
> Given an Array of integers . N elements occur k times and one element
> occurs b times, in other words there are n+1 distinct Elements. Given
> that 0 < b < k find the element occurring b times.
>
> We know k is NOT even .
>
>
> thanks
> --mac
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Array of intergers with repeating elements

[jatin luthra]

"N elements occur k times and one element occurs b times, in other words
there are n+1 distinct Elements"
didn't get this statement


On Wed, May 8, 2013 at 12:02 AM, MAC  wrote:

>
> I was asked this in recent amazon onsite interview and asked o write code
>
> Given an Array of integers . N elements occur k times and one element
> occurs b times, in other words there are n+1 distinct Elements. Given
> that 0 < b < k find the element occurring b times.
>
> We know k is NOT even .
>
>
> thanks
> --mac
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
>
>



-- 





---jatin

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Array Problem

[manish untwal]

@wladimir yes the problem seems to be that!!

On Tue, Dec 11, 2012 at 10:13 AM, Wladimir Tavares wrote:

> subset sum?
> Wladimir Araujo Tavares
> *Federal University of Ceará 
> Homepage  | 
> Maratona|
> *
>
>
>
>
>
> On Fri, Nov 16, 2012 at 2:46 AM, Pralay Biswas  > wrote:
>
>> Search for balance partitioning under Dynamic Programming. Doable in O(n)
>>
>>
>> On Thu, Nov 15, 2012 at 8:16 PM, bharat b 
>> wrote:
>>
>>> @ vishal : how can u divide an array into 2 groups whose difference is
>>> maximum in O(1). why max?
>>>
>>> solution : http://www.youtube.com/watch?v=GdnpQY2j064
>>>
>>>
>>>
>>>
>>> On Fri, Nov 16, 2012 at 9:22 AM, vishal chaudhary <
>>> vishal.cs.b...@gmail.com> wrote:
>>>
 Hi
 you can first sort the array which can be done in O(nlogn) complexity
 if the number of items in the array is n.
 Then using the indexing of arrays you can divide the array into two
 groups whose difference is going to be maximum and this can be done in O(1)
 complexity.
 So the complete algorithm is going to take O(nlogn) complexity.
 Kindly share an alternative algorithm if you find  one with lower
 complexity.

 Vishal


 On Wed, Nov 7, 2012 at 7:43 PM, Arun Kindra <
 reserve4placem...@gmail.com> wrote:

> Given an unsorted array, how to divide them into two equal arrays
> whose difference of sum is minimum.
>
> --
> 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.
>>>
>>
>>  --
>>
>>
>>
>
>  --
>
>
>



-- 
With regards,
Manish kumar untwal
Indian Institute of Information Technology
Allahabad (2009-2013 batch)

-- 

Re: [algogeeks] Array Problem

[Wladimir Tavares]

subset sum?
Wladimir Araujo Tavares
*Federal University of Ceará 
Homepage  |
Maratona|
*





On Fri, Nov 16, 2012 at 2:46 AM, Pralay Biswas
wrote:

> Search for balance partitioning under Dynamic Programming. Doable in O(n)
>
>
> On Thu, Nov 15, 2012 at 8:16 PM, bharat b wrote:
>
>> @ vishal : how can u divide an array into 2 groups whose difference is
>> maximum in O(1). why max?
>>
>> solution : http://www.youtube.com/watch?v=GdnpQY2j064
>>
>>
>>
>>
>> On Fri, Nov 16, 2012 at 9:22 AM, vishal chaudhary <
>> vishal.cs.b...@gmail.com> wrote:
>>
>>> Hi
>>> you can first sort the array which can be done in O(nlogn) complexity if
>>> the number of items in the array is n.
>>> Then using the indexing of arrays you can divide the array into two
>>> groups whose difference is going to be maximum and this can be done in O(1)
>>> complexity.
>>> So the complete algorithm is going to take O(nlogn) complexity.
>>> Kindly share an alternative algorithm if you find  one with lower
>>> complexity.
>>>
>>> Vishal
>>>
>>>
>>> On Wed, Nov 7, 2012 at 7:43 PM, Arun Kindra >> > wrote:
>>>
 Given an unsorted array, how to divide them into two equal arrays whose
 difference of sum is minimum.

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

[Dave]

@Ansum: Notice that the problem does not ask to give a method of making as 
many numbers as possible equal, but only what the maximum number is. Here 
is an algorithm for achieving an array with the equality numbers I 
specified:
 
1. If the sum of the numbers is a multiple of n, then avg = sum/n is the 
target number. If every number is not equal to avg, find a number a[i] in 
the array that is smaller than avg and a number a[j] that is larger than 
avg. Then set a[i] = a[i]+1 and a[j] = a[j]-1. Repeat until every number 
equals avg. Result is that n numbers are equal.
 
2. If the sum of the numbers is not a multiple of n, pick any number, say 
a[1], as the target value. If there is any number a[k] from k = 2 to n-1 
such that a[k] != a[1], increase or decrease a[k] by 1 to make it closer to 
a[1] and respectively decrease or increase a[n] by 1. Repeat until every 
number a[k] = a[1] for k = 2 to n-1. Then a[1] to a[n-1] are equal but a[n] 
cannot be equal because then the sum of the numbers would be a multiple of 
n. Result is that n-1 numbers are equal.
 
Since you don't have to produce the maximally equal array, the algorithm I 
gave is the solution. Here it is in code (with C's 0-based array indexing):
 
int maxEqual( int n, int a[])
{
int i, sum = 0;
for( i = 0 ; i < n ; ++i )
sum += a[i];
return if sum % n == 0 ? n : n - 1;
}
 
Dave

On Thursday, November 22, 2012 1:25:43 AM UTC-6, Ansum Baid wrote:

> @Dave: Can you give a little insight on your approach?
>
> On Wed, Nov 21, 2012 at 6:52 PM, Dave  >wrote:
>
>> @Ansum: Polycarpus should start by summing the numbers. If the sum is 
>> divisible by n, then n numbers can be made equal. If the sum is not 
>> divisible by n, then only n-1 numbers can be made equal.
>>  
>> Dave
>>
>> On Wednesday, November 21, 2012 12:18:54 PM UTC-6, Ansum Baid wrote:
>>
>>>  This question has been taken from codeforces.com. Any idea how to 
>>> solve this ?
>>>
>>> Polycarpus has an array, consisting of *n* integers *a*1, *a*2, ..., *a*
>>> *n*. Polycarpus likes it when numbers in an array match. That's why he 
>>> wants the array to have as many equal numbers as possible. For that 
>>> Polycarpus performs the following operation multiple times:
>>>
>>>
>>>- he chooses two elements of the array *a**i*, *a**j* (*i* ≠ *j*); 
>>>- he simultaneously increases number *a**i* by 1 and decreases 
>>>number *a**j* by 1, that is, executes *a**i* = *a**i* + 1 and *a**j*= 
>>>*a**j* - 1. 
>>>
>>> The given operation changes exactly two distinct array elements. 
>>> Polycarpus can apply the described operation an infinite number of times.
>>>
>>> Now he wants to know what maximum number of equal array elements he can 
>>> get if he performs an arbitrary number of such operation. Help Polycarpus.
>>> Input
>>>
>>> The first line contains integer *n* (1 ≤ *n* ≤ 105) — the array size. 
>>> The second line contains space-separated integers *a*1, *a*2, ..., *a**n
>>> * (|*a**i*| ≤ 104) — the original array.
>>> Output
>>>
>>> Print a single integer — the maximum number of equal array elements he 
>>> can get if he performs an arbitrary number of the given operation.
>>> Sample test(s)
>>>  input
>>>
>>> 2
>>> 2 1
>>>
>>> output
>>>
>>> 1
>>>
>>> input
>>>
>>> 3
>>> 1 4 1
>>>
>>> output
>>>
>>> 3
>>>
>>>
>>>  -- 
>>  
>>  
>>
>
>

-- 

Re: [algogeeks] Array problem

[Ansum Baid]

@Dave: Can you give a little insight on your approach?

On Wed, Nov 21, 2012 at 6:52 PM, Dave  wrote:

> @Ansum: Polycarpus should start by summing the numbers. If the sum is
> divisible by n, then n numbers can be made equal. If the sum is not
> divisible by n, then only n-1 numbers can be made equal.
>
> Dave
>
> On Wednesday, November 21, 2012 12:18:54 PM UTC-6, Ansum Baid wrote:
>
>>  This question has been taken from codeforces.com. Any idea how to solve
>> this ?
>>
>> Polycarpus has an array, consisting of *n* integers *a*1, *a*2, ..., *a**
>> n*. Polycarpus likes it when numbers in an array match. That's why he
>> wants the array to have as many equal numbers as possible. For that
>> Polycarpus performs the following operation multiple times:
>>
>>
>>- he chooses two elements of the array *a**i*, *a**j* (*i* ≠ *j*);
>>- he simultaneously increases number *a**i* by 1 and decreases number
>>*a**j* by 1, that is, executes *a**i* = *a**i* + 1 and *a**j* = *a**j*- 1
>>.
>>
>> The given operation changes exactly two distinct array elements.
>> Polycarpus can apply the described operation an infinite number of times.
>>
>> Now he wants to know what maximum number of equal array elements he can
>> get if he performs an arbitrary number of such operation. Help Polycarpus.
>> Input
>>
>> The first line contains integer *n* (1 ≤ *n* ≤ 105) — the array size.
>> The second line contains space-separated integers *a*1, *a*2, ..., *a**n*
>>  (|*a**i*| ≤ 104) — the original array.
>> Output
>>
>> Print a single integer — the maximum number of equal array elements he
>> can get if he performs an arbitrary number of the given operation.
>> Sample test(s)
>>  input
>>
>> 2
>> 2 1
>>
>> output
>>
>> 1
>>
>> input
>>
>> 3
>> 1 4 1
>>
>> output
>>
>> 3
>>
>>
>>  --
>
>
>

-- 

Re: [algogeeks] Array problem

[Dave]

@Ansum: Polycarpus should start by summing the numbers. If the sum is 
divisible by n, then n numbers can be made equal. If the sum is not 
divisible by n, then only n-1 numbers can be made equal.
 
Dave

On Wednesday, November 21, 2012 12:18:54 PM UTC-6, Ansum Baid wrote:

>  This question has been taken from codeforces.com. Any idea how to solve 
> this ?
>
> Polycarpus has an array, consisting of *n* integers *a*1, *a*2, ..., *a**n
> *. Polycarpus likes it when numbers in an array match. That's why he 
> wants the array to have as many equal numbers as possible. For that 
> Polycarpus performs the following operation multiple times:
>
>
>- he chooses two elements of the array *a**i*, *a**j* (*i* ≠ *j*); 
>- he simultaneously increases number *a**i* by 1 and decreases number *
>a**j* by 1, that is, executes *a**i* = *a**i* + 1 and *a**j* = *a**j*- 1
>. 
>
> The given operation changes exactly two distinct array elements. 
> Polycarpus can apply the described operation an infinite number of times.
>
> Now he wants to know what maximum number of equal array elements he can 
> get if he performs an arbitrary number of such operation. Help Polycarpus.
> Input
>
> The first line contains integer *n* (1 ≤ *n* ≤ 105) — the array size. The 
> second line contains space-separated integers *a*1, *a*2, ..., *a**n* (|*a
> **i*| ≤ 104) — the original array.
> Output
>
> Print a single integer — the maximum number of equal array elements he can 
> get if he performs an arbitrary number of the given operation.
> Sample test(s)
>  input
>
> 2
> 2 1
>
> output
>
> 1
>
> input
>
> 3
> 1 4 1
>
> output
>
> 3
>
>
>

-- 

Re: [algogeeks] Array Problem

[bharat b]

@ vishal :let array be {5,2,1,1} ==> as per u'r algo =>{1,2},{1,5} are sets
difference is 3 .. but the sol is {5}{1,1,2} ==> diff = 1;

On Fri, Nov 16, 2012 at 10:12 AM, vishal chaudhary  wrote:

> Hi
> Sorry for that as i misinterpreted the question.
> for the difference to be minimum, i think(not completely sure) we can
> first sort the array
> and then we can start putting the elements at even index in the last part
> of the array and the odd ones in the starting in the new array
> you can do this in the same array itself i guess but you have to do some
> kind of shifting.
> by doing this for all the elements and dividing them into two groups.
> I hope this helps.
>
> Vishal
>
>
>
> On Fri, Nov 16, 2012 at 9:46 AM, bharat b wrote:
>
>> @ vishal : how can u divide an array into 2 groups whose difference is
>> maximum in O(1). why max?
>>
>> solution : http://www.youtube.com/watch?v=GdnpQY2j064
>>
>>
>>
>>
>> On Fri, Nov 16, 2012 at 9:22 AM, vishal chaudhary <
>> vishal.cs.b...@gmail.com> wrote:
>>
>>> Hi
>>> you can first sort the array which can be done in O(nlogn) complexity if
>>> the number of items in the array is n.
>>> Then using the indexing of arrays you can divide the array into two
>>> groups whose difference is going to be maximum and this can be done in O(1)
>>> complexity.
>>> So the complete algorithm is going to take O(nlogn) complexity.
>>> Kindly share an alternative algorithm if you find  one with lower
>>> complexity.
>>>
>>> Vishal
>>>
>>>
>>> On Wed, Nov 7, 2012 at 7:43 PM, Arun Kindra >> > wrote:
>>>
 Given an unsorted array, how to divide them into two equal arrays whose
 difference of sum is minimum.

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

[vishal chaudhary]

Hi
Sorry for that as i misinterpreted the question.
for the difference to be minimum, i think(not completely sure) we can first
sort the array
and then we can start putting the elements at even index in the last part
of the array and the odd ones in the starting in the new array
you can do this in the same array itself i guess but you have to do some
kind of shifting.
by doing this for all the elements and dividing them into two groups.
I hope this helps.

Vishal


On Fri, Nov 16, 2012 at 9:46 AM, bharat b wrote:

> @ vishal : how can u divide an array into 2 groups whose difference is
> maximum in O(1). why max?
>
> solution : http://www.youtube.com/watch?v=GdnpQY2j064
>
>
>
>
> On Fri, Nov 16, 2012 at 9:22 AM, vishal chaudhary <
> vishal.cs.b...@gmail.com> wrote:
>
>> Hi
>> you can first sort the array which can be done in O(nlogn) complexity if
>> the number of items in the array is n.
>> Then using the indexing of arrays you can divide the array into two
>> groups whose difference is going to be maximum and this can be done in O(1)
>> complexity.
>> So the complete algorithm is going to take O(nlogn) complexity.
>> Kindly share an alternative algorithm if you find  one with lower
>> complexity.
>>
>> Vishal
>>
>>
>> On Wed, Nov 7, 2012 at 7:43 PM, Arun Kindra 
>> wrote:
>>
>>> Given an unsorted array, how to divide them into two equal arrays whose
>>> difference of sum is minimum.
>>>
>>> --
>>> 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 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 Problem

[bharat b]

@ vishal : how can u divide an array into 2 groups whose difference is
maximum in O(1). why max?

solution : http://www.youtube.com/watch?v=GdnpQY2j064



On Fri, Nov 16, 2012 at 9:22 AM, vishal chaudhary
wrote:

> Hi
> you can first sort the array which can be done in O(nlogn) complexity if
> the number of items in the array is n.
> Then using the indexing of arrays you can divide the array into two groups
> whose difference is going to be maximum and this can be done in O(1)
> complexity.
> So the complete algorithm is going to take O(nlogn) complexity.
> Kindly share an alternative algorithm if you find  one with lower
> complexity.
>
> Vishal
>
>
> On Wed, Nov 7, 2012 at 7:43 PM, Arun Kindra 
> wrote:
>
>> Given an unsorted array, how to divide them into two equal arrays whose
>> difference of sum is minimum.
>>
>> --
>> 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 Problem

[vishal chaudhary]

Hi
you can first sort the array which can be done in O(nlogn) complexity if
the number of items in the array is n.
Then using the indexing of arrays you can divide the array into two groups
whose difference is going to be maximum and this can be done in O(1)
complexity.
So the complete algorithm is going to take O(nlogn) complexity.
Kindly share an alternative algorithm if you find  one with lower
complexity.

Vishal

On Wed, Nov 7, 2012 at 7:43 PM, Arun Kindra wrote:

> Given an unsorted array, how to divide them into two equal arrays whose
> difference of sum is minimum.
>
> --
> 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 problem

[Tushar]

@srikanth
we can use segment trees to get sum of an interval
but there is another condition of sum of distinct numbers only. how can we 
take that into account in a segment tree?

On Thursday, 6 September 2012 17:35:59 UTC+5:30, srikanth reddy malipatel 
wrote:
>
> post the logic not the code!
> BTW this  problem can be done using segment trees.
>
>
> http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor
>  
>
> On Thu, Sep 6, 2012 at 4:51 PM, bharat b 
> > wrote:
>
>> Its better to write an O(n) solution for this problem as the # test cases 
>> are very high and #elements are also very huge..
>> use visited array for distinct numbers ... space--O(n).. time--O(n)
>>
>>
>>  On Sat, Aug 25, 2012 at 2:39 AM, michael miller 
>> 
>> > wrote:
>>
>>> Hi,
>>> You are given N numbers. You have to perform two kinds of operations:
>>> U x y - x-th number becomes equal to y.
>>> Q x y - calculate the sum of distinct numbers from x-th to y-th. It 
>>> means that the sum for the set {1, 2, 3, 2, 7} will be equal to 13 
>>> (1+2+3+7).
>>>
>>> 1<=N<=5 and 
>>> t is the number of test cases where   1<=t<=10
>>>
>>> all numbers fit in the 32 bit integer range...
>>>
>>> suggest some solution..
>>>
>>> here is my solution
>>> but it is giving wrong answer fo some unknown test case...plz suggest me 
>>> the test case where i am getting wrong answer
>>>
>>>
>>> #include
>>> #include
>>> int main()
>>> {
>>> int list[5],i,n,j,sum,k,l;char c;long t;
>>> scanf 
>>> ("%d",&n);
>>> for(i=0;i>> {
>>> scanf 
>>> ("%d",&list[i]);
>>>
>>>
>>> }
>>> scanf 
>>> ("%ld",&t);
>>>
>>>
>>> t=2*t;
>>> while(t)
>>> {
>>> sum=0;
>>> scanf 
>>> ("%c",&c);
>>>
>>>
>>> fflush(stdin);
>>> scanf 
>>> ("%d
>>> %d",&k,&l);   
>>>
>>>
>>> if(c=='Q')
>>> {
>>> for(i=k-1;i>> {
>>> for(j=i+1;j>> {
>>>if(list[i]==list[j])
>>>   break;
>>>else if((j==l-1) &&(list[i]!=list[j]))
>>>
>>>
>>>{
>>>   sum=sum+list[i];
>>>
>>>}
>>> }
>>>  }
>>>
>>>  printf 
>>> ("%d\n",sum+list[l-1]);
>>>
>>>
>>>  }
>>>  if(c=='U')
>>>  {
>>>  list[k-1]=l;
>>>
>>>  }
>>>  t--;
>>> }
>>> return 0;   
>>> }
>>>
>>>
>>>
>>>  -- 
>>> You received this message because you are subscribed to the Google 
>>> Groups "Algorithm Geeks" group.
>>> To post to this group, send email to algo...@googlegroups.com
>>> .
>>> To unsubscribe from this group, send email to 
>>> algogeeks+...@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 algo...@googlegroups.com
>> .
>> To unsubscribe from this group, send email to 
>> algogeeks+...@googlegroups.com .
>> For more options, visit this group at 
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> -- 
> Srikanth Reddy M
> (M.Sc Tech.) Information Systems
> BITS-PILANI
>
>  

-- 
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/-/tBX6PSU32EkJ.
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 problem

[Arman Kamal]

It will be even easier with BIT (Binary Indexed Tree), if you know how to
use it.

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

[srikanth reddy malipatel]

post the logic not the code!
BTW this  problem can be done using segment trees.

http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor


On Thu, Sep 6, 2012 at 4:51 PM, bharat b wrote:

> Its better to write an O(n) solution for this problem as the # test cases
> are very high and #elements are also very huge..
> use visited array for distinct numbers ... space--O(n).. time--O(n)
>
>
> On Sat, Aug 25, 2012 at 2:39 AM, michael miller <
> wentworth.miller6...@gmail.com> wrote:
>
>> Hi,
>> You are given N numbers. You have to perform two kinds of operations:
>> U x y - x-th number becomes equal to y.
>> Q x y - calculate the sum of distinct numbers from x-th to y-th. It means
>> that the sum for the set {1, 2, 3, 2, 7} will be equal to 13 (1+2+3+7).
>>
>> 1<=N<=5 and
>> t is the number of test cases where   1<=t<=10
>>
>> all numbers fit in the 32 bit integer range...
>>
>> suggest some solution..
>>
>> here is my solution
>> but it is giving wrong answer fo some unknown test case...plz suggest me
>> the test case where i am getting wrong answer
>>
>>
>> #include
>> #include
>> int main()
>> {
>> int list[5],i,n,j,sum,k,l;char c;long t;
>> scanf 
>> ("%d",&n);
>> for(i=0;i> {
>> scanf 
>> ("%d",&list[i]);
>>
>> }
>> scanf 
>> ("%ld",&t);
>>
>> t=2*t;
>> while(t)
>> {
>> sum=0;
>> scanf 
>> ("%c",&c);
>>
>> fflush(stdin);
>> scanf 
>> ("%d 
>>%d",&k,&l);
>>
>> if(c=='Q')
>> {
>> for(i=k-1;i> {
>> for(j=i+1;j> {
>>if(list[i]==list[j])
>>   break;
>>else if((j==l-1) &&(list[i]!=list[j]))
>>
>>{
>>   sum=sum+list[i];
>>
>>}
>> }
>>  }
>>
>>  printf 
>> ("%d\n",sum+list[l-1]);
>>
>>  }
>>  if(c=='U')
>>  {
>>  list[k-1]=l;
>>
>>  }
>>  t--;
>> }
>> return 0;
>> }
>>
>>
>>
>>  --
>> 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.
>



-- 
Srikanth Reddy M
(M.Sc Tech.) Information Systems
BITS-PILANI

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

[bharat b]

Its better to write an O(n) solution for this problem as the # test cases
are very high and #elements are also very huge..
use visited array for distinct numbers ... space--O(n).. time--O(n)

On Sat, Aug 25, 2012 at 2:39 AM, michael miller <
wentworth.miller6...@gmail.com> wrote:

> Hi,
> You are given N numbers. You have to perform two kinds of operations:
> U x y - x-th number becomes equal to y.
> Q x y - calculate the sum of distinct numbers from x-th to y-th. It means
> that the sum for the set {1, 2, 3, 2, 7} will be equal to 13 (1+2+3+7).
>
> 1<=N<=5 and
> t is the number of test cases where   1<=t<=10
>
> all numbers fit in the 32 bit integer range...
>
> suggest some solution..
>
> here is my solution
> but it is giving wrong answer fo some unknown test case...plz suggest me
> the test case where i am getting wrong answer
>
>
> #include
> #include
> int main()
> {
> int list[5],i,n,j,sum,k,l;char c;long t;
> scanf 
> ("%d",&n);
> for(i=0;i {
> scanf 
> ("%d",&list[i]);
> }
> scanf 
> ("%ld",&t);
> t=2*t;
> while(t)
> {
> sum=0;
> scanf 
> ("%c",&c);
> fflush(stdin);
> scanf 
> ("%d  
>   %d",&k,&l);
> if(c=='Q')
> {
> for(i=k-1;i {
> for(j=i+1;j {
>if(list[i]==list[j])
>   break;
>else if((j==l-1) &&(list[i]!=list[j]))
>{
>   sum=sum+list[i];
>
>}
> }
>  }
>
>  printf 
> ("%d\n",sum+list[l-1]);
>  }
>  if(c=='U')
>  {
>  list[k-1]=l;
>
>  }
>  t--;
> }
> return 0;
> }
>
>
>
>  --
> 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 problem

[sachin sabbarwal]

now i get this!! i thought we have to calculate the sum upto (i-1)th index.
thanx for the clarifiacation.

On Wed, Mar 14, 2012 at 3:07 PM, Dheeraj Sharma  wrote:

> you have to calculate the sum of elements which are less than..that
> particular element...this is not the question of calculating cumulative sum
>
>
> On Wed, Mar 14, 2012 at 11:22 AM, sachin sabbarwal <
> algowithsac...@gmail.com> wrote:
>
>> @gaurav popli:  how about this one??
>>
>> findsummat(int arr[],int n)
>> {
>>int *sum ;
>>  sum =(int*)malloc(sizeof(int)*n);
>>
>> for(int i=0;i>   sum[i] = 0;
>>
>> for(int i=0;i>sum[i] = sum[i-1] + arr[i-1];
>> //now print the sum array
>>
>> }
>>
>> it works very well
>> plz tell me if anything is wrong with this solution.
>>
>>
>> On Tue, Mar 13, 2012 at 12:03 PM, atul anand wrote:
>>
>>> @piyush : sorry dude , didnt get your algo . actually you are using
>>> different array and i get confused which array to be considered when.
>>>
>>>
>>>
>>> On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor wrote:
>>>
 1)First map the array numbers into the position in which they would be,
 if they are sorted,for example
 {30,50,10,60,77,88} ---> {2,3,1,4,5,6}
 2)Now for each number ,find the cumulative frequency of index ( = the
 corresponding number in the map - 1).
 3)Output the cumulative frequency and increase the frequency  at the
 position (=the corresponding number in the map) by the number itself.
 Example
 {3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
 Process the numbers now,
 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is
 0. so output 0
Increase the frequency at index 2 to the number 3.
 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
Increase the frequency at index 3 to the number 5.
 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at
 position 1 by 1.
 Similarly for others.


  --
 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.
>>
>
>
>
> --
> *Dheeraj Sharma*
>
>
>
>  --
> 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 problem

[Dheeraj Sharma]

you have to calculate the sum of elements which are less than..that
particular element...this is not the question of calculating cumulative sum

On Wed, Mar 14, 2012 at 11:22 AM, sachin sabbarwal  wrote:

> @gaurav popli:  how about this one??
>
> findsummat(int arr[],int n)
> {
>int *sum ;
>  sum =(int*)malloc(sizeof(int)*n);
>
> for(int i=0;i   sum[i] = 0;
>
> for(int i=0;isum[i] = sum[i-1] + arr[i-1];
> //now print the sum array
>
> }
>
> it works very well
> plz tell me if anything is wrong with this solution.
>
>
> On Tue, Mar 13, 2012 at 12:03 PM, atul anand wrote:
>
>> @piyush : sorry dude , didnt get your algo . actually you are using
>> different array and i get confused which array to be considered when.
>>
>>
>>
>> On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor wrote:
>>
>>> 1)First map the array numbers into the position in which they would be,
>>> if they are sorted,for example
>>> {30,50,10,60,77,88} ---> {2,3,1,4,5,6}
>>> 2)Now for each number ,find the cumulative frequency of index ( = the
>>> corresponding number in the map - 1).
>>> 3)Output the cumulative frequency and increase the frequency  at the
>>> position (=the corresponding number in the map) by the number itself.
>>> Example
>>> {3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
>>> Process the numbers now,
>>> 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is 0.
>>> so output 0
>>>Increase the frequency at index 2 to the number 3.
>>> 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
>>>Increase the frequency at index 3 to the number 5.
>>> 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at
>>> position 1 by 1.
>>> Similarly for others.
>>>
>>>
>>>  --
>>> 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.
>



-- 
*Dheeraj Sharma*

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

[sachin sabbarwal]

@gaurav popli:  how about this one??

findsummat(int arr[],int n)
{
   int *sum ;
 sum =(int*)malloc(sizeof(int)*n);

for(int i=0;iwrote:

> @piyush : sorry dude , didnt get your algo . actually you are using
> different array and i get confused which array to be considered when.
>
>
>
> On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor wrote:
>
>> 1)First map the array numbers into the position in which they would be,
>> if they are sorted,for example
>> {30,50,10,60,77,88} ---> {2,3,1,4,5,6}
>> 2)Now for each number ,find the cumulative frequency of index ( = the
>> corresponding number in the map - 1).
>> 3)Output the cumulative frequency and increase the frequency  at the
>> position (=the corresponding number in the map) by the number itself.
>> Example
>> {3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
>> Process the numbers now,
>> 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is 0.
>> so output 0
>>Increase the frequency at index 2 to the number 3.
>> 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
>>Increase the frequency at index 3 to the number 5.
>> 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at position
>> 1 by 1.
>> Similarly for others.
>>
>>
>>  --
>> 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 problem

[atul anand]

@piyush : sorry dude , didnt get your algo . actually you are using
different array and i get confused which array to be considered when.


On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor  wrote:

> 1)First map the array numbers into the position in which they would be, if
> they are sorted,for example
> {30,50,10,60,77,88} ---> {2,3,1,4,5,6}
> 2)Now for each number ,find the cumulative frequency of index ( = the
> corresponding number in the map - 1).
> 3)Output the cumulative frequency and increase the frequency  at the
> position (=the corresponding number in the map) by the number itself.
> Example
> {3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
> Process the numbers now,
> 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is 0.
> so output 0
>Increase the frequency at index 2 to the number 3.
> 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
>Increase the frequency at index 3 to the number 5.
> 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at position
> 1 by 1.
> Similarly for others.
>
>
>  --
> 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 problem

[santosh mahto]

I think we can use the counting sort method...

On Tue, Mar 13, 2012 at 1:51 AM, sunny agrawal wrote:

> @atul
> if its sum of numbers lesser than a[i] in left to i, then still i think it
> can be solved in O(nlgn) using Balanced Tree structures
> ie: if we use AVL tree, then we just need a  little care of how to update
> sum stored with rotations
> and required ans for ith index must be calculated just after the ith
> insertion
>
> and if its sum of  numbers lesser than i, then first sort(val, index pair)
> the array and find the prefix sum array would do, with some care for
> duplicates
>
> On Mon, Mar 12, 2012 at 11:09 PM, atul anand wrote:
>
>> @sunny : it was a reply to different question.
>> using AVL or RB for the given algo may screw it.
>>
>>
>> On Mon, Mar 12, 2012 at 11:00 PM, sunny agrawal 
>> wrote:
>>
>>> @atul
>>> TC can be bound to O(nlgn) using any balanced tree ie: AVL tree, RB tree
>>> as already mentioned in her last post
>>>
>>> On Mon, Mar 12, 2012 at 10:44 PM, atul anand wrote:
>>>
 @payal:
 TC will not alwayz be O(nlogn) bcozz we are not sure if the tree formed
 is balanced.
 so worst would be O(n^2)


 On Mon, Mar 12, 2012 at 9:16 PM, payal gupta wrote:

> @atul...
> if its the sum of the elements to the left of a[i] which are smaller
> the my approach works w/o any flaw
> here's the working code for ithttp://ideone.com/CH7VW
> if its the sum of all elements lesser than the element a[i] then this
> algo is surely wrong
> n we then have to proceed by the avl trees or some height balanced
> tree n the algo would be of TC-O(nlogn)
> btw nyc catch thnx...
>
> Regards,
> PAYAL GUPTA
>
>
>
> On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor wrote:
>
>> 1)First map the array numbers into the position in which they would
>> be, if they are sorted,for example
>> {30,50,10,60,77,88} ---> {2,3,1,4,5,6}
>> 2)Now for each number ,find the cumulative frequency of index ( = the
>> corresponding number in the map - 1).
>> 3)Output the cumulative frequency and increase the frequency  at the
>> position (=the corresponding number in the map) by the number itself.
>> Example
>> {3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
>> Process the numbers now,
>> 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is
>> 0. so output 0
>>Increase the frequency at index 2 to the number 3.
>> 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output
>> 3.
>>Increase the frequency at index 3 to the number 5.
>> 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at
>> position 1 by 1.
>> Similarly for others.
>>
>>
>>  --
>> 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.

>>>
>>>
>>>
>>> --
>>> Sunny Aggrawal
>>> B.Tech. V year,CSI
>>> Indian Institute Of Technology,Roorkee
>>>
>>>  --
>>> 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.
>>
>
>
>
> --
> Sunny Aggrawal
> B.Tech. V year,CSI
> Indian Institute Of Technology,Roorkee
>
>  --
> You received this message because you are subscribed 

Re: [algogeeks] Array problem

[sunny agrawal]

@atul
if its sum of numbers lesser than a[i] in left to i, then still i think it
can be solved in O(nlgn) using Balanced Tree structures
ie: if we use AVL tree, then we just need a  little care of how to update
sum stored with rotations
and required ans for ith index must be calculated just after the ith
insertion

and if its sum of  numbers lesser than i, then first sort(val, index pair)
the array and find the prefix sum array would do, with some care for
duplicates

On Mon, Mar 12, 2012 at 11:09 PM, atul anand wrote:

> @sunny : it was a reply to different question.
> using AVL or RB for the given algo may screw it.
>
>
> On Mon, Mar 12, 2012 at 11:00 PM, sunny agrawal 
> wrote:
>
>> @atul
>> TC can be bound to O(nlgn) using any balanced tree ie: AVL tree, RB tree
>> as already mentioned in her last post
>>
>> On Mon, Mar 12, 2012 at 10:44 PM, atul anand wrote:
>>
>>> @payal:
>>> TC will not alwayz be O(nlogn) bcozz we are not sure if the tree formed
>>> is balanced.
>>> so worst would be O(n^2)
>>>
>>>
>>> On Mon, Mar 12, 2012 at 9:16 PM, payal gupta wrote:
>>>
 @atul...
 if its the sum of the elements to the left of a[i] which are smaller
 the my approach works w/o any flaw
 here's the working code for ithttp://ideone.com/CH7VW
 if its the sum of all elements lesser than the element a[i] then this
 algo is surely wrong
 n we then have to proceed by the avl trees or some height balanced tree
 n the algo would be of TC-O(nlogn)
 btw nyc catch thnx...

 Regards,
 PAYAL GUPTA



 On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor wrote:

> 1)First map the array numbers into the position in which they would
> be, if they are sorted,for example
> {30,50,10,60,77,88} ---> {2,3,1,4,5,6}
> 2)Now for each number ,find the cumulative frequency of index ( = the
> corresponding number in the map - 1).
> 3)Output the cumulative frequency and increase the frequency  at the
> position (=the corresponding number in the map) by the number itself.
> Example
> {3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
> Process the numbers now,
> 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is
> 0. so output 0
>Increase the frequency at index 2 to the number 3.
> 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
>Increase the frequency at index 3 to the number 5.
> 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at
> position 1 by 1.
> Similarly for others.
>
>
>  --
> 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.
>>>
>>
>>
>>
>> --
>> Sunny Aggrawal
>> B.Tech. V year,CSI
>> Indian Institute Of Technology,Roorkee
>>
>>  --
>> 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.
>



-- 
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee

-- 
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/alg

Re: [algogeeks] Array problem

[atul anand]

@sunny : it was a reply to different question.
using AVL or RB for the given algo may screw it.

On Mon, Mar 12, 2012 at 11:00 PM, sunny agrawal wrote:

> @atul
> TC can be bound to O(nlgn) using any balanced tree ie: AVL tree, RB tree
> as already mentioned in her last post
>
> On Mon, Mar 12, 2012 at 10:44 PM, atul anand wrote:
>
>> @payal:
>> TC will not alwayz be O(nlogn) bcozz we are not sure if the tree formed
>> is balanced.
>> so worst would be O(n^2)
>>
>>
>> On Mon, Mar 12, 2012 at 9:16 PM, payal gupta  wrote:
>>
>>> @atul...
>>> if its the sum of the elements to the left of a[i] which are smaller the
>>> my approach works w/o any flaw
>>> here's the working code for ithttp://ideone.com/CH7VW
>>> if its the sum of all elements lesser than the element a[i] then this
>>> algo is surely wrong
>>> n we then have to proceed by the avl trees or some height balanced tree
>>> n the algo would be of TC-O(nlogn)
>>> btw nyc catch thnx...
>>>
>>> Regards,
>>> PAYAL GUPTA
>>>
>>>
>>>
>>> On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor wrote:
>>>
 1)First map the array numbers into the position in which they would be,
 if they are sorted,for example
 {30,50,10,60,77,88} ---> {2,3,1,4,5,6}
 2)Now for each number ,find the cumulative frequency of index ( = the
 corresponding number in the map - 1).
 3)Output the cumulative frequency and increase the frequency  at the
 position (=the corresponding number in the map) by the number itself.
 Example
 {3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
 Process the numbers now,
 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is
 0. so output 0
Increase the frequency at index 2 to the number 3.
 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
Increase the frequency at index 3 to the number 5.
 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at
 position 1 by 1.
 Similarly for others.


  --
 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.
>>
>
>
>
> --
> Sunny Aggrawal
> B.Tech. V year,CSI
> Indian Institute Of Technology,Roorkee
>
>  --
> 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 problem

[sunny agrawal]

@atul
TC can be bound to O(nlgn) using any balanced tree ie: AVL tree, RB tree as
already mentioned in her last post

On Mon, Mar 12, 2012 at 10:44 PM, atul anand wrote:

> @payal:
> TC will not alwayz be O(nlogn) bcozz we are not sure if the tree formed is
> balanced.
> so worst would be O(n^2)
>
>
> On Mon, Mar 12, 2012 at 9:16 PM, payal gupta  wrote:
>
>> @atul...
>> if its the sum of the elements to the left of a[i] which are smaller the
>> my approach works w/o any flaw
>> here's the working code for ithttp://ideone.com/CH7VW
>> if its the sum of all elements lesser than the element a[i] then this
>> algo is surely wrong
>> n we then have to proceed by the avl trees or some height balanced tree n
>> the algo would be of TC-O(nlogn)
>> btw nyc catch thnx...
>>
>> Regards,
>> PAYAL GUPTA
>>
>>
>>
>> On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor wrote:
>>
>>> 1)First map the array numbers into the position in which they would be,
>>> if they are sorted,for example
>>> {30,50,10,60,77,88} ---> {2,3,1,4,5,6}
>>> 2)Now for each number ,find the cumulative frequency of index ( = the
>>> corresponding number in the map - 1).
>>> 3)Output the cumulative frequency and increase the frequency  at the
>>> position (=the corresponding number in the map) by the number itself.
>>> Example
>>> {3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
>>> Process the numbers now,
>>> 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is 0.
>>> so output 0
>>>Increase the frequency at index 2 to the number 3.
>>> 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
>>>Increase the frequency at index 3 to the number 5.
>>> 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at
>>> position 1 by 1.
>>> Similarly for others.
>>>
>>>
>>>  --
>>> 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.
>



-- 
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee

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

[payal gupta]

@atul...
if its the sum of the elements to the left of a[i] which are smaller the my
approach works w/o any flaw
here's the working code for ithttp://ideone.com/CH7VW
if its the sum of all elements lesser than the element a[i] then this algo
is surely wrong
n we then have to proceed by the avl trees or some height balanced tree n
the algo would be of TC-O(nlogn)
btw nyc catch thnx...

Regards,
PAYAL GUPTA


On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor  wrote:

> 1)First map the array numbers into the position in which they would be, if
> they are sorted,for example
> {30,50,10,60,77,88} ---> {2,3,1,4,5,6}
> 2)Now for each number ,find the cumulative frequency of index ( = the
> corresponding number in the map - 1).
> 3)Output the cumulative frequency and increase the frequency  at the
> position (=the corresponding number in the map) by the number itself.
> Example
> {3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
> Process the numbers now,
> 1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is 0.
> so output 0
>Increase the frequency at index 2 to the number 3.
> 2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
>Increase the frequency at index 3 to the number 5.
> 3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at position
> 1 by 1.
> Similarly for others.
>
>
>  --
> 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 problem

[Piyush Kapoor]

1)First map the array numbers into the position in which they would be, if
they are sorted,for example
{30,50,10,60,77,88} ---> {2,3,1,4,5,6}
2)Now for each number ,find the cumulative frequency of index ( = the
corresponding number in the map - 1).
3)Output the cumulative frequency and increase the frequency  at the
position (=the corresponding number in the map) by the number itself.
Example
{3,5,1,6,7,8}  Map of which would be {2,3,1,4,5,6}
Process the numbers now,
1)3 comes ,find the cumulative frequency at index 1 ( = 2-1) which is 0. so
output 0
   Increase the frequency at index 2 to the number 3.
2)5 comes,find the CF at index 2( = 3-1) which is equal to 3 .output 3.
   Increase the frequency at index 3 to the number 5.
3)1 comes,CF at index 0 (=1-1) = 0 so output 0.increase the F at position 1
by 1.
Similarly for others.

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

[atul anand]

@piyush :  i dont knw what modification you have made to the BIT to make it
work for this problem .
please provide the code for better understanding or algo will do.

On Mon, Mar 12, 2012 at 3:56 PM, Piyush Kapoor  wrote:

> @atul anand : it will work,i can give u the code.
>
>
> On Mon, Mar 12, 2012 at 11:53 AM, sanjiv yadav wrote:
>
>> u r right.
>>
>>
>> On Mon, Mar 12, 2012 at 11:17 AM, atul anand wrote:
>>
>>> @sanjiv : wont work for this test case :-
>>>
>>> {1,5,3,6,2,7,8};
>>>
>>>
>>> On Mon, Mar 12, 2012 at 10:54 AM, sanjiv yadav 
>>> wrote:
>>>
 @atul anand- It will still work as follows---

 (3,0)
 /  \(5,0+3)
   (1,0) \(6,0+3+5)
 \(2,0+1)\(7,0+3+5+6)
   \(8,0+3+5+6+7)

 here, my logic is that if number is grater than its parent,then add the
 parent in the current sum,else keep it as such.

 check it and made correction in my logic if i m wrong.


 On Mon, Mar 12, 2012 at 10:33 AM, atul anand 
 wrote:

> @piyush : i dont think so BIT would work over here , we are not just
> reporting cumulative sum tilll index i.
>
> On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor 
> wrote:
>
>> This can be done very easily with the help of a Binary Indexed
>> Tree,and it is very short to code as well.Simply process the numbers in
>> order,and for each number output the cumulative frequency of the index of
>> the number you are processing.
>>
>>
>>  --
>> 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.
>



 --
 Regards

 Sanjiv Yadav

 MobNo.-  8050142693

 Email Id-  sanjiv2009...@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.

>>>
>>>  --
>>> 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
>>
>> Sanjiv Yadav
>>
>> MobNo.-  8050142693
>>
>> Email Id-  sanjiv2009...@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.
>

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

[Piyush Kapoor]

@atul anand : it will work,i can give u the code.

On Mon, Mar 12, 2012 at 11:53 AM, sanjiv yadav wrote:

> u r right.
>
>
> On Mon, Mar 12, 2012 at 11:17 AM, atul anand wrote:
>
>> @sanjiv : wont work for this test case :-
>>
>> {1,5,3,6,2,7,8};
>>
>>
>> On Mon, Mar 12, 2012 at 10:54 AM, sanjiv yadav 
>> wrote:
>>
>>> @atul anand- It will still work as follows---
>>>
>>> (3,0)
>>> /  \(5,0+3)
>>>   (1,0) \(6,0+3+5)
>>> \(2,0+1)\(7,0+3+5+6)
>>>   \(8,0+3+5+6+7)
>>>
>>> here, my logic is that if number is grater than its parent,then add the
>>> parent in the current sum,else keep it as such.
>>>
>>> check it and made correction in my logic if i m wrong.
>>>
>>>
>>> On Mon, Mar 12, 2012 at 10:33 AM, atul anand wrote:
>>>
 @piyush : i dont think so BIT would work over here , we are not just
 reporting cumulative sum tilll index i.

 On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor wrote:

> This can be done very easily with the help of a Binary Indexed
> Tree,and it is very short to code as well.Simply process the numbers in
> order,and for each number output the cumulative frequency of the index of
> the number you are processing.
>
>
>  --
> 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.

>>>
>>>
>>>
>>> --
>>> Regards
>>>
>>> Sanjiv Yadav
>>>
>>> MobNo.-  8050142693
>>>
>>> Email Id-  sanjiv2009...@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.
>>>
>>
>>  --
>> 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
>
> Sanjiv Yadav
>
> MobNo.-  8050142693
>
> Email Id-  sanjiv2009...@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 problem

[sanjiv yadav]

u r right.

On Mon, Mar 12, 2012 at 11:17 AM, atul anand wrote:

> @sanjiv : wont work for this test case :-
>
> {1,5,3,6,2,7,8};
>
>
> On Mon, Mar 12, 2012 at 10:54 AM, sanjiv yadav wrote:
>
>> @atul anand- It will still work as follows---
>>
>> (3,0)
>> /  \(5,0+3)
>>   (1,0) \(6,0+3+5)
>> \(2,0+1)\(7,0+3+5+6)
>>   \(8,0+3+5+6+7)
>>
>> here, my logic is that if number is grater than its parent,then add the
>> parent in the current sum,else keep it as such.
>>
>> check it and made correction in my logic if i m wrong.
>>
>>
>> On Mon, Mar 12, 2012 at 10:33 AM, atul anand wrote:
>>
>>> @piyush : i dont think so BIT would work over here , we are not just
>>> reporting cumulative sum tilll index i.
>>>
>>> On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor wrote:
>>>
 This can be done very easily with the help of a Binary Indexed Tree,and
 it is very short to code as well.Simply process the numbers in order,and
 for each number output the cumulative frequency of the index of the number
 you are processing.


  --
 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.
>>>
>>
>>
>>
>> --
>> Regards
>>
>> Sanjiv Yadav
>>
>> MobNo.-  8050142693
>>
>> Email Id-  sanjiv2009...@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.
>>
>
>  --
> 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

Sanjiv Yadav

MobNo.-  8050142693

Email Id-  sanjiv2009...@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 problem

[atul anand]

@sanjiv : wont work for this test case :-

{1,5,3,6,2,7,8};

On Mon, Mar 12, 2012 at 10:54 AM, sanjiv yadav wrote:

> @atul anand- It will still work as follows---
>
> (3,0)
> /  \(5,0+3)
>   (1,0) \(6,0+3+5)
> \(2,0+1)\(7,0+3+5+6)
>   \(8,0+3+5+6+7)
>
> here, my logic is that if number is grater than its parent,then add the
> parent in the current sum,else keep it as such.
>
> check it and made correction in my logic if i m wrong.
>
>
> On Mon, Mar 12, 2012 at 10:33 AM, atul anand wrote:
>
>> @piyush : i dont think so BIT would work over here , we are not just
>> reporting cumulative sum tilll index i.
>>
>> On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor wrote:
>>
>>> This can be done very easily with the help of a Binary Indexed Tree,and
>>> it is very short to code as well.Simply process the numbers in order,and
>>> for each number output the cumulative frequency of the index of the number
>>> you are processing.
>>>
>>>
>>>  --
>>> 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.
>>
>
>
>
> --
> Regards
>
> Sanjiv Yadav
>
> MobNo.-  8050142693
>
> Email Id-  sanjiv2009...@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.
>

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

[sanjiv yadav]

@atul anand- It will still work as follows---

(3,0)
/  \(5,0+3)
  (1,0) \(6,0+3+5)
\(2,0+1)\(7,0+3+5+6)
  \(8,0+3+5+6+7)

here, my logic is that if number is grater than its parent,then add the
parent in the current sum,else keep it as such.

check it and made correction in my logic if i m wrong.

On Mon, Mar 12, 2012 at 10:33 AM, atul anand wrote:

> @piyush : i dont think so BIT would work over here , we are not just
> reporting cumulative sum tilll index i.
>
> On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor wrote:
>
>> This can be done very easily with the help of a Binary Indexed Tree,and
>> it is very short to code as well.Simply process the numbers in order,and
>> for each number output the cumulative frequency of the index of the number
>> you are processing.
>>
>>
>>  --
>> 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.
>



-- 
Regards

Sanjiv Yadav

MobNo.-  8050142693

Email Id-  sanjiv2009...@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 problem

[atul anand]

@piyush : i dont think so BIT would work over here , we are not just
reporting cumulative sum tilll index i.

On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor  wrote:

> This can be done very easily with the help of a Binary Indexed Tree,and it
> is very short to code as well.Simply process the numbers in order,and for
> each number output the cumulative frequency of the index of the number you
> are processing.
>
>
>  --
> 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 problem

[atul anand]

@payal : what will be be the structure of the augmented tree , i add 2 to
the given input. so input become.
ar[]={3,5,1,6,7,8,2};

On Sun, Mar 11, 2012 at 11:07 PM, payal gupta  wrote:

>  the algo vich i thought of is as follows-
>
> struct node{
> int data;
> struct node *left,*right;
> int lsum;   //for storing the leftsum
> int k;// for storing the storing the reqd sum which is leftsum + sum
> of the elements traversed till now on the path
> };
>
>
> Algo for insertion of nodes in bst->
> 1. add the new node with data as the value ,lsum set to 0 and k set to 0
> 2.continue adding further nodes and update the value of 'k' by the data to
> be added  whenever value is added to theleft subtree of the node
> 3. on adding the node to the right of the root set the value of leftsum to
> be summation of rootvalue+k of the nodes considered during traversal
>
>
>
>(3,0,0)
> \
> (5,3+0,0)
>
>(3,0,1)
> /\
> (1,0,0)(5,3+0,0)
>
>(3,0,1)
>/ \
> (1,0,0)  (5,3+0,0)
>\
>(6,1+5+3,0)
>
> (3,0,1)
> / \
>  (1,0,0)   (5,3+0,0)
>  \
>  (6,1+5+3,0)
>\
>(7,1+5+3+6,0)
>
> (3,0,1)
> / \
> (1,0,0)  (5,3+0,0)
> \
> (6,1+5+3,0)
>   \
>   (7,1+3+5+6,0)
> \
> (8,3+1+5+6+7,0)
>
>
> where the node-(data,leftsum,k)
>
>
>
>
>
>
> On Sun, Mar 11, 2012 at 7:06 PM, sanjiv yadav wrote:
>
>> u r right payal but
>> can u expln o(n) time complexity..
>>
>>
>> On Sun, Mar 11, 2012 at 6:10 PM, payal gupta  wrote:
>>
>>> By Augmented BST-
>>> TC-O(n)
>>>
>>>
>>> On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli 
>>> wrote:
>>>
 given an array of size n...
 create an array of size n such that ai where ai is the element in the
 new array at index location i is equal to sum of all elements in
 original array which are smaller than element at posn i...

 e.g
 ar[]={3,5,1,6,7,8};

 ar1[]={0,3,0,9,15,22};

 --
 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.
>>>
>>
>>
>>
>> --
>> Regards
>>
>> Sanjiv Yadav
>>
>> MobNo.-  8050142693
>>
>> Email Id-  sanjiv2009...@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.
>>
>
>  --
> 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 problem

[Dheeraj Sharma]

we can use self balancing BST for this problem to yield the complexity
O(nlogn) ..where every node will contain the sum of the node values on it
left sub tree .. you can check this post..its pretty similar (Method 2)

http://www.geeksforgeeks.org/archives/17235

On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor  wrote:

> This can be done very easily with the help of a Binary Indexed Tree,and it
> is very short to code as well.Simply process the numbers in order,and for
> each number output the cumulative frequency of the index of the number you
> are processing.
>
>
>  --
> 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.
>



-- 
*Dheeraj Sharma*

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

[Piyush Kapoor]

This can be done very easily with the help of a Binary Indexed Tree,and it
is very short to code as well.Simply process the numbers in order,and for
each number output the cumulative frequency of the index of the number you
are processing.

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

[payal gupta]

 the algo vich i thought of is as follows-

struct node{
int data;
struct node *left,*right;
int lsum;   //for storing the leftsum
int k;// for storing the storing the reqd sum which is leftsum + sum of
the elements traversed till now on the path
};


Algo for insertion of nodes in bst->
1. add the new node with data as the value ,lsum set to 0 and k set to 0
2.continue adding further nodes and update the value of 'k' by the data to
be added  whenever value is added to theleft subtree of the node
3. on adding the node to the right of the root set the value of leftsum to
be summation of rootvalue+k of the nodes considered during traversal



   (3,0,0)
\
(5,3+0,0)

   (3,0,1)
/\
(1,0,0)(5,3+0,0)

   (3,0,1)
   / \
(1,0,0)  (5,3+0,0)
   \
   (6,1+5+3,0)

(3,0,1)
/ \
 (1,0,0)   (5,3+0,0)
 \
 (6,1+5+3,0)
   \
   (7,1+5+3+6,0)

(3,0,1)
/ \
(1,0,0)  (5,3+0,0)
\
(6,1+5+3,0)
  \
  (7,1+3+5+6,0)
\
(8,3+1+5+6+7,0)


where the node-(data,leftsum,k)






On Sun, Mar 11, 2012 at 7:06 PM, sanjiv yadav wrote:

> u r right payal but
> can u expln o(n) time complexity..
>
>
> On Sun, Mar 11, 2012 at 6:10 PM, payal gupta  wrote:
>
>> By Augmented BST-
>> TC-O(n)
>>
>>
>> On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli wrote:
>>
>>> given an array of size n...
>>> create an array of size n such that ai where ai is the element in the
>>> new array at index location i is equal to sum of all elements in
>>> original array which are smaller than element at posn i...
>>>
>>> e.g
>>> ar[]={3,5,1,6,7,8};
>>>
>>> ar1[]={0,3,0,9,15,22};
>>>
>>> --
>>> 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.
>>
>
>
>
> --
> Regards
>
> Sanjiv Yadav
>
> MobNo.-  8050142693
>
> Email Id-  sanjiv2009...@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.
>

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

[sanjiv yadav]

u r right payal but
can u expln o(n) time complexity..

On Sun, Mar 11, 2012 at 6:10 PM, payal gupta  wrote:

> By Augmented BST-
> TC-O(n)
>
>
> On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli wrote:
>
>> given an array of size n...
>> create an array of size n such that ai where ai is the element in the
>> new array at index location i is equal to sum of all elements in
>> original array which are smaller than element at posn i...
>>
>> e.g
>> ar[]={3,5,1,6,7,8};
>>
>> ar1[]={0,3,0,9,15,22};
>>
>> --
>> 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.
>



-- 
Regards

Sanjiv Yadav

MobNo.-  8050142693

Email Id-  sanjiv2009...@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 problem

[payal gupta]

By Augmented BST-
TC-O(n)

On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli wrote:

> given an array of size n...
> create an array of size n such that ai where ai is the element in the
> new array at index location i is equal to sum of all elements in
> original array which are smaller than element at posn i...
>
> e.g
> ar[]={3,5,1,6,7,8};
>
> ar1[]={0,3,0,9,15,22};
>
> --
> 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 problem

[Amol Sharma]

wellthat will be a different question.in my question i have never
said that value of the element lies between 0 and k moreover...i don't
want the count...i just want the element which is repeated b times...

hope u got the difference.
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
 







On Thu, Feb 16, 2012 at 11:30 PM, atul anand wrote:

> if i am not wrong , solution is given in this thread and with less
> complexity :-
>
>
> http://groups.google.com/group/algogeeks/browse_thread/thread/44dd396b22595142/6632ae276b99d4ad?hl=en&lnk=gst&q=Array+Problem+%2B+tushar#6632ae276b99d4ad
>
>
>
> On Thu, Feb 16, 2012 at 5:54 PM, Devansh Gupta 
> wrote:
>
>> On 2/16/12, Amol Sharma  wrote:
>> > k,n,b are known and 0> > --
>> >
>> >
>> > Amol Sharma
>> > Third Year Student
>> > Computer Science and Engineering
>> > MNNIT Allahabad
>> >  
>> > <
>> http://in.linkedin.com/pub/amol-sharma/21/79b/507><
>> http://www.simplyamol.blogspot.com/>
>> >
>> >
>> >
>> >
>> >
>> >
>> > On Thu, Feb 16, 2012 at 7:56 AM, saurabh singh 
>> wrote:
>> >
>> >> k,n and b are known to us?
>> >> Saurabh Singh
>> >> B.Tech (Computer Science)
>> >> MNNIT
>> >> blog:geekinessthecoolway.blogspot.com
>> >>
>> >>
>> >>
>> >> On Wed, Feb 15, 2012 at 11:37 PM, Amol Sharma
>> >> wrote:
>> >>
>> >>> Given an array of size n*k+b.In this array n elements are repeated k
>> >>> times and 1 elements are repeated b times.find the Elements which is
>> >>> repeated b time.( O(n*k+b) expected )
>> >>> --
>> >>>
>> >>>
>> >>> Amol Sharma
>> >>> Third Year Student
>> >>> Computer Science and Engineering
>> >>> MNNIT Allahabad
>> >>> 
>> >>> <
>> http://in.linkedin.com/pub/amol-sharma/21/79b/507><
>> http://www.simplyamol.blogspot.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.
>> >>>
>> >>
>> >>  --
>> >> 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
>> *Devansh Gupta*
>> *B.Tech Third Year*
>> *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 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 problem

[atul anand]

if i am not wrong , solution is given in this thread and with less
complexity :-

http://groups.google.com/group/algogeeks/browse_thread/thread/44dd396b22595142/6632ae276b99d4ad?hl=en&lnk=gst&q=Array+Problem+%2B+tushar#6632ae276b99d4ad


On Thu, Feb 16, 2012 at 5:54 PM, Devansh Gupta wrote:

> On 2/16/12, Amol Sharma  wrote:
> > k,n,b are known and 0 > --
> >
> >
> > Amol Sharma
> > Third Year Student
> > Computer Science and Engineering
> > MNNIT Allahabad
> >  
> > <
> http://in.linkedin.com/pub/amol-sharma/21/79b/507><
> http://www.simplyamol.blogspot.com/>
> >
> >
> >
> >
> >
> >
> > On Thu, Feb 16, 2012 at 7:56 AM, saurabh singh 
> wrote:
> >
> >> k,n and b are known to us?
> >> Saurabh Singh
> >> B.Tech (Computer Science)
> >> MNNIT
> >> blog:geekinessthecoolway.blogspot.com
> >>
> >>
> >>
> >> On Wed, Feb 15, 2012 at 11:37 PM, Amol Sharma
> >> wrote:
> >>
> >>> Given an array of size n*k+b.In this array n elements are repeated k
> >>> times and 1 elements are repeated b times.find the Elements which is
> >>> repeated b time.( O(n*k+b) expected )
> >>> --
> >>>
> >>>
> >>> Amol Sharma
> >>> Third Year Student
> >>> Computer Science and Engineering
> >>> MNNIT Allahabad
> >>> 
> >>> <
> http://in.linkedin.com/pub/amol-sharma/21/79b/507><
> http://www.simplyamol.blogspot.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.
> >>>
> >>
> >>  --
> >> 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
> *Devansh Gupta*
> *B.Tech Third Year*
> *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 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 problem

[Devansh Gupta]

On 2/16/12, Amol Sharma  wrote:
> k,n,b are known and 0 --
>
>
> Amol Sharma
> Third Year Student
> Computer Science and Engineering
> MNNIT Allahabad
>  
> 
>
>
>
>
>
>
> On Thu, Feb 16, 2012 at 7:56 AM, saurabh singh  wrote:
>
>> k,n and b are known to us?
>> Saurabh Singh
>> B.Tech (Computer Science)
>> MNNIT
>> blog:geekinessthecoolway.blogspot.com
>>
>>
>>
>> On Wed, Feb 15, 2012 at 11:37 PM, Amol Sharma
>> wrote:
>>
>>> Given an array of size n*k+b.In this array n elements are repeated k
>>> times and 1 elements are repeated b times.find the Elements which is
>>> repeated b time.( O(n*k+b) expected )
>>> --
>>>
>>>
>>> Amol Sharma
>>> Third Year Student
>>> Computer Science and Engineering
>>> 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 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.
>
>


-- 
Thanks and Regards
*Devansh Gupta*
*B.Tech Third Year*
*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 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 problem

[saurabh singh]

k,n and b are known to us?
Saurabh Singh
B.Tech (Computer Science)
MNNIT
blog:geekinessthecoolway.blogspot.com



On Wed, Feb 15, 2012 at 11:37 PM, Amol Sharma wrote:

> Given an array of size n*k+b.In this array n elements are repeated k times
> and 1 elements are repeated b times.find the Elements which is repeated b
> time.( O(n*k+b) expected )
> --
>
>
> Amol Sharma
> Third Year Student
> Computer Science and Engineering
> 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 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 Problem

[atul anand]

yeah...only if given array is sorted ..we can do it in O(n) and O(1) fetch
with all given restriction

On Wed, Feb 15, 2012 at 10:14 AM, Kartik Sachan wrote:

> @atul if array is not sorted we have to take extra array for
> this...otherwise this cannn't be done in O(n) time.
>
>  --
> 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 Problem

[Kartik Sachan]

@atul if array is not sorted we have to take extra array for
this...otherwise this cannn't be done in O(n) time.

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

[atul anand]

@kartik : question says inplace . so using hashing would be violation...
i dont think so it can be done if array is unsorted and with given
restriction

On Wed, Feb 15, 2012 at 10:05 AM, Kartik Sachan wrote:

> if n is less than 10^6 hasing works fine ..and we count in O(1) time only
>
>  --
> 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 Problem

[Kartik Sachan]

if n is less than 10^6 hasing works fine ..and we count in O(1) time only

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

[atul anand]

we can use hashtable ... and maintain count with each entry to the table.

if number occur for first time increment count..
if number occur again decrement count.

in the end jus check for entry whose count is 0rest count >  0
one who is repeated twice will have count=0

On Thu, Nov 17, 2011 at 9:29 PM, himanshu kansal <
himanshukansal...@gmail.com> wrote:

> consider an array having n elements.out of which one number is
> repeated twiceother number are repeated odd number of times(for
> simplicity, assume other numbers are occurring just once)
>
> can you find the number that is repeated twice in O(n) time???
>
> PS: numbers are not from a particular range.
>
> --
> 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 searching

[SAMM]

Yes we can do so in O(n) .

First find the XOR of all unique elements  using hash table or some other DS.
Secondly XOR  all the elements of the array .which will hav the xor of
elements other thn the element repeated twice.

Now XOR the above two value which will give the answer..

On 11/17/11, himanshu kansal  wrote:
> consider an array having n elements.out of which one number is
> repeated twiceother number are repeated odd number of times(for
> simplicity, assume other numbers are occurring just once)
>
> can you find the number that is repeated twice in O(n) time???
>
> PS: numbers are not from a particular range.
>
> --
> 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.
>
>


-- 
Somnath Singh

-- 
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 or matrix problems...anyone?

[Kunal Patil]

@shady: There were no specific constraints. Actually, they didn't expect
any best solution. People who wrote brute force also got shortlisted. Brute
force would be Just picking a number one by one from first row and then
checking other rows for existence of this number. I think it is a O(n^3)
algorithm where n--> number of rows/cols

Another approach might be, we can sort each row in O(nlogn). So total is
O(n^2 * log(n)). Take number one by one from first row and then binary
search on remaining rows. It is O(logn) in one row. So total binary search
cost for searching one element in n rows is O(nlogn). In worst case where
last element of first row occurs in each row, complexity of this algorithm
seems to be O(n^2 * logn )

Correct me if I'm wrong. Anyone having better solution to this, please
comment..

Also as second algorithm is quite complex to implement and in question they
explicitly mentioned matrix is 3X3, So brute force would be the fastest i
guess... :) :)

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

[rahul sharma]

all integers pairs in array that sum to given value say (k)...i have two sol
for the array that contain unique elements..m asking should i take care of
duplicates or notcoz my logic wont work for duplicates like if i have 0
1 2 3 4 5 6 8 8 if i want all pairs having some 8 ...den it should give(0,8)
(0,8) two tymes or one tym is alryt

On Sat, Oct 1, 2011 at 9:12 PM, shady  wrote:

> what is the question
> ???
>
> On Sat, Oct 1, 2011 at 9:08 PM, rahul sharma wrote:
>
>> all pairs of integers sum upto x.shiuld we take care of
>> duplicates??
>>
>> --
>> 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 sum

[shady]

what is the question
???

On Sat, Oct 1, 2011 at 9:08 PM, rahul sharma wrote:

> all pairs of integers sum upto x.shiuld we take care of
> duplicates??
>
> --
> 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 PROBLEM

[Wladimir Tavares]

First,
you need change 0 to -1
Wladimir Araujo Tavares
*Federal University of Ceará 
Homepage  |
Maratona|
*




On Thu, Sep 29, 2011 at 7:35 AM, Wladimir Tavares wrote:

> Algorithm Kadane
>
> http://www.algorithmist.com/index.php/Kadane%27s_Algorithm
>
> http://www.cs.ucf.edu/~reinhard/classes/cop3503/lectures/AlgAnalysis04.pdf
>
>
> http://struts2spring.wordpress.com/2009/11/02/finding-the-maximum-contiguous-subsequence-in-a-one-dimensional-array/
>
>
> Wladimir Araujo Tavares
> *Federal University of Ceará 
> Homepage  | 
> Maratona|
> *
>
>
>
>
>
> On Thu, Sep 29, 2011 at 5:28 AM, apoorv gupta wrote:
>
>> sachan!!amol ke rum par jaakar pooch le.
>>
>>
>> On Thu, Sep 29, 2011 at 1:10 PM, kartik sachan 
>> wrote:
>>
>>> ok amol i will do it..but i am unable to convience myself
>>> that this algo will give the desire result
>>>
>>>  --
>>> 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 Sincere Regards
>> Apoorv Gupta
>> Btech 3rd Year
>> Computer Science And Engineering
>> 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 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 PROBLEM

[Wladimir Tavares]

Algorithm Kadane

http://www.algorithmist.com/index.php/Kadane%27s_Algorithm

http://www.cs.ucf.edu/~reinhard/classes/cop3503/lectures/AlgAnalysis04.pdf

http://struts2spring.wordpress.com/2009/11/02/finding-the-maximum-contiguous-subsequence-in-a-one-dimensional-array/


Wladimir Araujo Tavares
*Federal University of Ceará 
Homepage  |
Maratona|
*




On Thu, Sep 29, 2011 at 5:28 AM, apoorv gupta wrote:

> sachan!!amol ke rum par jaakar pooch le.
>
>
> On Thu, Sep 29, 2011 at 1:10 PM, kartik sachan wrote:
>
>> ok amol i will do it..but i am unable to convience myself that
>> this algo will give the desire result
>>
>>  --
>> 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 Sincere Regards
> Apoorv Gupta
> Btech 3rd Year
> Computer Science And Engineering
> 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 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 PROBLEM

[apoorv gupta]

sachan!!amol ke rum par jaakar pooch le.

On Thu, Sep 29, 2011 at 1:10 PM, kartik sachan wrote:

> ok amol i will do it..but i am unable to convience myself that
> this algo will give the desire result
>
>  --
> 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 Sincere Regards
Apoorv Gupta
Btech 3rd Year
Computer Science And Engineering
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 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 PROBLEM

[kartik sachan]

ok amol i will do it..but i am unable to convience myself that
this algo will give the desire result

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

[Amol Sharma]

@kartik...try to implement the algo using pen and paper take 2-3 extra
variables for storing index also along with the variable max.the same
algo will also give you the required subarray indexes along with its
length...
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad







On Thu, Sep 29, 2011 at 12:58 PM, DIVIJ WADHAWAN  wrote:

> Impossible to solve in O(n) I suppose
>
>
> On Thu, Sep 29, 2011 at 12:34 PM, kartik sachan 
> wrote:
>
>> @AMOL i want array index i.e i to j that will be max subarry which has
>> equal no of zero and one's
>>
>>
>> but i think ur soln is not providing this
>>
>>  --
>> 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 PROBLEM

[DIVIJ WADHAWAN]

Impossible to solve in O(n) I suppose

On Thu, Sep 29, 2011 at 12:34 PM, kartik sachan wrote:

> @AMOL i want array index i.e i to j that will be max subarry which has
> equal no of zero and one's
>
>
> but i think ur soln is not providing this
>
>  --
> 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 PROBLEM

[kartik sachan]

@AMOL i want array index i.e i to j that will be max subarry which has equal
no of zero and one's


but i think ur soln is not providing this

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

[Shravan Kumar]

O/P should be 00111010  and sub array is exclusive of start index, inclusive
of end index.

Nice solution

On Thu, Sep 29, 2011 at 11:58 AM, UTKARSH SRIVASTAV  wrote:

> @Amol +1
>
> On Thu, Sep 29, 2011 at 11:52 AM, Amol Sharma wrote:
>
>> given array-
>> 1  0  0  1  1  1  0  1  0  1
>> for our convenience lets replace 0 by -1
>> array becomes
>> 1 -1 -1  1  1  1 -1  1 -1  1
>>
>> take another array count which which represents the sum till that index
>> sum array becomes
>> 1  0 -1  0  1  2  1  2  1  2 //count array
>>
>> now make an important observation that if a number repeats in the count
>> array then between that two indexes equal number of zeros and ones have been
>> added...
>>
>> now take 2 arrays of size 2n+1 and index them from -n to n.lets call
>> them array a_front and a_backthe idea behind indexing is that the
>> possible value of sum varies from -n(all 0's) to +n(all 1's)
>>
>>
>> for *a_front*
>>   traverse the count array from front and for each number update index of
>> it's first occurrence in the a_front array
>>in this case...a_front[1]=0,a_front[0]=1,a_front[-1]=2,a_front[2]=6...only
>> these four entries will be updated in the a_front array
>>
>> for *a_back*
>>   traverse the count array from back and for each number update index of
>> it's last occurrence in the a_back array
>>  in this case...a_back[2]=9,a_back[1]=8,a_back[0]=3,a_back[-1]=2..only
>> these four entries will be updated in the a_back array
>>
>> now traverse both a_front and a_back simultaneously
>> max(a_back[i]-a_front[i]) will indicate the maximum subarray with equal
>> zeros and ones.
>>
>> Hope this helps !!
>>
>>
>>
>> --
>>
>>
>> Amol Sharma
>> Third Year Student
>> Computer Science and Engineering
>> MNNIT Allahabad
>>  
>> 
>>
>>
>>
>>
>>
>> On Thu, Sep 29, 2011 at 10:39 AM, kartik sachan 
>> wrote:
>>
>>>Given a binary array ( array containing only 0s and 1s ). You have to
>>> print the sub-array with
>>> maximum number of equal 1s and 0s.
>>> INPUT   OUTPUT
>>> 1001110101  0011101
>>>
>>>
>>> complex-O(n)
>>>
>>> --
>>>
>>> *WITH REGARDS,*
>>> *
>>> *
>>> *KARTIK SACHAN*
>>>
>>> *B.TECH 3rd YEAR*
>>> *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.
>>
>
>
>
> --
> *UTKARSH SRIVASTAV
> CSE-3
> B-Tech 3rd Year
> @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 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 PROBLEM

[UTKARSH SRIVASTAV]

@Amol +1

On Thu, Sep 29, 2011 at 11:52 AM, Amol Sharma wrote:

> given array-
> 1  0  0  1  1  1  0  1  0  1
> for our convenience lets replace 0 by -1
> array becomes
> 1 -1 -1  1  1  1 -1  1 -1  1
>
> take another array count which which represents the sum till that index
> sum array becomes
> 1  0 -1  0  1  2  1  2  1  2 //count array
>
> now make an important observation that if a number repeats in the count
> array then between that two indexes equal number of zeros and ones have been
> added...
>
> now take 2 arrays of size 2n+1 and index them from -n to n.lets call
> them array a_front and a_backthe idea behind indexing is that the
> possible value of sum varies from -n(all 0's) to +n(all 1's)
>
>
> for *a_front*
>   traverse the count array from front and for each number update index of
> it's first occurrence in the a_front array
>in this case...a_front[1]=0,a_front[0]=1,a_front[-1]=2,a_front[2]=6...only
> these four entries will be updated in the a_front array
>
> for *a_back*
>   traverse the count array from back and for each number update index of
> it's last occurrence in the a_back array
>  in this case...a_back[2]=9,a_back[1]=8,a_back[0]=3,a_back[-1]=2..only
> these four entries will be updated in the a_back array
>
> now traverse both a_front and a_back simultaneously
> max(a_back[i]-a_front[i]) will indicate the maximum subarray with equal
> zeros and ones.
>
> Hope this helps !!
>
>
>
> --
>
>
> Amol Sharma
> Third Year Student
> Computer Science and Engineering
> MNNIT Allahabad
>  
> 
>
>
>
>
>
> On Thu, Sep 29, 2011 at 10:39 AM, kartik sachan 
> wrote:
>
>>Given a binary array ( array containing only 0s and 1s ). You have to
>> print the sub-array with
>> maximum number of equal 1s and 0s.
>> INPUT   OUTPUT
>> 1001110101  0011101
>>
>>
>> complex-O(n)
>>
>> --
>>
>> *WITH REGARDS,*
>> *
>> *
>> *KARTIK SACHAN*
>>
>> *B.TECH 3rd YEAR*
>> *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.
>



-- 
*UTKARSH SRIVASTAV
CSE-3
B-Tech 3rd Year
@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 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 PROBLEM

[Amol Sharma]

complexity O(n)
extra space O(n)
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
 






On Thu, Sep 29, 2011 at 11:52 AM, Amol Sharma wrote:

> given array-
> 1  0  0  1  1  1  0  1  0  1
> for our convenience lets replace 0 by -1
> array becomes
> 1 -1 -1  1  1  1 -1  1 -1  1
>
> take another array count which which represents the sum till that index
> sum array becomes
> 1  0 -1  0  1  2  1  2  1  2 //count array
>
> now make an important observation that if a number repeats in the count
> array then between that two indexes equal number of zeros and ones have been
> added...
>
> now take 2 arrays of size 2n+1 and index them from -n to n.lets call
> them array a_front and a_backthe idea behind indexing is that the
> possible value of sum varies from -n(all 0's) to +n(all 1's)
>
>
> for *a_front*
>   traverse the count array from front and for each number update index of
> it's first occurrence in the a_front array
>in this case...a_front[1]=0,a_front[0]=1,a_front[-1]=2,a_front[2]=6...only
> these four entries will be updated in the a_front array
>
> for *a_back*
>   traverse the count array from back and for each number update index of
> it's last occurrence in the a_back array
>  in this case...a_back[2]=9,a_back[1]=8,a_back[0]=3,a_back[-1]=2..only
> these four entries will be updated in the a_back array
>
> now traverse both a_front and a_back simultaneously
> max(a_back[i]-a_front[i]) will indicate the maximum subarray with equal
> zeros and ones.
>
> Hope this helps !!
>
>
>
> --
>
>
> Amol Sharma
> Third Year Student
> Computer Science and Engineering
> MNNIT Allahabad
>  
> 
>
>
>
>
>
> On Thu, Sep 29, 2011 at 10:39 AM, kartik sachan 
> wrote:
>
>>Given a binary array ( array containing only 0s and 1s ). You have to
>> print the sub-array with
>> maximum number of equal 1s and 0s.
>> INPUT   OUTPUT
>> 1001110101  0011101
>>
>>
>> complex-O(n)
>>
>> --
>>
>> *WITH REGARDS,*
>> *
>> *
>> *KARTIK SACHAN*
>>
>> *B.TECH 3rd YEAR*
>> *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 PROBLEM

[Amol Sharma]

given array-
1  0  0  1  1  1  0  1  0  1
for our convenience lets replace 0 by -1
array becomes
1 -1 -1  1  1  1 -1  1 -1  1

take another array count which which represents the sum till that index
sum array becomes
1  0 -1  0  1  2  1  2  1  2 //count array

now make an important observation that if a number repeats in the count
array then between that two indexes equal number of zeros and ones have been
added...

now take 2 arrays of size 2n+1 and index them from -n to n.lets call
them array a_front and a_backthe idea behind indexing is that the
possible value of sum varies from -n(all 0's) to +n(all 1's)


for *a_front*
  traverse the count array from front and for each number update index of
it's first occurrence in the a_front array
   in this case...a_front[1]=0,a_front[0]=1,a_front[-1]=2,a_front[2]=6...only
these four entries will be updated in the a_front array

for *a_back*
  traverse the count array from back and for each number update index of
it's last occurrence in the a_back array
 in this case...a_back[2]=9,a_back[1]=8,a_back[0]=3,a_back[-1]=2..only these
four entries will be updated in the a_back array

now traverse both a_front and a_back simultaneously
max(a_back[i]-a_front[i]) will indicate the maximum subarray with equal
zeros and ones.

Hope this helps !!



--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad







On Thu, Sep 29, 2011 at 10:39 AM, kartik sachan wrote:

>Given a binary array ( array containing only 0s and 1s ). You have to
> print the sub-array with
> maximum number of equal 1s and 0s.
> INPUT   OUTPUT
> 1001110101  0011101
>
>
> complex-O(n)
>
> --
>
> *WITH REGARDS,*
> *
> *
> *KARTIK SACHAN*
>
> *B.TECH 3rd YEAR*
> *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 A and B

[anshu mishra]

you can use mergesort technique, segment tree, binary index tree or BST

-- 
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 ques based on correlation factor

[Piyush Grover]

=>Take a function rand() which returns value between [0, 1) uniformly or use
function rand(n) = n*rand() which return value between 0- (n-1) using
uniform probability distribution.
=>Now create a array A[0..n-1] = [0..n-1]
 now rake an array R.

k = n;
for(i = 0; i < n; i++){
 a = rand(k);
 R.push(A[a]);
 swap(A[a], A[k-1]);
 k--;
}
return(R);


Verification:

1.) Yes, R contains values between 0-n-1;

2.) Yes, R has no repeated numbers

3.) R can be filled in O(n) so yes deterministic time.

4.) Correlation factor: Selection of one number should not affect the
probability of selecting other number.

here correlation factor = 0;

for each location 0..n-1 the probability of putting any number is 1/n.

->At 0th index probability of putting a number say, x is: 1/n
->at 1st index probability of putting a number y is: (n-1)/n *  1/(n-1) =
1/n
->at 2nd index probability of putting a number z is: (n-1)/n *(n-2)/(n-1) *
1/(n-2) = 1/n

and so on. So selection of any number at any position is independent of any
number being selected. So
they have independent and uniform probability.

-Piyush

On Sat, Sep 17, 2011 at 10:42 PM, sivaviknesh s wrote:

> Write a method fill up an array of size n - and returns the array to the
> caller - with the following conditions
>
> 1. the numbers shud be between 0 to n-1
> 2. no repeated numbers
> 3. the method should have a deterministic time to fill the arrays
> 4. arrays returned from the method should have low-correlation factor
>
> ...btw what does 4 th point mean? what is a correlation factor?? Plz
> provide code and explain...
>
>
> --
> Regards,
> $iva
>
>  --
> 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 sum

[Neha Singh]

@Ankit: Ur solution has some flaws I think. Ur solution assumes that we r
dividing the sorted array into 2 halves, but the question says:  divide an
integer array into 2 sub-arrays and make their averages equal. Take some
test case and apply ur solution to it.
 We cud do this problem in the following way :
1. Sort the array

2. Take 2 containers i.e. arrays

3. Start adding elements from the sorted array into the container which has
less average. Note that the average of the 2 new arrays can be maintained in
2 variables and need not computed each time an element is added

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

[Ankit Sinha]

Algo:

1. Sort the array
2. modify binary search on the set comparing average of both the set.
3. if aveage (start, mid) > average (mid , end) then go to left sub
set else right subset.


This could lead to solution in o(nlogn) time. Please comment futher!!

Cheers,
Ankit Sinha

On Sat, Aug 27, 2011 at 12:40 PM, wujin chen  wrote:
> take a subset from the array, if the average is equal then output the
> result.
> backtracing can do this.
> the time complexity seems not low, any good idea~~?
>
> 2011/8/27 sukhmeet singh 
>>
>> how to divide an integer array into 2 sub-arrays and make their averages
>> equal?
>> array is unsorted and we can also take any numbers and the numbers in the
>> array need not be contiguous in the original array.
>> how many total such array's are possible. Output them
>>
>> --
>> 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 sum

[wujin chen]

take a subset from the array, if the average is equal then output the
result.
backtracing can do this.

the time complexity seems not low, any good idea~~?

2011/8/27 sukhmeet singh 

> how to divide an integer array into 2 sub-arrays and make their averages
> equal?
> array is unsorted and we can also take any numbers and the numbers in the
> array need not be contiguous in the original array.
> how many total such array's are possible. Output them
>
> --
> 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 problem

[Puneet Chawla]

+1 Sanjay

On Sun, Aug 21, 2011 at 2:59 PM, Dheeraj Sharma  wrote:

> yeah bt..when we talk abt the complexity..we consider abt the worst case
>
> On 8/21/11, himanshu kansal  wrote:
> > problem: There is an array containing integers.
> > for every bit in the integer,you have to print a 1 if no of 1s
> > corresponding to that bit is more than no of 0s corresponding to that
> > bit (counting that bit in all the integers) otherwise print a 0(if no
> > of 0s corresponding to that bit are more).
> >
> > this you have to do for all bits in the integers.
> >
> > assumption:integers are of 32bits.
> > no of integers in array are odd...(i.e. there is no case like no. of
> > 1s=no. of 0s)
> >
> > i have  done this by counting the no of 1s and 0s for all bits.
> >
> > but can anyone suggest any other efficient approach (somewhat using
> > bitwise operators).
> >
> > --
> > 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.
> >
> >
>
>
> --
> *Dheeraj Sharma*
> Comp Engg.
> NIT Kurukshetra
> +91 8950264227
>
> --
> 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
  
Puneet Chawla
Computer Engineering Student
NIT Kurukshetra

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

[Dheeraj Sharma]

yeah bt..when we talk abt the complexity..we consider abt the worst case

On 8/21/11, himanshu kansal  wrote:
> problem: There is an array containing integers.
> for every bit in the integer,you have to print a 1 if no of 1s
> corresponding to that bit is more than no of 0s corresponding to that
> bit (counting that bit in all the integers) otherwise print a 0(if no
> of 0s corresponding to that bit are more).
>
> this you have to do for all bits in the integers.
>
> assumption:integers are of 32bits.
> no of integers in array are odd...(i.e. there is no case like no. of
> 1s=no. of 0s)
>
> i have  done this by counting the no of 1s and 0s for all bits.
>
> but can anyone suggest any other efficient approach (somewhat using
> bitwise operators).
>
> --
> 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.
>
>


-- 
*Dheeraj Sharma*
Comp Engg.
NIT Kurukshetra
+91 8950264227

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

[sagar pareek]

This problem can be reduced if we are taking whole 32 bits...
Mean left most all 0's bits are also including
then if number is less than 65535 (2^16-1) then make it 0
as 16 bits are at least zero in this case

On Sun, Aug 21, 2011 at 2:19 PM, Sanjay Rajpal  wrote:

> let n be the no.of integers in the array :
>
> int i=1,a;
> int zero,one;
> for(int a=1;a<=32;a++)
> {
> zero=0;
> one=0;
> for(int j=0;j {
> if(a[j] & i)
> {
> one++;
> }
> else
> {
> zero++;
> }
> }
> if(one > zero)
> {
> printf("1s are more \n");
> }
> else
> {
> printf("0s are more \n");
> }
> i=i<<1;
> }
>
> Correct me if m wrong.
>
> Sanju
> :)
>
>
>
> On Sun, Aug 21, 2011 at 1:28 AM, Dheeraj Sharma <
> dheerajsharma1...@gmail.com> wrote:
>
>> yeah i took it in the another way..i ll post it v soon
>>
>> On 8/21/11, himanshu kansal  wrote:
>> > problem: There is an array containing integers.
>> > for every bit in the integer,you have to print a 1 if no of 1s
>> > corresponding to that bit is more than no of 0s corresponding to that
>> > bit (counting that bit in all the integers) otherwise print a 0(if no
>> > of 0s corresponding to that bit are more).
>> >
>> > this you have to do for all bits in the integers.
>> >
>> > assumption:integers are of 32bits.
>> > no of integers in array are odd...(i.e. there is no case like no. of
>> > 1s=no. of 0s)
>> >
>> > i have  done this by counting the no of 1s and 0s for all bits.
>> >
>> > but can anyone suggest any other efficient approach (somewhat using
>> > bitwise operators).
>> >
>> > --
>> > 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.
>> >
>> >
>>
>>
>> --
>> *Dheeraj Sharma*
>> Comp Engg.
>> NIT Kurukshetra
>> +91 8950264227
>>
>> --
>> 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.
>



-- 
**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 problem

[Sanjay Rajpal]

let n be the no.of integers in the array :

int i=1,a;
int zero,one;
for(int a=1;a<=32;a++)
{
zero=0;
one=0;
for(int j=0;j zero)
{
printf("1s are more \n");
}
else
{
printf("0s are more \n");
}
i=i<<1;
}

Correct me if m wrong.

Sanju
:)



On Sun, Aug 21, 2011 at 1:28 AM, Dheeraj Sharma  wrote:

> yeah i took it in the another way..i ll post it v soon
>
> On 8/21/11, himanshu kansal  wrote:
> > problem: There is an array containing integers.
> > for every bit in the integer,you have to print a 1 if no of 1s
> > corresponding to that bit is more than no of 0s corresponding to that
> > bit (counting that bit in all the integers) otherwise print a 0(if no
> > of 0s corresponding to that bit are more).
> >
> > this you have to do for all bits in the integers.
> >
> > assumption:integers are of 32bits.
> > no of integers in array are odd...(i.e. there is no case like no. of
> > 1s=no. of 0s)
> >
> > i have  done this by counting the no of 1s and 0s for all bits.
> >
> > but can anyone suggest any other efficient approach (somewhat using
> > bitwise operators).
> >
> > --
> > 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.
> >
> >
>
>
> --
> *Dheeraj Sharma*
> Comp Engg.
> NIT Kurukshetra
> +91 8950264227
>
> --
> 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 problem

[Dheeraj Sharma]

yeah i took it in the another way..i ll post it v soon

On 8/21/11, himanshu kansal  wrote:
> problem: There is an array containing integers.
> for every bit in the integer,you have to print a 1 if no of 1s
> corresponding to that bit is more than no of 0s corresponding to that
> bit (counting that bit in all the integers) otherwise print a 0(if no
> of 0s corresponding to that bit are more).
>
> this you have to do for all bits in the integers.
>
> assumption:integers are of 32bits.
> no of integers in array are odd...(i.e. there is no case like no. of
> 1s=no. of 0s)
>
> i have  done this by counting the no of 1s and 0s for all bits.
>
> but can anyone suggest any other efficient approach (somewhat using
> bitwise operators).
>
> --
> 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.
>
>


-- 
*Dheeraj Sharma*
Comp Engg.
NIT Kurukshetra
+91 8950264227

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

[Puneet Chawla]

Similary as we  are counting set bits count 0's nd cmpare nd set 1 if
coutn(1)>count(0) for each integer in array

On Sun, Aug 21, 2011 at 1:44 PM, Sanjay Rajpal  wrote:

> @Dheeraj : I think u should review the problem again.
> What u have posted is a way to find no. of set bits in a number.
> But problem is check a bit at a position in all number for no. of 1s and
> 0s, not in a single number.
> This has to be done for all 32 bits.
>
> Sanju
> :)
>
>
>
> On Sun, Aug 21, 2011 at 1:11 AM, Dheeraj Sharma <
> dheerajsharma1...@gmail.com> wrote:
>
>> while(a)
>> (
>> a&=(a-1)
>> count++
>> )
>> counts number of 1s in number 'a'..
>> Loop can be breaken if count exceeds 16..
>>
>> On 8/21/11, himanshu kansal  wrote:
>> > problem: There is an array containing integers.
>> > for every bit in the integer,you have to print a 1 if no of 1s
>> > corresponding to that bit is more than no of 0s corresponding to that
>> > bit (counting that bit in all the integers) otherwise print a 0(if no
>> > of 0s corresponding to that bit are more).
>> >
>> > this you have to do for all bits in the integers.
>> >
>> > assumption:integers are of 32bits.
>> > no of integers in array are odd...(i.e. there is no case like no. of
>> > 1s=no. of 0s)
>> >
>> > i have  done this by counting the no of 1s and 0s for all bits.
>> >
>> > but can anyone suggest any other efficient approach (somewhat using
>> > bitwise operators).
>> >
>> > --
>> > 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.
>> >
>> >
>>
>>
>> --
>> *Dheeraj Sharma*
>> Comp Engg.
>> NIT Kurukshetra
>> +91 8950264227
>>
>> --
>> 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.
>



-- 
With regards
  
Puneet

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

[Sanjay Rajpal]

@Dheeraj : I think u should review the problem again.
What u have posted is a way to find no. of set bits in a number.
But problem is check a bit at a position in all number for no. of 1s and 0s,
not in a single number.
This has to be done for all 32 bits.

Sanju
:)



On Sun, Aug 21, 2011 at 1:11 AM, Dheeraj Sharma  wrote:

> while(a)
> (
> a&=(a-1)
> count++
> )
> counts number of 1s in number 'a'..
> Loop can be breaken if count exceeds 16..
>
> On 8/21/11, himanshu kansal  wrote:
> > problem: There is an array containing integers.
> > for every bit in the integer,you have to print a 1 if no of 1s
> > corresponding to that bit is more than no of 0s corresponding to that
> > bit (counting that bit in all the integers) otherwise print a 0(if no
> > of 0s corresponding to that bit are more).
> >
> > this you have to do for all bits in the integers.
> >
> > assumption:integers are of 32bits.
> > no of integers in array are odd...(i.e. there is no case like no. of
> > 1s=no. of 0s)
> >
> > i have  done this by counting the no of 1s and 0s for all bits.
> >
> > but can anyone suggest any other efficient approach (somewhat using
> > bitwise operators).
> >
> > --
> > 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.
> >
> >
>
>
> --
> *Dheeraj Sharma*
> Comp Engg.
> NIT Kurukshetra
> +91 8950264227
>
> --
> 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 problem

[Dheeraj Sharma]

while(a)
(
a&=(a-1)
count++
)
counts number of 1s in number 'a'..
Loop can be breaken if count exceeds 16..

On 8/21/11, himanshu kansal  wrote:
> problem: There is an array containing integers.
> for every bit in the integer,you have to print a 1 if no of 1s
> corresponding to that bit is more than no of 0s corresponding to that
> bit (counting that bit in all the integers) otherwise print a 0(if no
> of 0s corresponding to that bit are more).
>
> this you have to do for all bits in the integers.
>
> assumption:integers are of 32bits.
> no of integers in array are odd...(i.e. there is no case like no. of
> 1s=no. of 0s)
>
> i have  done this by counting the no of 1s and 0s for all bits.
>
> but can anyone suggest any other efficient approach (somewhat using
> bitwise operators).
>
> --
> 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.
>
>


-- 
*Dheeraj Sharma*
Comp Engg.
NIT Kurukshetra
+91 8950264227

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

[Sanjay Rajpal]

for this problem, we will have to check all the bits i.e. 32*n where n is
the number of integers in the array.
n bits in one go. So i think your approach will be fine.

Using bitwise operators will not make any difference.

if someone knows better solution ,plz post it.

Sanju
:)



On Sun, Aug 21, 2011 at 12:47 AM, himanshu kansal <
himanshukansal...@gmail.com> wrote:

> problem: There is an array containing integers.
> for every bit in the integer,you have to print a 1 if no of 1s
> corresponding to that bit is more than no of 0s corresponding to that
> bit (counting that bit in all the integers) otherwise print a 0(if no
> of 0s corresponding to that bit are more).
>
> this you have to do for all bits in the integers.
>
> assumption:integers are of 32bits.
> no of integers in array are odd...(i.e. there is no case like no. of
> 1s=no. of 0s)
>
> i have  done this by counting the no of 1s and 0s for all bits.
>
> but can anyone suggest any other efficient approach (somewhat using
> bitwise operators).
>
> --
> 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

[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 ques

[siddharth srivastava]

On 15 August 2011 21:07, sagar pareek  wrote:

> int lol=2; // total lol's encountered upto now
>
> lol++;


it is a programming mistake as you have indicated the value of the important
variable constant lol to 2 and then you have incremented it. :P


>
>
> On Mon, Aug 15, 2011 at 12:41 AM, aditi garg wrote:
>
>> lol
>>
>>
>> On Mon, Aug 15, 2011 at 12:40 AM, aditya kumar <
>> aditya.kumar130...@gmail.com> wrote:
>>
>>> @aditi : sry i dint realise that n > log n .:P
>>>
>>> On Mon, Aug 15, 2011 at 12:38 AM, aditi garg 
>>> wrote:
>>>
 @aditya : dis is obviously correct bt here complexity will be O(n) bt we
 are asked to gv O(log n) solution

 On Mon, Aug 15, 2011 at 12:37 AM, aditya kumar <
 aditya.kumar130...@gmail.com> wrote:

> for(j=0;j {
> if(a[j]==j)
>  return j;
>  else
>  continue ;
> }
>
> this shud also be correct right ??
>
> On Mon, Aug 15, 2011 at 12:31 AM, Akash Mukherjee 
> wrote:
>
>> just my 2 cents  in d binary search, replacing key with mid, ie
>> if(a[mid] > mid)
>> check lower half
>> else upper half
>>
>> should work??
>>
>>
>> On Mon, Aug 15, 2011 at 12:26 AM, aditi garg <
>> aditi.garg.6...@gmail.com> wrote:
>>
>>> Given an ordered array A[1…n] with numbers in strictly increasing
>>> order. Find a ‘j’ such that A [j]=j or -1 if no such number exist in
>>> o (log n).
>>>
>>> --
>>> 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.
>



 --
 Aditi Garg
 Undergraduate Student
 Electronics & Communication Divison
 NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
 Sector 3, Dwarka
 New Delhi


  --
 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.
>>>
>>
>>
>>
>> --
>> Aditi Garg
>> Undergraduate Student
>> Electronics & Communication Divison
>> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
>> Sector 3, Dwarka
>> New Delhi
>>
>>
>>  --
>> 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.
>



-- 
Regards
Siddharth Srivastava

-- 
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/algogeek

Re: [algogeeks] array ques

[sagar pareek]

int lol=2; // total lol's encountered upto now

lol++;

On Mon, Aug 15, 2011 at 12:41 AM, aditi garg wrote:

> lol
>
>
> On Mon, Aug 15, 2011 at 12:40 AM, aditya kumar <
> aditya.kumar130...@gmail.com> wrote:
>
>> @aditi : sry i dint realise that n > log n .:P
>>
>> On Mon, Aug 15, 2011 at 12:38 AM, aditi garg 
>> wrote:
>>
>>> @aditya : dis is obviously correct bt here complexity will be O(n) bt we
>>> are asked to gv O(log n) solution
>>>
>>> On Mon, Aug 15, 2011 at 12:37 AM, aditya kumar <
>>> aditya.kumar130...@gmail.com> wrote:
>>>
 for(j=0;j>>> {
 if(a[j]==j)
  return j;
  else
  continue ;
 }

 this shud also be correct right ??

 On Mon, Aug 15, 2011 at 12:31 AM, Akash Mukherjee 
 wrote:

> just my 2 cents  in d binary search, replacing key with mid, ie
> if(a[mid] > mid)
> check lower half
> else upper half
>
> should work??
>
>
> On Mon, Aug 15, 2011 at 12:26 AM, aditi garg <
> aditi.garg.6...@gmail.com> wrote:
>
>> Given an ordered array A[1…n] with numbers in strictly increasing
>> order. Find a ‘j’ such that A [j]=j or -1 if no such number exist in
>> o (log n).
>>
>> --
>> 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.

>>>
>>>
>>>
>>> --
>>> Aditi Garg
>>> Undergraduate Student
>>> Electronics & Communication Divison
>>> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
>>> Sector 3, Dwarka
>>> New Delhi
>>>
>>>
>>>  --
>>> 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.
>>
>
>
>
> --
> Aditi Garg
> Undergraduate Student
> Electronics & Communication Divison
> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
> Sector 3, Dwarka
> New Delhi
>
>
>  --
> 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 ques

[aditi garg]

lol

On Mon, Aug 15, 2011 at 12:40 AM, aditya kumar  wrote:

> @aditi : sry i dint realise that n > log n .:P
>
> On Mon, Aug 15, 2011 at 12:38 AM, aditi garg wrote:
>
>> @aditya : dis is obviously correct bt here complexity will be O(n) bt we
>> are asked to gv O(log n) solution
>>
>> On Mon, Aug 15, 2011 at 12:37 AM, aditya kumar <
>> aditya.kumar130...@gmail.com> wrote:
>>
>>> for(j=0;j>> {
>>> if(a[j]==j)
>>>  return j;
>>>  else
>>>  continue ;
>>> }
>>>
>>> this shud also be correct right ??
>>>
>>> On Mon, Aug 15, 2011 at 12:31 AM, Akash Mukherjee wrote:
>>>
 just my 2 cents  in d binary search, replacing key with mid, ie
 if(a[mid] > mid)
 check lower half
 else upper half

 should work??


 On Mon, Aug 15, 2011 at 12:26 AM, aditi garg >>> > wrote:

> Given an ordered array A[1…n] with numbers in strictly increasing
> order. Find a ‘j’ such that A [j]=j or -1 if no such number exist in
> o (log n).
>
> --
> 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.
>>>
>>
>>
>>
>> --
>> Aditi Garg
>> Undergraduate Student
>> Electronics & Communication Divison
>> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
>> Sector 3, Dwarka
>> New Delhi
>>
>>
>>  --
>> 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.
>



-- 
Aditi Garg
Undergraduate Student
Electronics & Communication Divison
NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
Sector 3, Dwarka
New Delhi

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

[aditya kumar]

@aditi : sry i dint realise that n > log n .:P

On Mon, Aug 15, 2011 at 12:38 AM, aditi garg wrote:

> @aditya : dis is obviously correct bt here complexity will be O(n) bt we
> are asked to gv O(log n) solution
>
> On Mon, Aug 15, 2011 at 12:37 AM, aditya kumar <
> aditya.kumar130...@gmail.com> wrote:
>
>> for(j=0;j> {
>> if(a[j]==j)
>>  return j;
>>  else
>>  continue ;
>> }
>>
>> this shud also be correct right ??
>>
>> On Mon, Aug 15, 2011 at 12:31 AM, Akash Mukherjee wrote:
>>
>>> just my 2 cents  in d binary search, replacing key with mid, ie
>>> if(a[mid] > mid)
>>> check lower half
>>> else upper half
>>>
>>> should work??
>>>
>>>
>>> On Mon, Aug 15, 2011 at 12:26 AM, aditi garg 
>>> wrote:
>>>
 Given an ordered array A[1…n] with numbers in strictly increasing
 order. Find a ‘j’ such that A [j]=j or -1 if no such number exist in
 o (log n).

 --
 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.
>>
>
>
>
> --
> Aditi Garg
> Undergraduate Student
> Electronics & Communication Divison
> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
> Sector 3, Dwarka
> New Delhi
>
>
>  --
> 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 ques

[shady]

lol

On Mon, Aug 15, 2011 at 12:38 AM, aditi garg wrote:

> @aditya : dis is obviously correct bt here complexity will be O(n) bt we
> are asked to gv O(log n) solution
>
>
> On Mon, Aug 15, 2011 at 12:37 AM, aditya kumar <
> aditya.kumar130...@gmail.com> wrote:
>
>> for(j=0;j> {
>> if(a[j]==j)
>>  return j;
>>  else
>>  continue ;
>> }
>>
>> this shud also be correct right ??
>>
>> On Mon, Aug 15, 2011 at 12:31 AM, Akash Mukherjee wrote:
>>
>>> just my 2 cents  in d binary search, replacing key with mid, ie
>>> if(a[mid] > mid)
>>> check lower half
>>> else upper half
>>>
>>> should work??
>>>
>>>
>>> On Mon, Aug 15, 2011 at 12:26 AM, aditi garg 
>>> wrote:
>>>
 Given an ordered array A[1…n] with numbers in strictly increasing
 order. Find a ‘j’ such that A [j]=j or -1 if no such number exist in
 o (log n).

 --
 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.
>>
>
>
>
> --
> Aditi Garg
> Undergraduate Student
> Electronics & Communication Divison
> NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
> Sector 3, Dwarka
> New Delhi
>
>
>  --
> 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 ques

[siddharth srivastava]

Hi

On 15 August 2011 00:37, aditya kumar  wrote:

> for(j=0;j {
> if(a[j]==j)
>  return j;
>  else
>  continue ;
> }
>
> this shud also be correct right ??
>


It is a O(n) algo

>
> On Mon, Aug 15, 2011 at 12:31 AM, Akash Mukherjee wrote:
>
>> just my 2 cents  in d binary search, replacing key with mid, ie
>> if(a[mid] > mid)
>> check lower half
>> else upper half
>>
>> should work??
>>
>>
>> On Mon, Aug 15, 2011 at 12:26 AM, aditi garg 
>> wrote:
>>
>>> Given an ordered array A[1…n] with numbers in strictly increasing
>>> order. Find a ‘j’ such that A [j]=j or -1 if no such number exist in
>>> o (log n).
>>>
>>> --
>>> 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.
>



-- 
Regards
Siddharth Srivastava

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

[aditi garg]

@aditya : dis is obviously correct bt here complexity will be O(n) bt we are
asked to gv O(log n) solution

On Mon, Aug 15, 2011 at 12:37 AM, aditya kumar  wrote:

> for(j=0;j {
> if(a[j]==j)
>  return j;
>  else
>  continue ;
> }
>
> this shud also be correct right ??
>
> On Mon, Aug 15, 2011 at 12:31 AM, Akash Mukherjee wrote:
>
>> just my 2 cents  in d binary search, replacing key with mid, ie
>> if(a[mid] > mid)
>> check lower half
>> else upper half
>>
>> should work??
>>
>>
>> On Mon, Aug 15, 2011 at 12:26 AM, aditi garg 
>> wrote:
>>
>>> Given an ordered array A[1…n] with numbers in strictly increasing
>>> order. Find a ‘j’ such that A [j]=j or -1 if no such number exist in
>>> o (log n).
>>>
>>> --
>>> 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.
>



-- 
Aditi Garg
Undergraduate Student
Electronics & Communication Divison
NETAJI SUBHAS INSTITUTE OF TECHNOLOGY
Sector 3, Dwarka
New Delhi

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

[aditya kumar]

for(j=0;jwrote:

> just my 2 cents  in d binary search, replacing key with mid, ie
> if(a[mid] > mid)
> check lower half
> else upper half
>
> should work??
>
>
> On Mon, Aug 15, 2011 at 12:26 AM, aditi garg wrote:
>
>> Given an ordered array A[1…n] with numbers in strictly increasing
>> order. Find a ‘j’ such that A [j]=j or -1 if no such number exist in
>> o (log n).
>>
>> --
>> 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 ques

[Akash Mukherjee]

just my 2 cents  in d binary search, replacing key with mid, ie
if(a[mid] > mid)
check lower half
else upper half

should work??


On Mon, Aug 15, 2011 at 12:26 AM, aditi garg wrote:

> Given an ordered array A[1…n] with numbers in strictly increasing
> order. Find a ‘j’ such that A [j]=j or -1 if no such number exist in
> o (log n).
>
> --
> 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 ques

[shady]

already discussed... binary search :)

On Mon, Aug 15, 2011 at 12:26 AM, aditi garg wrote:

> Given an ordered array A[1…n] with numbers in strictly increasing
> order. Find a ‘j’ such that A [j]=j or -1 if no such number exist in
> o (log n).
>
> --
> 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.