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
@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/ |
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
@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
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
@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
@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
@ 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
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
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
@ 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
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
@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
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
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
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
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)
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
@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
@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
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---
@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
@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
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
@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
@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
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
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
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
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,
@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
@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
@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
@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)
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
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
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
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
@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
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).
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
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 +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
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
@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
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
@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
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
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
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
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:
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,*
*
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
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
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
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
{
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
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
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
@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
@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,
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.
@ 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
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
@ 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
@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)
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
@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
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
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
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
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
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
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
@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:
@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
@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
@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]
@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
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
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
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
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
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
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
@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
@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,
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:
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
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.
--
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
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
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,
@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
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]
@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
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:
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
@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.
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
100 matches
Mail list logo
