subject:"\[algogeeks\] array problem"

[algogeeks] Array problem

2013-08-07 Thread payel roy

There is a stream of numbers coming in and you have to find K largest
numbers out of the numbers received so far at any given time. Next problem
is that a constraint is added. memory is limited to m. m  k. How would you
achieve the goal still.

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

2012-12-11 Thread manish untwal

@wladimir yes the problem seems to be that!!

On Tue, Dec 11, 2012 at 10:13 AM, Wladimir Tavares wladimir...@gmail.comwrote:

 subset sum?
 Wladimir Araujo Tavares
 *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
 Homepage http://lia.ufc.br/%7Ewladimir/ | 
 Maratonahttps://sites.google.com/site/quixadamaratona/|
 *





 On Fri, Nov 16, 2012 at 2:46 AM, Pralay Biswas pralaybiswas2...@gmail.com
  wrote:

 Search for balance partitioning under Dynamic Programming. Doable in O(n)


 On Thu, Nov 15, 2012 at 8:16 PM, bharat b 
 bagana.bharatku...@gmail.comwrote:

 @ 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

2012-12-10 Thread Wladimir Tavares

subset sum?
Wladimir Araujo Tavares
*Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
Homepage http://lia.ufc.br/%7Ewladimir/ |
Maratonahttps://sites.google.com/site/quixadamaratona/|
*





On Fri, Nov 16, 2012 at 2:46 AM, Pralay Biswas
pralaybiswas2...@gmail.comwrote:

 Search for balance partitioning under Dynamic Programming. Doable in O(n)


 On Thu, Nov 15, 2012 at 8:16 PM, bharat b bagana.bharatku...@gmail.comwrote:

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


  --




--

Re: [algogeeks] Array problem

2012-11-22 Thread 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 dave_an...@juno.com 
 javascript: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


  -- 
  
  




--

[algogeeks] Array problem

2012-11-21 Thread Ansum Baid

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

2012-11-21 Thread 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

2012-11-21 Thread Ansum Baid

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

On Wed, Nov 21, 2012 at 6:52 PM, Dave dave_and_da...@juno.com 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

2012-11-16 Thread 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 vishal.cs.b...@gmail.com
 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 bagana.bharatku...@gmail.comwrote:

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


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.

[algogeeks] Array Problem

2012-11-15 Thread Arun Kindra

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.

Re: [algogeeks] Array Problem

2012-11-15 Thread 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 reserve4placem...@gmail.comwrote:

 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

2012-11-15 Thread 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
vishal.cs.b...@gmail.comwrote:

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

 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

2012-11-15 Thread 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 bagana.bharatku...@gmail.comwrote:

 @ 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.comwrote:

 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

2012-09-16 Thread 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=Staticd1=tutorialsd2=lowestCommonAncestor
  

 On Thu, Sep 6, 2012 at 4:51 PM, bharat b bagana.bh...@gmail.comjavascript:
  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@gmail.comjavascript:
  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


 #includestdio.h
 #includemath.h
 int main()
 {
 int list[5],i,n,j,sum,k,l;char c;long t;
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,n);
 for(i=0;in;i++)
 {
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,list[i]);


 }
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%ld,t);


 t=2*t;
 while(t)
 {
 sum=0;
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%c,c);


 fflush(stdin);
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d
 %d,k,l);   


 if(c=='Q')
 {
 for(i=k-1;il-1;i++)
 {
 for(j=i+1;jl;j++)
 {
if(list[i]==list[j])
   break;
else if((j==l-1) (list[i]!=list[j]))


{
   sum=sum+list[i];

}
 }
  }

  printf 
 http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(%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.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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

2012-09-06 Thread 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


 #includestdio.h
 #includemath.h
 int main()
 {
 int list[5],i,n,j,sum,k,l;char c;long t;
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,n);
 for(i=0;in;i++)
 {
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,list[i]);
 }
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%ld,t);
 t=2*t;
 while(t)
 {
 sum=0;
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%c,c);
 fflush(stdin);
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d  
   %d,k,l);
 if(c=='Q')
 {
 for(i=k-1;il-1;i++)
 {
 for(j=i+1;jl;j++)
 {
if(list[i]==list[j])
   break;
else if((j==l-1) (list[i]!=list[j]))
{
   sum=sum+list[i];

}
 }
  }

  printf 
 http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(%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

2012-09-06 Thread srikanth reddy malipatel

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

http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor


On Thu, Sep 6, 2012 at 4:51 PM, bharat b bagana.bharatku...@gmail.comwrote:

 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


 #includestdio.h
 #includemath.h
 int main()
 {
 int list[5],i,n,j,sum,k,l;char c;long t;
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,n);
 for(i=0;in;i++)
 {
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,list[i]);

 }
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%ld,t);

 t=2*t;
 while(t)
 {
 sum=0;
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%c,c);

 fflush(stdin);
 scanf 
 http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d 
