Re: [algogeeks] fastest sequential access

[atul anand]

@shady : as subject says "fastest sequential access " , then if i am not
getting it wrong.we only care of sequential access a value not modifying
the linked list.
so i guess double linked list would be helpful
1) bcozz it can move in both the direction , so if linked list is sorted
then it would be a great help
2) if you want to insert element at the end of linked list then if will be
better than vector
so i guess it required 1-2 more parameter to decide ,which one to use.

On Wed, Nov 21, 2012 at 8:21 PM, shady  wrote:

> which data structure among the follow has fastest sequential access ?
> i)   vector
> ii)  Singly linked list
> iii) Doubly linked list
>
> it won't be doubly linked list as it involves more pointer manipulations
> than singly linked list...
>
> --
>
>
>

-- 

Re: [algogeeks] Array problem

[Ansum Baid]

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

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

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

-- 

Re: [algogeeks] Array problem

[Dave]

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

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

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

-- 

Re: [algogeeks] fastest sequential access

[vishal chaudhary]

singly linked list

On Wed, Nov 21, 2012 at 8:21 PM, shady  wrote:

> which data structure among the follow has fastest sequential access ?
> i)   vector
> ii)  Singly linked list
> iii) Doubly linked list
>
> it won't be doubly linked list as it involves more pointer manipulations
> than singly linked list...
>
> --
>
>
>

-- 

[algogeeks] Game

[Wladimir Tavares]

Arnaldo and Bernaldo are playing within the classroom as follows:
they write initially under a positive integer n. then
alternately, beginning with Arnold, erase the number that is on the table
and
write a new number that can be:
• what has just been erased least the largest power of 2 (with exponent
non-negative integer) less than or equal to the number off;
• what has just been cleared divided by 2, if the number  deleted is
even.
Whoever wins the game gets first zero.
a) Determine which of the players has a winning strategy for n = 40
and describe it.
b) Determine which of the players has a winning strategy for n =
2012 and describe it.

For instance,

if n=3   then 3-2 = 1
if n = 4 then 4-4 = 0 or 4/2 = 2


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

-- 

Re: [algogeeks] Re: Largest contigious subarray with average greather than k

[Sachin Chitale]

Implementation

public class Kadanes {
static int maxAvgSum(int a[], float k) {
int max_so_far = 0, max_ending_here = 0, avg = 0, s = -1, e = -1, ts, te,
tsum;
boolean flag = false;

for (int i = 0; i < a.length; i++) {

if (max_ending_here == 0)
s = e = i;

max_ending_here = max_ending_here + a[i];

if (max_ending_here < 0) {
max_ending_here = 0;
s = e = -1;
}
if (max_so_far < max_ending_here) {
max_so_far = max_ending_here;

e = i;
}

}

if (avgGreater(max_so_far, s, e, k)){
System.out.println("Result subarray start index:" + s
+ " End index:" + e);
return max_so_far;
}
/*This will generate two sequence use optimal time complexity of this algo
is O(n)
 *
 *
 */
 if (s >= 0 && !avgGreater(max_so_far, s, e, k)) {
max_ending_here = max_so_far;
ts = s;
te = e;

while (ts < te) {

max_ending_here -= a[ts];
if (avgGreater(max_ending_here, ts+1, te, k)) {
ts++;
System.out.println("Result subarray start index:" + ts
+ " End index:" + te);
break;
}
ts++;
}
ts = s;
te = e;
max_ending_here = max_so_far;
while (ts < te) {

max_ending_here -= a[te];
if (avgGreater(max_ending_here, ts, te-1, k)) {
te--;
System.out.println("Result subarray start index:" + ts
+ " End index:" + te);
break;
}
te--;
}

}

return max_so_far;
}

static boolean avgGreater(int sum, int s, int e, float k) {
float t= (float) (sum / (e - s + 1));
 return t>=k? true : false;
}

public static void main(String[] args) {

int[] a = { 100, 10, -1, -1, 4, -1, 7, 2, 8 };
System.out.println(maxAvgSum(a, 5));
}
}


On Wed, Nov 21, 2012 at 10:07 PM, Sachin Chitale
wrote:

> Hello,
>
> Algorithm-->
> 1. Find out start and end index of contiguous subarray which has max sum
> O(n)
> 2.Once u have start and end index calculate avg if it satisfies the
> condition then done O(n)
>   2.1 other wise run a loop through start to end index and remove trailing
> elements by increasing start
>  2.2 simultaneously check avg..this will lead to proper subarray.
> 3. In similar fashion start reducing end valuse keeping start
> constant.do it sub steps of 2...
>
> compare result of 2 and 3 and choose d best one...
> give me some time to write code
>
>
> On Wed, Nov 21, 2012 at 12:29 AM, Koup  wrote:
>
>> To be correct I need the longest subarray that has an average greater
>> than k but my main problem here is to find the longest one. Thank you !
>>
>> --
>>
>>
>>
>
>
>
> --
> Regards,
> Sachin Chitale
> Application Engineer SCJP, SCWCD
> Contact# : +91 8086284349, 9892159511
> Oracle Corporation
>



-- 
Regards,
Sachin Chitale
Application Engineer SCJP, SCWCD
Contact# : +91 8086284349, 9892159511
Oracle Corporation

-- 

[algogeeks] Array problem

[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] Re: Largest contigious subarray with average greather than k

[Sachin Chitale]

Hello,

Algorithm-->
1. Find out start and end index of contiguous subarray which has max sum
O(n)
2.Once u have start and end index calculate avg if it satisfies the
condition then done O(n)
  2.1 other wise run a loop through start to end index and remove trailing
elements by increasing start
 2.2 simultaneously check avg..this will lead to proper subarray.
3. In similar fashion start reducing end valuse keeping start
constant.do it sub steps of 2...

compare result of 2 and 3 and choose d best one...
give me some time to write code


On Wed, Nov 21, 2012 at 12:29 AM, Koup  wrote:

> To be correct I need the longest subarray that has an average greater than
> k but my main problem here is to find the longest one. Thank you !
>
> --
>
>
>



-- 
Regards,
Sachin Chitale
Application Engineer SCJP, SCWCD
Contact# : +91 8086284349, 9892159511
Oracle Corporation

-- 

[algogeeks] fastest sequential access

[shady]

which data structure among the follow has fastest sequential access ?
i)   vector
ii)  Singly linked list
iii) Doubly linked list

it won't be doubly linked list as it involves more pointer manipulations
than singly linked list...

--