Without the memory constraint, you just keep a minheap heap with the k
largest elements. For every new number, if the heap is not full, add the
number. Otherwise compare it to the smallest item in the heap, and if it is
larger replace that item with the new one and downheap.
The memory
I was going through this problem on stackoverflow, and I found this classic
article on this very topic
http://www.americanscientist.org/issues/pub/2002/3/the-easiest-hard-problem
Definitely, worth a read.
--
*
*
*thanks regards,*
*Avinesh Kumar
National Institute of Technology, Calicut.*
@arun..
Couple of questions need to be clarified :
1) Are all the numbers given in the unsorted array +ive integers.. ?
2) By 2 equal arrays do you mean that both the arrays should be of size N/2
(where N is even) .. ?
If the above assumptions are true then we can use the following recurrence
I think that the problem specifies that the two arrays be of equal
size.
Don
On Nov 16, 9:12 am, bharat b bagana.bharatku...@gmail.com wrote:
@ 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,
use the concept of segment tree+lazy propagation
On Saturday, August 25, 2012 2:39:54 AM UTC+5:30, wentworth miller wrote:
Hi,
You are given N numbers. You have to perform two kinds of operations:
U x y - x-th number becomes equal to y.
Q x y - calculate the sum of distinct numbers from x-th
interesting discussion going on the question, check this link--
http://stackoverflow.com/questions/9442958/find-the-element-occurring-b-times-in-an-an-array-of-size-nkb
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
@Amol: Since you don't restrict using extra space, use hashing or do a
radix sort, either being O(n*k+b).
Dave
On Feb 15, 12:07 pm, Amol Sharma amolsharm...@gmail.com wrote:
Given an array of size n*k+b.In this array n elements are repeated k times
and 1 elements are repeated b times.find the
@amol : actually complexity you have asked for is like saying finding
solution in linear time. because we need to traverse whole array once
atleast to find the solution and total size of array is n*k+b=N. so
required complexity is O(N).
so we can use hashmap to solve this problem.
On Fri, Feb
any other solution other than hashingbcoz say numbers are very very
largeyai want a linear solution
i first choice was also hashing.but the interviewer wanted something
other than that...
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
convert the numbers into base k... and do bitwise addition of numbers, where
bit(a)+bit(b)=bit(a+b)mod(k)
of you convert all the numbers into base k and add them bitwise in a
variable say x, then the numbers occuring nk times vanish, and the final
result stored in x is a+a++a(b times) where a
can u explain with a explain what r u trying to say ?
--
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
@Siddhartha : doing bitwise addtiton may result into overflow if values are
large.
correct me if i am wrong.
On Fri, Feb 17, 2012 at 10:04 AM, Siddhartha Banerjee
thefourrup...@gmail.com wrote:
convert the numbers into base k... and do bitwise addition of numbers,
where
@amrit,@Pranav and others : Thanks a lot..
On Feb 15, 11:35 am, amrit harry dabbcomput...@gmail.com wrote:
@tushar
lower bound for sorting an array is
nlogn.http://www.bowdoin.edu/~ltoma/teaching/cs231/fall11/Lectures/6-moreso...
On Wed, Feb 15, 2012 at 11:16 AM, TUSHAR
I think for count it should be count=(int)(k/N), instead of (int)k/5...
On Wed, Feb 15, 2012 at 6:00 PM, TUSHAR tusharkanta.r...@gmail.com wrote:
@amrit,@Pranav and others : Thanks a lot..
On Feb 15, 11:35 am, amrit harry dabbcomput...@gmail.com wrote:
@tushar
lower bound for
@Pranav: This could fail if N sqrt(maxint) and a sufficient number
of A[i] have the same value so that A[A[i]] N*N, which overflows.
Dave
On Feb 15, 1:08 am, Pranav meetpranav...@gmail.com wrote:
Array 'A' contains N elements st A[i] =k N
Now,
Iterate over the array.
Let k=A[i]
If A[i]
heres a O(n) solution.. correct me if am wrong..
1. In order to get the count in O(1) we need to place the count of each
number in their respective index.So before storing the count we need to
swap the nos. in such a way that all k=n are at their respective
index.This can be done in O(n)
That means,,,we have to sort the array first in O(n).
Is there any way to sort the array inplace in 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 algogeeks@googlegroups.com.
To unsubscribe from
Array 'A' contains N elements st A[i] =k N
Now,
Iterate over the array.
Let k=A[i]
If A[i] N
then k=A[i] mod N
go to A[k] and write A[k] = A[k] + N
So, lets take a sample array of size 5: 1,2,1,0,4
i=0: k=A[i]=1; A[i] 5; A[1] = A[1] + 5 = A[1] = 7 = A = 1,7,1,0,4
i=1: k=A[i]=7; A[i] 5;
@amit : it is valid for comparison based model..
On Wed, Feb 15, 2012 at 12:05 PM, amrit harry dabbcomput...@gmail.comwrote:
@tushar
lower bound for sorting an array is nlogn.
http://www.bowdoin.edu/~ltoma/teaching/cs231/fall11/Lectures/6-moresorting/sortLB.pdf
On Wed, Feb 15, 2012 at
You are right the algorithm is based on the max subarray problem. The
difference is the logic to get the crossingSubArray() method. The way it works
is like this:
The outer while loop, makes sure that left position or right position at least
one of this should be between lo and hi values
Here is the code for O (nlgn) time complexity using recursion written in Java:
public class SubArray {
static int A [] = {2, 1, 3, 4, 5};
static int k;
private class Result {
int lo;
int hi;
int total;
I think we can also solve this using divide and conquer:
The algorithm is based on the concept of diving the current array into two
parts and then considering if the solution exists, in the first part from lo to
mid and last part from mid+1 to high and the case in which the subarray crosses
@ mohit my first post on here. this solution got ac in spoj
main()
{
unsigned int n,m,sum,max,i,j;
sum=0;max=1;
n=in.ReadNextUInt();
m=in.ReadNextUInt();
unsigned int *a = new unsigned int[n];
unsigned
cant think of anything better than O(N^2). Are you sure there exists such
algo?
On Tue, Nov 29, 2011 at 2:55 AM, Mohit kumar lal kumarmohit...@gmail.comwrote:
Given a array of positive integers ,You have to find the largest sum
possible from consecutive sub-array but sum should be less than or
here it is similar type of question i found on spoj ,it asks only for the
sum
http://www.spoj.pl/problems/HOTELS/
but it is giving TLE in O(n^2)..
On Tue, Nov 29, 2011 at 5:51 PM, Nitin Garg nitin.garg.i...@gmail.comwrote:
cant think of anything better than O(N^2). Are you sure there exists
Given a array of positive integers ,You have to find the largest sum
possible from consecutive sub-array but sum should be less than or equal to
K and also find that sub-array. Ex- array={2,1,3,4,5} k=12,
ans-12, sub-array={3,4,5}
Firstly i tried with brute-force and then i also tried to solve
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1 correspondence.
output[i] is equal to the input[j] (ji) which is smaller than input[i] and
jth is nearest to ith ( i.e. first element which is smaller).
If no such
I can't think of a better than O(n^2) solution for this..
Any one got anything better?
On Tue, Nov 22, 2011 at 8:23 PM, Ankuj Gupta ankuj2...@gmail.com wrote:
Input: A unsorted array of size n.
Output: An array of size n.
Relationship:
elements of input array and output array have 1:1
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the right.
put the first element in stack.
take next element suppose num if this number is less than elements
stored in stack, pop those elements , for these pooped elements num will
be the
On Tue, Nov 22, 2011 at 11:50 PM, tech coder techcoderonw...@gmail.comwrote:
here is an O(n) approach using a stack.
problem can be stated as find the 1st smaller element on the right.
put the first element in stack.
take next element suppose num if this number is less than elements
What do you mean by if this number is less than elements stored in
stack
There have be N comparisons in the worst case. And that way, you have to do
it for every element.
So it will be governed by O(n^2)
On Wed, Nov 23, 2011 at 12:50 AM, Aamir Khan ak4u2...@gmail.com wrote:
On Tue, Nov
B[n]=0;
for i=n to 1
{
if(A[i-1]=A[i])
B[i-1]=B[i];
else
B[i-1]=B[i]+1;
}
O(n) solution.
Correct me if I am wrong.
On Tue, Oct 4, 2011 at 2:07 PM, anshu mishra anshumishra6...@gmail.comwrote:
int count(int x, int tree[], int s, int e, int n)
{
tree[n]++;
if (s==e) return 0;
int cnt = 0;
for second part
maintain an array of c[n-1] elements initialized to 1.
for given count in B[i] from i=o,start counting 1's in c.
at that (count)==b[i]+1,assume at c[j] set c[j]=0 and a[i]=j;
its O(n2) :-(
--
You received this message because you are subscribed to the Google Groups
int count(int x, int tree[], int s, int e, int n)
{
tree[n]++;
if (s==e) return 0;
int cnt = 0;
int mid = (s+e)/2;
if (mid x) return tree[2*n+1]+count(x, tree, mid+1, e, 2*n+2);
else return count(x, tree, s, mid, 2*n+1);
}
main()
{
for(i=n-1;i=0; i--)
{
sol[i] = insert(ar[i], tree, 0,
Hi Vikram!
Obviously The naivest solution is O(n2). Could you give a hint for
this problem?
On Oct 3, 4:39 pm, Vikram Singh singhvikram...@gmail.com wrote:
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],
int B[sizeof(A)];
int k=0 , j ;
for(j=i;jn;j++)
{
if (A[j] A[i])
B[k++]=A[j];
}
On Tue, Oct 4, 2011 at 5:30 AM, Abraham freedomsou...@gmail.com wrote:
Hi Vikram!
Obviously The naivest solution is O(n2). Could you give a hint for
this problem?
On Oct 3, 4:39 pm, Vikram Singh
Ummm..
Algorithm:
Start from the right of the array,
make the last element of B to 0,
initialize a variables counter to 0 and max to A[end];
LOOP:
and now move from right to left,
if the next element of the left element max
increment counter and assign it to that B[ n - element ] index.
max =
7 1 4 5 3 6 2
try for
is it necessary to have elements within 1-n range?
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Tue, Oct 4, 2011 at 7:36 AM, Anup Ghatage ghat...@gmail.com wrote:
Ummm..
Algorithm:
Start from the right of the array,
@ashish: yes it is given that elements are in 1-n range...
@anup: ur sol doesnt work for above case... try to make it general..
@abraham: i hv O(n2) sol, not required, that to of only 1st part...
guys try thinking 2nd part also??
On Tue, Oct 4, 2011 at 8:14 AM, Ashish Goel
use segment tree or binary index tree to solve O(nlogn)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
@anshu: pls elaborate... give an example...
On Tue, Oct 4, 2011 at 9:51 AM, anshu mishra anshumishra6...@gmail.comwrote:
use segment tree or binary index tree to solve O(nlogn)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to
Can we assume the output array is a new array and we can distort the
originial array???
On Fri, Sep 30, 2011 at 9:14 AM, praveen raj praveen0...@gmail.com wrote:
Take two array... one will take care of left products... and othr will take
care of right product.. at any index
@nitin ..
Output array is not a new array ... you can do anything to input array ..
~raju
On Fri, Sep 30, 2011 at 1:24 PM, Nitin Garg nitin.garg.i...@gmail.comwrote:
Can we assume the output array is a new array and we can distort the
originial array???
On Fri, Sep 30, 2011 at 9:14 AM,
@raju - so it means the input array should be distorted to give the output
array.
Are you sure about it? i doubt if its possible.
On Fri, Sep 30, 2011 at 11:24 PM, raju nikutel...@gmail.com wrote:
@nitin ..
Output array is not a new array ... you can do anything to input array ..
~raju
On
char A[] = { 1,2,3,4,5 };
int algo(int b, int i) {
if(i == sizeof(A)) { return 1; }
int c = A[i];
int f = algo(b*c, i+1);
A[i] = b*f;
return f*c;
}
On Thu, Sep 29, 2011 at 8:26 AM, raju nikutel...@gmail.com wrote:
Given an integer array. { 1,2,3,4,5 }
Compute array
Is the array Sorted ?
On Thu, Sep 29, 2011 at 4:56 PM, raju nikutel...@gmail.com wrote:
Given an integer array. { 1,2,3,4,5 }
Compute array containing elements
120,60,40,30,24 (2*3*4*5,1*3*4*5, 1*2*4*5, 1*2*3*5, 1*2*3*4)
We shouldn't use division operator( / )
Time complexity O(n) ..
maintain two arrays one left array having value left[i] =
a[0]*a[1]*a[2].a[i-1] and one right array having value
right[i]=a[i+1]*[i+2]a[n] and then to get
ans[i]...ans[i]=left[i]*right[i]
On Thu, Sep 29, 2011 at 8:16 PM, Ankur Garg ankurga...@gmail.com wrote:
Is the array Sorted ?
whats the running time? isn't it O(n2) ?
On Thu, Sep 29, 2011 at 8:54 PM, UTKARSH SRIVASTAV
usrivastav...@gmail.comwrote:
maintain two arrays one left array having value left[i] =
a[0]*a[1]*a[2].a[i-1] and one right array having value
right[i]=a[i+1]*[i+2]a[n] and then to get
//use dynamic programming approach
//it is O(n) time and O(1) space
#includestdio.h
#define N 5
void main()
{
int a[N]={1,2,3,4,5},i;
int prod1[N];
int p=1;
for(i=0;iN;++i)
{
prod1[i]=p;
p*=a[i];
}
int prod2[N];
p=1;
for(i=N-1;i=0;--i)
{
prod2[i]=p;
p*=a[i];
}
int products[N];
check this http://www.geeksforgeeks.org/archives/7527
time O(n)
space O(n)
--
Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
http://gplus.to/amolsharma99
are the algorithm instance always a sequence incremented by one?
On Thu, Sep 29, 2011 at 8:26 AM, raju nikutel...@gmail.com wrote:
Given an integer array. { 1,2,3,4,5 }
Compute array containing elements
120,60,40,30,24 (2*3*4*5,1*3*4*5, 1*2*4*5, 1*2*3*5, 1*2*3*4)
We shouldn't use division
Given array A.
Compute array B such that
B[0] = 1;
for(i = 1; i n; i++)
B[i] = B[i-1]*A[i-1]
now,
mul = 1;
for (i = n-2; i =0; i--){
mul = mul*A[i];
B[i] = B[i]*mul;
}
On Fri, Sep 30, 2011 at 2:18 AM, Hatta tmd...@gmail.com wrote:
are the algorithm instance always a sequence
sorry, one mistake...
mul = mul*A[i];
it should be
mul = mul*A[i+1]
On Fri, Sep 30, 2011 at 2:57 AM, Piyush Grover piyush4u.iit...@gmail.comwrote:
Given array A.
Compute array B such that
B[0] = 1;
for(i = 1; i n; i++)
B[i] = B[i-1]*A[i-1]
now,
mul = 1;
for (i = n-2; i =0;
Take two array... one will take care of left products... and othr will take
care of right product.. at any index left[i]=A[i-1]*left[i-1] starting
from left and right[i]= A[i+1]*right[i+1] starting frm right……
--
You received this message because you are subscribed to the Google Groups
it can be done in O(N) by using XOR ing the elements
1: Xor all the elemnts since those elemnts that even freq will nullify each
other we get number taht will tell in which the two required number differ.
2: divide the array in two sets on the basis of bit in which numbers
differ
3:1 element
@Umesh I really appreciate your solution and thinking to understand the
complexity of the program.
Actually I don't have that much idea about the *how to calculate complexity
of any program*. So could you please show some light on the evaluation
procedure of complexity.
Rahul Verma
--
You
We have an array which contains integer numbers (not any fixed range). Only
two numbers are repeated odd number of times and remaining even number of
times. Find the 2 numbers.
like
arr[]={1,2,5,1,5,1,1,3,2,2}
1 - 4 times(even)
2- 3 times(odd)
3- 1 times(odd)
5- 2 times(even)
output 2 3
m not
int main()
{
int arr[]={1,2,5,1,5,1,1,3,2,2,};
int elements = sizeof(arr)/sizeof(arr[0]);
int count=1;
int num;
sort(arr,arr+elements);
num=arr[0];
for(int i=1;ielements;i++)
{
if(arr[i]==num)
count++;
else
{
It would work i guess
On Aug 21, 1:49 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)
@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
@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
This problem is close than this:
http://uva.onlinejudge.org/external/103/10327.html
I found this:
http://en.wikipedia.org/wiki/Pancake_sorting
Wladimir Araujo Tavares
*Federal University of Ceará
*
On Fri, Feb 11, 2011 at 10:57 AM, juver++ avpostni...@gmail.com wrote:
@jalaj please
@jalaj please ignore my prevoius post, misread the 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
@Jalaj: What is the work for each of the operations? I presume that
get is O(1), but don't know if reverse is O(1) or O(end-start).
Dave
On Feb 10, 12:07 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote:
sort the input array. only following operations on array is allowed:
1)get(index) -gets
Cartesian tree will do.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options,
@ dave assume reverse also O(1)
@juver will you elaborate a bit dude
On Thu, Feb 10, 2011 at 8:21 PM, juver++ avpostni...@gmail.com wrote:
Cartesian tree will do.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group,
can you please explain more in detail the logic for XORing the index.
On 22.08.2010 07:53, UMarius wrote:
@Nikhil : I considered the array to be a linked list. xoring the
indexes helps when you don't know how many elements you have.
Marius.
On Aug 22, 5:04 am, Nikhil
a={1,2,2,3,4}
b={1,2,3,3,4}
in this case???
elements are not equal but they certainly consist equal set of
integers(1,2,3,4) which is what question says.
On Sun, Aug 22, 2010 at 7:53 AM, UMarius mar...@aseara.ro wrote:
@Nikhil : I considered the array to be a linked list. xoring the
indexes
Its easier to look at a property of numbers. It will be interesting to
evaluate/prove if two different arrays have same value for sum of elements
and sum of squares of the elements.
On Fri, Aug 20, 2010 at 9:38 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
Check this new algo: plz provide
@Nikhil Agarwal: You cannot take extra memory and neither the range of
numbers is specified.
Counting will not be a viable option.
On Fri, Aug 20, 2010 at 9:38 AM, Nikhil Agarwal
nikhil.bhoja...@gmail.comwrote:
Check this new algo: plz provide counter eg.(if any)
step 1 : count the no. of
What about this?
1. xor all elements of each array and their corresponding indexes
sum all the elements of each array mul all elements of each array
2. if all results are the same then the arrays are identical
Nice to meet you all, I just joined and this is my first post :) ...
Given two
@UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
original problem, you see that the question is not whether the arrays
are identical (which is easily determined by simply comparing them
element-by-element in O(n)), but whether they contain the same values,
possibly in a different
@marius Why are you xorring the indexes along with nos.?any special reason?
On Sun, Aug 22, 2010 at 7:19 AM, UMarius mar...@aseara.ro wrote:
@Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1}
the output is correct.
Maybe I didn't explain the steps correctly. This is the
@Nikhil : I considered the array to be a linked list. xoring the
indexes helps when you don't know how many elements you have.
Marius.
On Aug 22, 5:04 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote:
@marius Why are you xorring the indexes along with nos.?any special reason?
On
@Nikhil: A = {0,2,2}, B = {0,0,4}.
Rather than challenging everyone to keep coming up with
counterexamples, please provide a rationale as to why an algorithm
such as this should work. It looks as if you have two equations in 2N
unknowns and are trying to assert that the only solution is A_1 =
Nikhil's algo is correct if the following is always true:
Given: x + y = S, x * y = M
and x' + y' = S', x' * y' = M'
If: S' = S and M' = M, then x = x' and y = y'
i.e for given sum and product, the elements are unique.
On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal
@Nikhil Jindal: What you say is true for 2 numbers, but not for more
than 2.
1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36.
Dave
On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote:
Nikhil's algo is correct if the following is always true:
Given: x + y = S, x * y = M
1. Add sum of squares of all numbers in respective groups, if equal
goto step 2.
2. XOR all elements of both groups, (if==0) elements are same.
On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote:
@Nikhil Jindal: What you say is true for 2 numbers, but not for more
than 2.
1 + 6 + 6 = 2 + 2
@Saikat: Rather than challenging everyone to keep coming up with
counterexamples, please provide a rationale as to why an algorithm
such as this should work. It looks as if you have two equations in 2N
unknowns and are trying to assert that the only solution is A_1 =
B_1,
A_2 = B_2, etc. (where I
@saikat ur algo fails with the test case a1=-2,-2 and a2=2,2
On Thu, Aug 19, 2010 at 10:22 PM, Saikat Debnath saikat@gmail.comwrote:
1. Add sum of squares of all numbers in respective groups, if equal
goto step 2.
2. XOR all elements of both groups, (if==0) elements are same.
On Aug 19,
@Chonku, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2).
Dave
On Aug 18, 7:52 am, Chonku cho...@gmail.com wrote:
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
@Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
(0,2,-2).
Dave
On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote:
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
@Chonku, Make that: Your algorithm seems to fail on A = {0,1,-2), B =
(0,2,-3). I was thinking onwa-complement arithmetic instead of twos-
complement.
Dave
On Aug 18, 11:57 pm, Dave dave_and_da...@juno.com wrote:
@Chonku, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2).
Dave
On
@Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B
=
(0,2,-3). I was thinking ones-complement arithmetic instead of twos-
complement.
Dave
On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote:
@Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
(0,2,-2).
Dave
It would be great if they have the likes and dislike like in yahoo
answers so that correct or rather best solutions can be looked at
immediately then subsequently the other solutions!!
second, if u cud give the link to the problem, even we can try the
problem and submit it and gain some confidence
i meant make an array of indexes.. index[]={0,1...,n-1}
now sort the original array and move the elements of index array
accordingly..
now follow modelling expert's algo nd while taking largest-smallest check if
the index of largest in index array index of smallest in index array.
On 13 June
@BALARUKESH
i think the problem is to maximize the diffrence j-i according to condition
and in your solution j can be less than i.
This problem can be solved by sorting the array first, then taking
diffrence.
this solution is done in O(nlogn).
--
You received this message because you are
Problme is not clear.
Quesrtions:
1. Is the array all of positive numbers
if yes then sort the array in ascending order. Now for every j, ji
and i,j =n, A[j]A[i] and so A[j]-A[i] 0. Now if we want max(j-i)
such that A[j]-A[i]0, it has to be j=n, the last element of A and
i=1, the first element of
Let's say array A , 1 till n
s_index = 1; e_index = n ;
start = A[s_index] ;
end = A[e_index];
result = 0; //! j - i
if ( *end *start ){
result = index(end) - index(start) ( only of its greater than
previous value of result )
break ;
}else{
end-- ; //! till
i think we need to maintain an array of index as well such that while
subtracting smallest element from largest element of sorted array we need to
check if index of largest is greater than index of smallest. if no..then
this is not the solution..
On 12 June 2010 14:20, Modeling Expert
yes we need to maintain an array that shows the real indexes before sorting
and then loop on the elements and find the minimum index that appeared
before a number in the sorted array and subtract it from it's index
and find the maximum difference
On 6/12/10, divya jain sweetdivya@gmail.com
This problem seems to be finding the maxdiff in an array.
int maxdiff ( int A[], int n ) {
// write your code here
int max_diff = A[1] - A[0];
int min_element = A[0];
int i;
for(i = 1; i n; i++)
{
if(A[i] - min_element max_diff)
max_diff = A[i] - min_element;
if(A[i]
@sourav : if I understood problem correctly , you can't change the
list ( hence you can't sort ).
and list can containt + . - ive ints .
e.g. say list is
7 9 1 -4 8 0 0 0 3 1 0
Here answer is index(0) - index(-4) = 11
@divya : didn't get what you said , but guess you also thought of
sorting
@Satya: I don't think what you have coded will work.. though i have not read
the whole code.
Don't you think a simple divide and conquer scheme would work...(almost like
the mergesort)
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer
94 matches
Mail list logo