%d,k,l);

 if(c=='Q')
 {
 for(i=k-1;il-1;i++)
 {
 for(j=i+1;jl;j++)
 {
if(list[i]==list[j])
   break;
else if((j==l-1) (list[i]!=list[j]))

{
   sum=sum+list[i];

}
 }
  }

  printf 
 http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(%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

2012-09-06 Thread 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

2012-03-14 Thread 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 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;in;i++)
   sum[i] = 0;

 for(int i=0;in;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 atul.87fri...@gmail.comwrote:

 @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 pkjee2...@gmail.comwrote:

 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

2012-03-14 Thread 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 dheerajsharma1...@gmail.com
 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;in;i++)
   sum[i] = 0;

 for(int i=0;in;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 atul.87fri...@gmail.comwrote:

 @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 pkjee2...@gmail.comwrote:

 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

2012-03-13 Thread 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 pkjee2...@gmail.com 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

2012-03-13 Thread 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;in;i++)
  sum[i] = 0;

for(int i=0;in;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 atul.87fri...@gmail.comwrote:

 @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 pkjee2...@gmail.comwrote:

 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

2012-03-12 Thread sanjiv yadav

u r right.

On Mon, Mar 12, 2012 at 11:17 AM, atul anand atul.87fri...@gmail.comwrote:

 @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 sanjiv2009...@gmail.comwrote:

 @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 atul.87fri...@gmail.comwrote:

 @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 pkjee2...@gmail.comwrote:

 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

2012-03-12 Thread Piyush Kapoor

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

On Mon, Mar 12, 2012 at 11:53 AM, sanjiv yadav sanjiv2009...@gmail.comwrote:

 u r right.


 On Mon, Mar 12, 2012 at 11:17 AM, atul anand atul.87fri...@gmail.comwrote:

 @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 
 sanjiv2009...@gmail.comwrote:

 @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 atul.87fri...@gmail.comwrote:

 @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 pkjee2...@gmail.comwrote:

 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

2012-03-12 Thread 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 pkjee2...@gmail.com wrote:

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


 On Mon, Mar 12, 2012 at 11:53 AM, sanjiv yadav sanjiv2009...@gmail.comwrote:

 u r right.


 On Mon, Mar 12, 2012 at 11:17 AM, atul anand atul.87fri...@gmail.comwrote:

 @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 
 sanjiv2009...@gmail.comwrote:

 @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 
 atul.87fri...@gmail.comwrote:

 @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 
 pkjee2...@gmail.comwrote:

 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

2012-03-12 Thread 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

2012-03-12 Thread 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 pkjee2...@gmail.com 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

2012-03-12 Thread 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 atul.87fri...@gmail.comwrote:

 @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 
 sunny816.i...@gmail.comwrote:

 @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 atul.87fri...@gmail.comwrote:

 @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 gpt.pa...@gmail.comwrote:

 @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 pkjee2...@gmail.comwrote:

 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/algogeeks?hl=en.

[algogeeks] Array problem

2012-03-11 Thread Gaurav Popli

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.

Re: [algogeeks] Array problem

2012-03-11 Thread payal gupta

By Augmented BST-
TC-O(n)

On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote:

 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

2012-03-11 Thread 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 gpt.pa...@gmail.com wrote:

 By Augmented BST-
 TC-O(n)


 On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli gpgaurav.n...@gmail.comwrote:

 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

2012-03-11 Thread 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 pkjee2...@gmail.com 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

2012-03-11 Thread 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 gpt.pa...@gmail.com 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 sanjiv2009...@gmail.comwrote:

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


 On Sun, Mar 11, 2012 at 6:10 PM, payal gupta gpt.pa...@gmail.com wrote:

 By Augmented BST-
 TC-O(n)


 On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli 
 gpgaurav.n...@gmail.comwrote:

 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

2012-03-11 Thread 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 pkjee2...@gmail.com 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

2012-03-11 Thread 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 atul.87fri...@gmail.comwrote:

 @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 pkjee2...@gmail.comwrote:

 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

2012-03-11 Thread 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 sanjiv2009...@gmail.comwrote:

 @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 atul.87fri...@gmail.comwrote:

 @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 pkjee2...@gmail.comwrote:

 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

2012-02-16 Thread 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=enlnk=gstq=Array+Problem+%2B+tushar#6632ae276b99d4ad

On Thu, Feb 16, 2012 at 5:54 PM, Devansh Gupta devanshgupta...@gmail.comwrote:

On 2/16/12, Amol Sharma amolsharm...@gmail.com wrote:
k,n,b are known and 0bk
--

Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99
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 saurab...@gmail.com
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
amolsharm...@gmail.comwrote:

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

--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

2012-02-16 Thread 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
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/

On Thu, Feb 16, 2012 at 11:30 PM, atul anand atul.87fri...@gmail.comwrote:

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=enlnk=gstq=Array+Problem+%2B+tushar#6632ae276b99d4ad

On Thu, Feb 16, 2012 at 5:54 PM, Devansh Gupta
devanshgupta...@gmail.comwrote:

On 2/16/12, Amol Sharma amolsharm...@gmail.com wrote:
k,n,b are known and 0bk
--

On Thu, Feb 16, 2012 at 7:56 AM, saurabh singh saurab...@gmail.com
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
amolsharm...@gmail.comwrote:

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

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

[algogeeks] Array Problem

2012-02-14 Thread TUSHAR

Given an array of size N having numbers in the range 0 to k where
k=N, preprocess the array inplace and in linear time in such a way
that after preprocessing you should be able to return count of the
input element in O(1).

Please give some idea !!
Thanks..

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

2012-02-14 Thread 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 Problem

2012-02-14 Thread 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 kartik.sac...@gmail.comwrote:

 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.

[algogeeks] Array Problem??

2011-10-03 Thread Vikram Singh

Given an array say A=(4,3,1,2). An array B is formed out of this in
such a way that B[i] = no. of elements in A, occuring on rhs of A[i],
which are less then A[i].
eg.for the A given, B is (3,2,0,0).
Here A of length n only contains elements from 1 to n that too
distinct..
Now the problem is:
1). You are given with any such A. Find out corresponding B?

2). You are given with any such B. Find out corresponding A?

Please provide solution in O(n),if possible??

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] ARRAY PROBLEM

2011-09-29 Thread 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
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99





On Thu, Sep 29, 2011 at 10:39 AM, kartik sachan kartik.sac...@gmail.comwrote:

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

2011-09-29 Thread Amol Sharma

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


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
 http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99





On Thu, Sep 29, 2011 at 11:52 AM, Amol Sharma amolsharm...@gmail.comwrote:

 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
 http://gplus.to/amolsharma99 
 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99





 On Thu, Sep 29, 2011 at 10:39 AM, kartik sachan 
 kartik.sac...@gmail.comwrote:

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

2011-09-29 Thread UTKARSH SRIVASTAV

@Amol +1

On Thu, Sep 29, 2011 at 11:52 AM, Amol Sharma amolsharm...@gmail.comwrote:

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
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99

On Thu, Sep 29, 2011 at 10:39 AM, kartik sachan
kartik.sac...@gmail.comwrote:

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.

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

2011-09-29 Thread 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 usrivastav...@gmail.com
wrote:

@Amol +1

On Thu, Sep 29, 2011 at 11:52 AM, Amol Sharma amolsharm...@gmail.comwrote:

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)

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
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99

On Thu, Sep 29, 2011 at 10:39 AM, kartik sachan
kartik.sac...@gmail.comwrote:

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.

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

2011-09-29 Thread 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

2011-09-29 Thread DIVIJ WADHAWAN

Impossible to solve in O(n) I suppose

On Thu, Sep 29, 2011 at 12:34 PM, kartik sachan kartik.sac...@gmail.comwrote:

 @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

2011-09-29 Thread 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
http://gplus.to/amolsharma99
http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://youtube.com/amolsharma99

On Thu, Sep 29, 2011 at 12:58 PM, DIVIJ WADHAWAN divij...@gmail.com wrote:

Impossible to solve in O(n) I suppose

On Thu, Sep 29, 2011 at 12:34 PM, kartik sachan
kartik.sac...@gmail.comwrote:

@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

2011-09-29 Thread 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

2011-09-29 Thread apoorv gupta

sachan!!amol ke rum par jaakar pooch le.

On Thu, Sep 29, 2011 at 1:10 PM, kartik sachan kartik.sac...@gmail.comwrote:

 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

2011-09-29 Thread 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á http://lia.ufc.br/%7Ewladimir/
Homepage http://lia.ufc.br/%7Ewladimir/ |
Maratonahttps://sites.google.com/site/quixadamaratona/|
*

On Thu, Sep 29, 2011 at 5:28 AM, apoorv gupta apoorvcool2...@gmail.comwrote:

sachan!!amol ke rum par jaakar pooch le.

On Thu, Sep 29, 2011 at 1:10 PM, kartik sachan kartik.sac...@gmail.comwrote:

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

2011-09-29 Thread Wladimir Tavares

First,
you need change 0 to -1
Wladimir Araujo Tavares
*Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
Homepage http://lia.ufc.br/%7Ewladimir/ |
Maratonahttps://sites.google.com/site/quixadamaratona/|
*

On Thu, Sep 29, 2011 at 7:35 AM, Wladimir Tavares wladimir...@gmail.comwrote:

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á http://lia.ufc.br/%7Ewladimir/
Homepage http://lia.ufc.br/%7Ewladimir/ |
Maratonahttps://sites.google.com/site/quixadamaratona/|
*

On Thu, Sep 29, 2011 at 5:28 AM, apoorv gupta apoorvcool2...@gmail.comwrote:

sachan!!amol ke rum par jaakar pooch le.

On Thu, Sep 29, 2011 at 1:10 PM, kartik sachan
kartik.sac...@gmail.comwrote:

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.

[algogeeks] ARRAY PROBLEM

2011-09-28 Thread kartik sachan

   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.

Re: [algogeeks] array problem

2011-08-21 Thread 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 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.




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

2011-08-21 Thread 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 srn...@gmail.com 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 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.
 
 


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

2011-08-21 Thread Dheeraj Sharma

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

On 8/21/11, 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.




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

2011-08-21 Thread 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;jn;j++)
{
if(a[j]  i)
{
one++;
}
else
{
zero++;
}
}
if(one  zero)
{
printf(1s are more \n);
}
else
{
printf(0s are more \n);
}
i=i1;
}

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


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

2011-08-21 Thread 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 srn...@gmail.com 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;jn;j++)
 {
 if(a[j]  i)
 {
 one++;
 }
 else
 {
 zero++;
 }
 }
 if(one  zero)
 {
 printf(1s are more \n);
 }
 else
 {
 printf(0s are more \n);
 }
 i=i1;
 }

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


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

2011-08-21 Thread Dheeraj Sharma

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

On 8/21/11, 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.




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

2011-08-14 Thread Yasir

any O(nlogn) solution?

-- 
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/-/7Q8DHLIlbDoJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

2011-05-23 Thread Azazle simon

@ps: ..:-)

On 5/22/11, Piyush Sinha ecstasy.piy...@gmail.com wrote:
 @MONSIEUR..
 someone once saidTHE SECRET OF SUCCESS IS TO NEVER REVEAL YOUR
 SOURCES... ;)...:P..:P

 On 5/22/11, MONSIEUR monsieur@gmail.com wrote:
 @piyush: excellent buddybtw what was the initial
 spark...???.:-)

 On May 21, 1:01 pm, Piyush Sinha ecstasy.piy...@gmail.com wrote:
 @Amit JaspalThe algo given by me works for the given case..check
 it

 On 5/20/11, Anurag Bhatia abhati...@gmail.com wrote:



  Just need some clarification; sorry I joined the thread late. What are
  we
  trying maximize? A[j] -A[i] such that ij? or j-i such that A[i]A[j]?

  --Anurag

  On Fri, May 20, 2011 at 12:34 AM, Kunal Patil kp101...@gmail.com
  wrote:

  @ Piyush: Excellent Solution...It appears both Correct and O(n)...Good
  work !![?]

  Just a minor correction in your algo.[?]

  while(B[i]C[j])
   j++;
  must also check for J's bound as:
  while ( j  ( sizeof(A)/sizeof(A[0]) )  B[i]C[j] )
   j++;
  Or it will crash when J goes out of bound and we try to reference
  C[j].

  Nywayz..thnx for the solution and algo !!

  --
  You received this message because you are subscribed to the Google
  Groups
  Algorithm Geeks group.
  To post to this group, send email to algogeeks@googlegroups.com.
  To unsubscribe from 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.

 --
 *Piyush Sinha*
 *IIIT, Allahabad*
 *+91-8792136657*
 *+91-7483122727*
 *https://www.facebook.com/profile.php?id=10655377926*

  363.gif
  1KViewDownload

  360.gif
  1KViewDownload

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 *Piyush Sinha*
 *IIIT, Allahabad*
 *+91-8792136657*
 *+91-7483122727*
 *https://www.facebook.com/profile.php?id=10655377926 *

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



-- 
Sent from my mobile device

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

2011-05-21 Thread Piyush Sinha

@Amit JaspalThe algo given by me works for the given case..check it

On 5/20/11, Anurag Bhatia abhati...@gmail.com wrote:
 Just need some clarification; sorry I joined the thread late. What are we
 trying maximize? A[j] -A[i] such that ij? or j-i such that A[i]A[j]?

 --Anurag

 On Fri, May 20, 2011 at 12:34 AM, Kunal Patil kp101...@gmail.com wrote:

 @ Piyush: Excellent Solution...It appears both Correct and O(n)...Good
 work !![?]

 Just a minor correction in your algo.[?]

 while(B[i]C[j])
  j++;
 must also check for J's bound as:
 while ( j  ( sizeof(A)/sizeof(A[0]) )  B[i]C[j] )
  j++;
 Or it will crash when J goes out of bound and we try to reference C[j].

 Nywayz..thnx for the solution and algo !!

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.



-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

363.gif360.gif

Re: [algogeeks] Array problem

2011-05-20 Thread Terence


Try this case:
1000 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 1

On 2011-5-18 0:27, Kunal Patil wrote:

Ohh..If it is so...Sorry !!  I understood it the different way...
But if the question is as mentioned in your 2nd case then also I 
believe there is O(n) solution.


Maintain
two pointers: *START* and *END*
two variables: max1 and max2
Assume arr[MAX_SIZE] to be the array containing the given elements.

Algorithm:
*1) Initially, make START point to zeroth element and END pointing to 
last element of the array.

2) Calculate max1 as:
2a) Compare arr[**START**] and arr[**END**].
   If arr[**START**]  arr[**END**]
  {
 max1 = **END**- **START**;
 Jump to 3rd step
  }
2b) If arr[**START**] = arr[**END**]
   {
**END**-- ;
 jump to step 2a and repeat this procedure 
till **END**!= **START*

*   }
3) Reset **END**so that it points to last element of the array.
4) Calculate max2 as:
4a) Compare arr[**START**] and arr[**END**].
   If arr[**START**]  arr[**END**]
  {
 max2 = **END**- **START**;
 Jump to 5th step
  }
4b) If arr**[START**] = arr[**END**]
   {
**START**++ ;
 jump to step 4a and repeat this procedure 
till **START**!= **END*

*   }
5) Return max( max1, max2)*

Hope this algo is clear.
This algo makes two passes over the array. Thus it is O(2n) = O(n)..
Let me know if this algo fails for any case you can think of..
--
You received this message because you are subscribed to the Google 
Groups Algorithm Geeks group.

To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.

image/gifimage/gifimage/gifimage/gifimage/gif

Re: [algogeeks] Array problem

2011-05-20 Thread Amit Jaspal

@ Above

I think your solution would not work for A[] = {9,6,3,2,8,1}

Ans is A[4]-A[1]  0 i.e 4-1 = 3.

On Tue, May 17, 2011 at 9:57 PM, Kunal Patil kp101...@gmail.com wrote:

 Ohh..If it is so...Sorry !![?]  I understood it the different way...[?]
 But if the question is as mentioned in your 2nd case then also I believe
 there is O(n) solution.[?]

 Maintain
 two pointers: *START* and *END*
 two variables: max1 and max2
 Assume arr[MAX_SIZE] to be the array containing the given elements.

 Algorithm:
 *1) Initially, make START point to zeroth element and END pointing to last
 element of the array.
 2) Calculate max1 as:
 2a) Compare arr[**START**] and arr[**END**].
If arr[**START**]  arr[**END**]
   {
  max1 = **END** - **START**;
  Jump to 3rd step
   }
 2b) If arr[**START**] = arr[**END**]
{
  **END**-- ;
  jump to step 2a and repeat this procedure till **
 END** != **START*
 *   }
 3) Reset **END** so that it points to last element of the array.
 4) Calculate max2 as:
 4a) Compare arr[**START**] and arr[**END**].
If arr[**START**]  arr[**END**]
   {
  max2 = **END** - **START**;
  Jump to 5th step
   }
 4b) If arr**[START**] = arr[**END**]
{
 **START**++ ;
  jump to step 4a and repeat this procedure till **
 START** != **END*
 *}
 5) Return max( max1, max2)*

 Hope this algo is clear.
 This algo makes two passes over the array. Thus it is O(2n) = O(n)..[?]
 Let me know if this algo fails for any case you can think of..[?]

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Amit Jaspal.

Men do less than they ought,
unless they do all they can

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

363.gif361.gif33D.gif322.gif360.gif

Re: [algogeeks] Array problem

2011-05-20 Thread Anurag Bhatia

Just need some clarification; sorry I joined the thread late. What are we
trying maximize? A[j] -A[i] such that ij? or j-i such that A[i]A[j]?

--Anurag

On Fri, May 20, 2011 at 12:34 AM, Kunal Patil kp101...@gmail.com wrote:

 @ Piyush: Excellent Solution...It appears both Correct and O(n)...Good work
 !![?]

 Just a minor correction in your algo.[?]

 * while(B[i]C[j]) *
 * j++;
 must also check for J's bound as:
 **while ( j  ( sizeof(A)/sizeof(A[0]) )*  *B[i]C[j] )
  j++;
 Or it will crash when J goes out of bound and we try to reference C[j].

 Nywayz..thnx for the solution and algo !!
 *

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.

363.gif360.gif

Re: [algogeeks] Array problem

2011-05-19 Thread Kunal Patil

@ Piyush: Excellent Solution...It appears both Correct and O(n)...Good work
!![?]

Just a minor correction in your algo.[?]
* while(B[i]C[j]) *
* j++;
must also check for J's bound as:
**while ( j  ( sizeof(A)/sizeof(A[0]) )*  *B[i]C[j] )
 j++;
Or it will crash when J goes out of bound and we try to reference C[j].

Nywayz..thnx for the solution and algo !!
*

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

363.gif360.gif

Re: [algogeeks] Array problem

2011-05-18 Thread amit kumar

@kunal patil
your soln does not work for
5 3 4 5 3 3

On Tue, May 17, 2011 at 9:57 PM, Kunal Patil kp101...@gmail.com wrote:

 Ohh..If it is so...Sorry !![?]  I understood it the different way...[?]
 But if the question is as mentioned in your 2nd case then also I believe
 there is O(n) solution.[?]

 Maintain
 two pointers: *START* and *END*
 two variables: max1 and max2
 Assume arr[MAX_SIZE] to be the array containing the given elements.

 Algorithm:
 *1) Initially, make START point to zeroth element and END pointing to last
 element of the array.
 2) Calculate max1 as:
 2a) Compare arr[**START**] and arr[**END**].
If arr[**START**]  arr[**END**]
   {
  max1 = **END** - **START**;
  Jump to 3rd step
   }
 2b) If arr[**START**] = arr[**END**]
{
  **END**-- ;
  jump to step 2a and repeat this procedure till **
 END** != **START*
 *   }
 3) Reset **END** so that it points to last element of the array.
 4) Calculate max2 as:
 4a) Compare arr[**START**] and arr[**END**].
If arr[**START**]  arr[**END**]
   {
  max2 = **END** - **START**;
  Jump to 5th step
   }
 4b) If arr**[START**] = arr[**END**]
{
 **START**++ ;
  jump to step 4a and repeat this procedure till **
 START** != **END*
 *}
 5) Return max( max1, max2)*

 Hope this algo is clear.
 This algo makes two passes over the array. Thus it is O(2n) = O(n)..[?]
 Let me know if this algo fails for any case you can think of..[?]

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.

363.gif361.gif33D.gif322.gif360.gif

Re: [algogeeks] Array problem

2011-05-18 Thread amit kumar

i dnt htink a o(n) soln exists for this problem.

On Wed, May 18, 2011 at 3:47 PM, amit kumar amitthecoo...@gmail.com wrote:

 @kunal patil
 your soln does not work for
 5 3 4 5 3 3

 On Tue, May 17, 2011 at 9:57 PM, Kunal Patil kp101...@gmail.com wrote:

 Ohh..If it is so...Sorry !![?]  I understood it the different way...[?]
 But if the question is as mentioned in your 2nd case then also I believe
 there is O(n) solution.[?]

 Maintain
 two pointers: *START* and *END*
 two variables: max1 and max2
 Assume arr[MAX_SIZE] to be the array containing the given elements.

 Algorithm:
 *1) Initially, make START point to zeroth element and END pointing to
 last element of the array.
 2) Calculate max1 as:
 2a) Compare arr[**START**] and arr[**END**].
If arr[**START**]  arr[**END**]
   {
  max1 = **END** - **START**;
  Jump to 3rd step
   }
 2b) If arr[**START**] = arr[**END**]
{
  **END**-- ;
  jump to step 2a and repeat this procedure till *
 *END** != **START*
 *   }
 3) Reset **END** so that it points to last element of the array.
 4) Calculate max2 as:
 4a) Compare arr[**START**] and arr[**END**].
If arr[**START**]  arr[**END**]
   {
  max2 = **END** - **START**;
  Jump to 5th step
   }
 4b) If arr**[START**] = arr[**END**]
{
 **START**++ ;
  jump to step 4a and repeat this procedure till *
 *START** != **END*
 *}
 5) Return max( max1, max2)*

 Hope this algo is clear.
 This algo makes two passes over the array. Thus it is O(2n) = O(n)..[?]
 Let me know if this algo fails for any case you can think of..[?]

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.

363.gif361.gif33D.gif322.gif360.gif

Re: [algogeeks] Array problem

2011-05-18 Thread Kunal Patil

@Amit: Ohh..Your test case is correct but not my solution..[?]
It only works if it is guaranteed that one end will be at the extreme of the
array ! (UseLess ! [?])
Sorry folks...
So can anybody prove that O(n) solution does not exist for this problem? [?]

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

35F.gif33A.gif320.gif

Re: [algogeeks] Array problem

2011-05-18 Thread Piyush Sinha

I think it can be done in O(n) but the auxilliary space required will be
more... in the solution which i have got its in the order of 2n

On Wed, May 18, 2011 at 4:44 PM, Kunal Patil kp101...@gmail.com wrote:

 @Amit: Ohh..Your test case is correct but not my solution..[?]
 It only works if it is guaranteed that one end will be at the extreme of
 the array ! (UseLess ! [?])
 Sorry folks...
 So can anybody prove that O(n) solution does not exist for this problem?
 [?]

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

35F.gif33A.gif320.gif

Re: [algogeeks] Array problem

2011-05-18 Thread Piyush Sinha

last night i was going through a similar kind of question and tried to
implement its algo in this question...If anyone finds any counter example
for it, please do comment..

Algo:-

*Let the array be A[].
We can keep two arrays B[] and C[] which will do the following work..
B[i] will store the minimum value in A[] till ith index
C[i] will store the maximum value (starting from the end) in A[i] till ith
index.*

*Lets say taking amit's example...*

*A[] = { 5 3 4 5 3 3 }*

*then B[] = {5,3,3,3,3,3}; //starting from the beginning.
and C[] = {5,5,5,5,3,3}; //starting from the end*

*the we can take two pointers i and j and a max_diff (all initialised to 0)
and run the following loop*
*while(j(sizeof(A)/sizeof(A[0])))
{
while(B[i]C[j]) *
* j++;
if(max_diffj-i-1)
max_diff = j-i-1;
i++;
j++;
}

the code for creating B[] and C[] can be as follows...
let N = (sizeof(A)/sizeof(A[0]))
B[0] = A[0];
for(i=1;iN;i++)
{
   B[i] = ((A[i]B[i-1])?A[i]:B[i-1]);
}
C[N-1] = A[N-1];
for(i=N-2;i=0;i--)
{
   C[i] = ((A[i]B[i+1])?A[i]:B[i+1]);
}*

For the given example, answer is coming to be j = 4,i=1,max_diff = 4-1-1 = 2

I hope I am clear... [?]

On Wed, May 18, 2011 at 4:52 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote:

 I think it can be done in O(n) but the auxilliary space required will be
 more... in the solution which i have got its in the order of 2n


 On Wed, May 18, 2011 at 4:44 PM, Kunal Patil kp101...@gmail.com wrote:

 @Amit: Ohh..Your test case is correct but not my solution..[?]
 It only works if it is guaranteed that one end will be at the extreme of
 the array ! (UseLess ! [?])
 Sorry folks...
 So can anybody prove that O(n) solution does not exist for this problem?
 [?]

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
   *Piyush Sinha*
 *IIIT, Allahabad*
 *+91-8792136657*
 *+91-7483122727*
 *https://www.facebook.com/profile.php?id=10655377926 *




-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

35F.gif33A.gif330.gif320.gif

Re: [algogeeks] Array problem

2011-05-17 Thread Kunal Patil

Ohh..If it is so...Sorry !![?]  I understood it the different way...[?]
But if the question is as mentioned in your 2nd case then also I believe
there is O(n) solution.[?]

Maintain
two pointers: *START* and *END*
two variables: max1 and max2
Assume arr[MAX_SIZE] to be the array containing the given elements.

Algorithm:
*1) Initially, make START point to zeroth element and END pointing to last
element of the array.
2) Calculate max1 as:
2a) Compare arr[**START**] and arr[**END**].
   If arr[**START**]  arr[**END**]
  {
 max1 = **END** - **START**;
 Jump to 3rd step
  }
2b) If arr[**START**] = arr[**END**]
   {
 **END**-- ;
 jump to step 2a and repeat this procedure till **
END** != **START*
*   }
3) Reset **END** so that it points to last element of the array.
4) Calculate max2 as:
4a) Compare arr[**START**] and arr[**END**].
   If arr[**START**]  arr[**END**]
  {
 max2 = **END** - **START**;
 Jump to 5th step
  }
4b) If arr**[START**] = arr[**END**]
   {
**START**++ ;
 jump to step 4a and repeat this procedure till **
START** != **END*
*}
5) Return max( max1, max2)*

Hope this algo is clear.
This algo makes two passes over the array. Thus it is O(2n) = O(n)..[?]
Let me know if this algo fails for any case you can think of..[?]

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

363.gif361.gif33D.gif322.gif360.gif

Re: [algogeeks] Array problem

2011-05-16 Thread anuj agarwal

How about create a BST and then, for each node find the difference between
the node and its child and do this for all except leaf nodes.
If u want i will write the code for the same.

Anuj Agarwal

Engineering is the art of making what you want from things you can get.


On Mon, May 16, 2011 at 11:20 AM, anshu mishra anshumishra6...@gmail.comwrote:

 @amit ur code is wrong. just check it for this {5, 4, 1, 8, 4, 4};

 --the
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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

2011-05-16 Thread Piyush Sinha

how about this??

*int maxinterval(int a[],int i,int j)
{
 if(i==j)
  return 0;
 int max1 = 0,max2;
 max2 = maxinterval(a,i+1,j);
 while(ij)
 {
  if(a[i]a[j])
  {
   if(j-i)max1)
max1 =j-i;
  }
  i++;
 }
 return(max1max2?max1:max2);
}
*
On Mon, May 16, 2011 at 11:36 AM, anuj agarwal coolbuddy...@gmail.comwrote:

 How about create a BST and then, for each node find the difference between
 the node and its child and do this for all except leaf nodes.
 If u want i will write the code for the same.

 Anuj Agarwal

 Engineering is the art of making what you want from things you can get.


  On Mon, May 16, 2011 at 11:20 AM, anshu mishra anshumishra6...@gmail.com
  wrote:

 @amit ur code is wrong. just check it for this {5, 4, 1, 8, 4, 4};

 --the
   You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.




-- 
PIYUSH SINHA
9936757773

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

2011-05-16 Thread anuj agarwal

Kunal,
Your solution runs in O(n) time but it is a wrong solution. It will run fine
if the array is sorted.

Anuj Agarwal

Engineering is the art of making what you want from things you can get.


On Mon, May 16, 2011 at 7:17 PM, Kunal Patil kp101...@gmail.com wrote:

 @Piyush Sinha: I doubt correctness of your solution. And even if it gets
 out to be correct It is not O(n)
 My approach:
 Maintain 2 variables: curr_max and prev_max to keep knowledge about current
 maximum length and previous maximum length.

 Algorithm:

 *initialize curr_max and prev_max to 1

 for i=0 to size-2
if next element of array is greater than current element
  {
   increment curr_max;
   check whether curr_max is greater than prev_max, if yes,
 assign   curr_max to prev_max;
  }
else // next element is smaller than or equal to current element
  reset curr_max to 1;
 //End for

 Finally return prev_max*

 This is clearly O(n) as it iterates through array only once.

 --
  You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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

2011-05-16 Thread Piyush Sinha

@kunal..

anuj is right..ur code works only for sorted array...and I missed the
part of doing it in O(n) time...I don't think there is way of doing it
in O(n) time...if its there and if amit knows the solution, he should
provide some hints...

On 5/16/11, anuj agarwal coolbuddy...@gmail.com wrote:
 Kunal,
 Your solution runs in O(n) time but it is a wrong solution. It will run fine
 if the array is sorted.

 Anuj Agarwal

 Engineering is the art of making what you want from things you can get.


 On Mon, May 16, 2011 at 7:17 PM, Kunal Patil kp101...@gmail.com wrote:

 @Piyush Sinha: I doubt correctness of your solution. And even if it gets
 out to be correct It is not O(n)
 My approach:
 Maintain 2 variables: curr_max and prev_max to keep knowledge about
 current
 maximum length and previous maximum length.

 Algorithm:

 *initialize curr_max and prev_max to 1

 for i=0 to size-2
if next element of array is greater than current element
  {
   increment curr_max;
   check whether curr_max is greater than prev_max, if yes,
 assign   curr_max to prev_max;
  }
else // next element is smaller than or equal to current element
  reset curr_max to 1;
 //End for

 Finally return prev_max*

 This is clearly O(n) as it iterates through array only once.

 --
  You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from 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.




-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

2011-05-16 Thread Kunal Patil

@Anuj  Piyush:
You didn't get the algo. It works on unsorted array also. You might have
missed the statement
*else // next element is smaller than or equal to current element
 reset curr_max to 1;*
Here, the comment itself shows unsorted elements have been taken into
consideration.
If you still have the doubt let me know.
Here is code for you:

#includecstdio#define MAX_SIZE 10
int maxinterval(int a[],int size){
int curr_max=1, prev_max=1;

for(int k=0;ksize-1;k++)
{
if(a[k]  a[k+1])
{
  curr_max++;

  if(curr_max  prev_max)
  {
prev_max=curr_max;
  }
}
else
  curr_max=1;
}
return prev_max;}
int main(){
int arr[MAX_SIZE] = {19,18,17,21,22,23,24};
printf(%d\n,maxinterval(arr,7) );
getchar();}

As expected it gives output 5.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

2011-05-16 Thread Piyush Sinha

@kunal

i think we both understood the problem differently...thats what i
asked from amit..that whether in the window is it neccessary the
elements in between should also be in increasing order or only the end
elements should have the relation of one being greater than the
other...I too thought for the same kind of algo had it been the first
case...but i think its the second case amit is asking forand if it
is so..ur answer is wrong...it should be 6(j-i=6-0=6)

On 5/17/11, Kunal Patil kp101...@gmail.com wrote:
 @Anuj  Piyush:
 You didn't get the algo. It works on unsorted array also. You might have
 missed the statement
 *else // next element is smaller than or equal to current element
  reset curr_max to 1;*
 Here, the comment itself shows unsorted elements have been taken into
 consideration.
 If you still have the doubt let me know.
 Here is code for you:

 #includecstdio#define MAX_SIZE 10
 int maxinterval(int a[],int size){
 int curr_max=1, prev_max=1;

 for(int k=0;ksize-1;k++)
 {
 if(a[k]  a[k+1])
 {
   curr_max++;

   if(curr_max  prev_max)
   {
 prev_max=curr_max;
   }
 }
 else
   curr_max=1;
 }
 return prev_max;}
 int main(){
 int arr[MAX_SIZE] = {19,18,17,21,22,23,24};
 printf(%d\n,maxinterval(arr,7) );
 getchar();}

 As expected it gives output 5.

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.com.
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
*Piyush Sinha*
*IIIT, Allahabad*
*+91-8792136657*
*+91-7483122727*
*https://www.facebook.com/profile.php?id=10655377926 *

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

2011-05-15 Thread Piyush Sinha

@amit jaspal

I have doubt with your question...in the maximum window found i.e.
A[i..j]...the elements should be in increasing order or only the end
elements should have the relation of A[i]A[j]??

On Fri, May 13, 2011 at 1:54 AM, amit amitjaspal...@gmail.com wrote:

 Given an array A[i..j] find out maximum j-i such that A[i]a[j] 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.




-- 
PIYUSH SINHA
9936757773

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

2011-05-15 Thread anshu mishra

@amit ur code is wrong. just check it for this {5, 4, 1, 8, 4, 4};

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Array problem

2011-05-13 Thread amit

Given an array A[i..j] find out maximum j-i such that A[i]a[j] 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.

[algogeeks] array problem

2011-02-09 Thread jalaj jaiswal

sort the input array. only following operations on array is allowed:
1)get(index) -gets the element at that index
2)reverse(int start,int end) - example reverse(1,3) for the array
[1,2,3,4,5] will return [1,4,3,2,5]

better then nlogn

-- 
With Regards,
*Jalaj Jaiswal* (+919019947895)
Software developer, Cisco Systems
Final Year Undergraduate,
IIIT ALLAHABAD

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-08-19 Thread Nikhil Agarwal

On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote:

 @Nikhil: Your algo seems to fail with following input. What do you say?
 Arr1[]= {1,2,3}
 Arr2[]={6}


There is an obvious check. N1==N2 at the beginning.




 On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com
  wrote:

 Sum all the elements of both the arrays..let it be s1 and s2
 Multiply the elements and call as m1 and m2
 if(s1==s2) (m1==m2)
 return 1;else
 return 0;

 O(n)

 On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote:

 Given two arrays of numbers, find if each of the two arrays have the
 same set of integers ? Suggest an algo which can run faster than NlogN
 without extra space?

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 Thanks  Regards
 Nikhil Agarwal
 Senior Undergraduate
 Computer Science  Engineering,
 National Institute Of Technology, Durgapur,India
 http://tech-nikk.blogspot.com
 http://beta.freshersworld.com/communities/nitd


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Thanks  Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science  Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-08-19 Thread Chonku

How about combining sum and multiplication in the first step. As in perform
both sum and multiplication or may be sum of squares.

On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote:

 @Chonku: Your algo seems to fail with following input.
 Arr1[]= {1,6}
 Arr2[]={7}




 On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.comwrote:

 @Nikhil: Your algo seems to fail with following input. What do you say?
 Arr1[]= {1,2,3}
 Arr2[]={6}




 On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal 
 nikhil.bhoja...@gmail.com wrote:

 Sum all the elements of both the arrays..let it be s1 and s2
 Multiply the elements and call as m1 and m2
 if(s1==s2) (m1==m2)
 return 1;else
 return 0;

 O(n)

 On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote:

 Given two arrays of numbers, find if each of the two arrays have the
 same set of integers ? Suggest an algo which can run faster than NlogN
 without extra space?

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 Thanks  Regards
 Nikhil Agarwal
 Senior Undergraduate
 Computer Science  Engineering,
 National Institute Of Technology, Durgapur,India
 http://tech-nikk.blogspot.com
 http://beta.freshersworld.com/communities/nitd


   --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-08-18 Thread Nikhil Agarwal

Sum all the elements of both the arrays..let it be s1 and s2
Multiply the elements and call as m1 and m2
if(s1==s2) (m1==m2)
return 1;else
return 0;

O(n)

On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote:

 Given two arrays of numbers, find if each of the two arrays have the
 same set of integers ? Suggest an algo which can run faster than NlogN
 without extra space?

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
Thanks  Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science  Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-08-18 Thread Chonku

1. Sum all the elements of both arrays. If the sum are same then perform
step 2. If the sum is not different, then arrays are different.
2. Xor elements of first array and then xor the result with elements of
second array. If result is zero, then the arrays are same.


On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote:

 Given two arrays of numbers, find if each of the two arrays have the
 same set of integers ? Suggest an algo which can run faster than NlogN
 without extra space?

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-08-18 Thread Rais Khan

@Nikhil: Your algo seems to fail with following input. What do you say?
Arr1[]= {1,2,3}
Arr2[]={6}



On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:

 Sum all the elements of both the arrays..let it be s1 and s2
 Multiply the elements and call as m1 and m2
 if(s1==s2) (m1==m2)
 return 1;else
 return 0;

 O(n)

 On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote:

 Given two arrays of numbers, find if each of the two arrays have the
 same set of integers ? Suggest an algo which can run faster than NlogN
 without extra space?

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 Thanks  Regards
 Nikhil Agarwal
 Senior Undergraduate
 Computer Science  Engineering,
 National Institute Of Technology, Durgapur,India
 http://tech-nikk.blogspot.com
 http://beta.freshersworld.com/communities/nitd


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-08-18 Thread Rais Khan

@Chonku: Your algo seems to fail with following input.
Arr1[]= {1,6}
Arr2[]={7}



On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote:

 @Nikhil: Your algo seems to fail with following input. What do you say?
 Arr1[]= {1,2,3}
 Arr2[]={6}




 On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com
  wrote:

 Sum all the elements of both the arrays..let it be s1 and s2
 Multiply the elements and call as m1 and m2
 if(s1==s2) (m1==m2)
 return 1;else
 return 0;

 O(n)

 On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote:

 Given two arrays of numbers, find if each of the two arrays have the
 same set of integers ? Suggest an algo which can run faster than NlogN
 without extra space?

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 Thanks  Regards
 Nikhil Agarwal
 Senior Undergraduate
 Computer Science  Engineering,
 National Institute Of Technology, Durgapur,India
 http://tech-nikk.blogspot.com
 http://beta.freshersworld.com/communities/nitd


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-08-18 Thread srinivas reddy

add one more thing to the solution suggested by nikhil i.e;count the number
of elements in array 1 and number of elements in array2 if these two values
are equal then after follow the algo proposed by nikhil agarwal..

On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote:

 @Chonku: Your algo seems to fail with following input.
 Arr1[]= {1,6}
 Arr2[]={7}




 On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.comwrote:

 @Nikhil: Your algo seems to fail with following input. What do you say?
 Arr1[]= {1,2,3}
 Arr2[]={6}




 On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal 
 nikhil.bhoja...@gmail.com wrote:

 Sum all the elements of both the arrays..let it be s1 and s2
 Multiply the elements and call as m1 and m2
 if(s1==s2) (m1==m2)
 return 1;else
 return 0;

 O(n)

 On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote:

 Given two arrays of numbers, find if each of the two arrays have the
 same set of integers ? Suggest an algo which can run faster than NlogN
 without extra space?

 --
 You received this message because you are subscribed to the Google
 Groups Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 Thanks  Regards
 Nikhil Agarwal
 Senior Undergraduate
 Computer Science  Engineering,
 National Institute Of Technology, Durgapur,India
 http://tech-nikk.blogspot.com
 http://beta.freshersworld.com/communities/nitd


  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



  --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Array Problem

2010-08-17 Thread amit

Given two arrays of numbers, find if each of the two arrays have the
same set of integers ? Suggest an algo which can run faster than NlogN
without extra space?

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Array Problem

2010-08-09 Thread amit

Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a \in A and b
\in B}. Obviously there are n2 elements in S. The value of such a pair
is defined as Val(a,b) = a +
b. Now we want to get the n pairs from S with largest values.

How to do this in O(nlogn) time.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-08-09 Thread ankur bhardwaj

we can merge the 2 arrays in sorted manner. Now from the 2nd last number,we
can have the first pair (last,second last).From the 3rd last,we can have 2
pairs (last,3rd last) and (2nd last,3rd last). similarly we will keep on
taking till we get n pairs.

time complexity: O(2n+n)- O(n)
space complexity: O(2n)-O(n)

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-08-09 Thread Chonku

Since the arrays are sorted, you should be able to do this in O(n) time.

a[1..n], b[1..n]
output a[n], b[n]
int count=1;
while (i  0 and j  0 and count  n)
Begin
   if (a[i-1] * b[j] = a[i] * b[j-1])
  Begin
Output a[i-1]  b[j]
 i=i-1;
  End
else
  Begin
Output a[i]  b[j-1]
 j = j-1;
  End
 ++count;
End

On Mon, Aug 9, 2010 at 6:36 PM, amit amitjaspal...@gmail.com wrote:

 Given two sorted positive integer arrays A(n) and B(n), we define a
 set S = {(a,b) | a \in A and b
 \in B}. Obviously there are n2 elements in S. The value of such a pair
 is defined as Val(a,b) = a +
 b. Now we want to get the n pairs from S with largest values.

 How to do this in O(nlogn) time.

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-08-09 Thread ankur bhardwaj

ignore my last post :(

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-07-16 Thread jalaj jaiswal

@amit did u got any solution ??

On Sun, Jul 11, 2010 at 7:29 PM, amit amitjaspal...@gmail.com wrote:

 You have an array like ar[]= {1,3,2,4,5,4,2}. You need to create
 another array ar_low[] such that ar_low[i] = number of elements lower
 than or equal to ar[i] in ar[i+1:n-1].
 So the output of above should be {0,2,1,2,2,1,0}

 Time complexity : O(n)
 use of extra space allowed.

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-06-24 Thread Anurag Sharma

Sorry, this point is already pointed out by Sharad.

Anurag Sharma


On Thu, Jun 24, 2010 at 4:42 PM, Anurag Sharma anuragvic...@gmail.comwrote:

 @jalaj
 Your approach will not work, what I perceived from your solution, as in
 question the maximum difference S is defined as:-

 S = a[i] - a[j] where* ij
 *
 Perhaps you forgot that the 'order' of the max and min also matters :)


 Anurag Sharma



 On Mon, Jun 21, 2010 at 10:34 PM, jalaj jaiswal jalaj.jaiswa...@gmail.com
  wrote:

 traverse the array ...take two variables min and max ... and update them
 ...while traversing.
 finally min will contain the most negative value,,, and max will contain
 the most positive vale... do max-min.. that will be S

 On Mon, Jun 21, 2010 at 5:38 PM, amit amitjaspal...@gmail.com wrote:

 There is an integer array consisting positive and negative integers.
 Find maximum positive difference S defined as:

 S = a[i] - a[j] where ij
 and
 S  0

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 With Regards,
 Jalaj Jaiswal
 +919026283397
 B.TECH IT
 IIIT ALLAHABAD

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-06-24 Thread Anurag Sharma

@jalaj
Your approach will not work, what I perceived from your solution, as in
question the maximum difference S is defined as:-
S = a[i] - a[j] where* ij
*Perhaps you forgot that the 'order' of the max and min also matters :)


Anurag Sharma


On Mon, Jun 21, 2010 at 10:34 PM, jalaj jaiswal
jalaj.jaiswa...@gmail.comwrote:

 traverse the array ...take two variables min and max ... and update them
 ...while traversing.
 finally min will contain the most negative value,,, and max will contain
 the most positive vale... do max-min.. that will be S

 On Mon, Jun 21, 2010 at 5:38 PM, amit amitjaspal...@gmail.com wrote:

 There is an integer array consisting positive and negative integers.
 Find maximum positive difference S defined as:

 S = a[i] - a[j] where ij
 and
 S  0

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




 --
 With Regards,
 Jalaj Jaiswal
 +919026283397
 B.TECH IT
 IIIT ALLAHABAD

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-06-21 Thread jalaj jaiswal

traverse the array ...take two variables min and max ... and update them
...while traversing.
finally min will contain the most negative value,,, and max will contain the
most positive vale... do max-min.. that will be S

On Mon, Jun 21, 2010 at 5:38 PM, amit amitjaspal...@gmail.com wrote:

 There is an integer array consisting positive and negative integers.
 Find maximum positive difference S defined as:

 S = a[i] - a[j] where ij
 and
 S  0

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.




-- 
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-06-21 Thread Amir hossein Shahriari

using divide and conquer you can do it in O(nlogn) your recursive function
must return three values the max and min value in this range and the maximum
difference

but this can also be solved in O(n)
start from the end of array if you loop backward you can determine the
max(a[i]) for i=j
and then subtract it from a[ j ]

S=0;
Max = a[n-1];
for ( j=n-2 ; j=0 ; j-- ){
   if (Max - a[j]  S)
   S=Max - a[j];
   if ( a[j]  Max )
  Max = a[j];
}

On Mon, Jun 21, 2010 at 4:38 PM, amit amitjaspal...@gmail.com wrote:

 There is an integer array consisting positive and negative integers.
 Find maximum positive difference S defined as:

 S = a[i] - a[j] where ij
 and
 S  0

 --
 You received this message because you are subscribed to the Google Groups
 Algorithm Geeks group.
 To post to this group, send email to algoge...@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
 .
 For more options, visit this group at
 http://groups.google.com/group/algogeeks?hl=en.



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Array Problem

2010-06-21 Thread sharad kumar

@jalaj one more constraint is there ij

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Array Problem

2010-06-11 Thread amit

given an array A of n elements.
for indexes j , i such that ji
maximize( j - i )
such that A[j] - A [ i ] 0 .

Any Algorithm less than O(n^2) would do.

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

1 2 >

100 matches

Mail list logo