[algogeeks] Array problem

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 subscri

Re: [algogeeks] Array Problem

@wladimir yes the problem seems to be that!! On Tue, Dec 11, 2012 at 10:13 AM, Wladimir Tavares wrote: > subset sum? > Wladimir Araujo Tavares > *Federal University of Ceará > Homepage | > Maratona

Re: [algogeeks] Array Problem

subset sum? Wladimir Araujo Tavares *Federal University of Ceará Homepage | Maratona| * On Fri, Nov 16, 2012 at 2:46 AM, Pralay Biswas wrote: > Search for balance partitioning und

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

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

[algogeeks] Array problem

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 Polycarp

Re: [algogeeks] Array Problem

@ vishal :let array be {5,2,1,1} ==> as per u'r algo =>{1,2},{1,5} are sets difference is 3 .. but the sol is {5}{1,1,2} ==> diff = 1; On Fri, Nov 16, 2012 at 10:12 AM, vishal chaudhary wrote: > Hi > Sorry for that as i misinterpreted the question. > for the difference to be minimum, i think(not

Re: [algogeeks] Array Problem

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

Re: [algogeeks] Array Problem

@ vishal : how can u divide an array into 2 groups whose difference is maximum in O(1). why max? solution : http://www.youtube.com/watch?v=GdnpQY2j064 On Fri, Nov 16, 2012 at 9:22 AM, vishal chaudhary wrote: > Hi > you can first sort the array which can be done in O(nlogn) complexity if > the

Re: [algogeeks] Array Problem

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

[algogeeks] Array Problem

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 gr

Re: [algogeeks] array problem

@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! > BT

Re: [algogeeks] array 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

Re: [algogeeks] array problem

post the logic not the code! BTW this problem can be done using segment trees. http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor On Thu, Sep 6, 2012 at 4:51 PM, bharat b wrote: > Its better to write an O(n) solution for this problem as the # test cases > are v

Re: [algogeeks] array problem

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 g

Re: [algogeeks] Array problem

now i get this!! i thought we have to calculate the sum upto (i-1)th index. thanx for the clarifiacation. On Wed, Mar 14, 2012 at 3:07 PM, Dheeraj Sharma wrote: > you have to calculate the sum of elements which are less than..that > particular element...this is not the question of calculating cu

Re: [algogeeks] Array problem

you have to calculate the sum of elements which are less than..that particular element...this is not the question of calculating cumulative sum On Wed, Mar 14, 2012 at 11:22 AM, sachin sabbarwal wrote: > @gaurav popli: how about this one?? > > findsummat(int arr[],int n) > { >int *sum ; >

Re: [algogeeks] Array problem

@gaurav popli: how about this one?? findsummat(int arr[],int n) { int *sum ; sum =(int*)malloc(sizeof(int)*n); for(int i=0;iwrote: > @piyush : sorry dude , didnt get your algo . actually you are using > different array and i get confused which array to be considered when. > > > > On Mon

Re: [algogeeks] Array problem

@piyush : sorry dude , didnt get your algo . actually you are using different array and i get confused which array to be considered when. On Mon, Mar 12, 2012 at 5:19 PM, Piyush Kapoor wrote: > 1)First map the array numbers into the position in which they would be, if > they are sorted,for exam

Re: [algogeeks] Array problem

I think we can use the counting sort method... On Tue, Mar 13, 2012 at 1:51 AM, sunny agrawal wrote: > @atul > if its sum of numbers lesser than a[i] in left to i, then still i think it > can be solved in O(nlgn) using Balanced Tree structures > ie: if we use AVL tree, then we just need a

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

@sunny : it was a reply to different question. using AVL or RB for the given algo may screw it. On Mon, Mar 12, 2012 at 11:00 PM, sunny agrawal wrote: > @atul > TC can be bound to O(nlgn) using any balanced tree ie: AVL tree, RB tree > as already mentioned in her last post > > On Mon, Mar 12, 201

Re: [algogeeks] Array problem

@atul TC can be bound to O(nlgn) using any balanced tree ie: AVL tree, RB tree as already mentioned in her last post On Mon, Mar 12, 2012 at 10:44 PM, atul anand wrote: > @payal: > TC will not alwayz be O(nlogn) bcozz we are not sure if the tree formed is > balanced. > so worst would be O(n^2) >

Re: [algogeeks] Array problem

@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

Re: [algogeeks] Array problem

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 th

Re: [algogeeks] Array problem

@piyush : i dont knw what modification you have made to the BIT to make it work for this problem . please provide the code for better understanding or algo will do. On Mon, Mar 12, 2012 at 3:56 PM, Piyush Kapoor wrote: > @atul anand : it will work,i can give u the code. > > > On Mon, Mar 12, 20

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

u r right. On Mon, Mar 12, 2012 at 11:17 AM, atul anand wrote: > @sanjiv : wont work for this test case :- > > {1,5,3,6,2,7,8}; > > > On Mon, Mar 12, 2012 at 10:54 AM, sanjiv yadav wrote: > >> @atul anand- It will still work as follows--- >> >> (3,0) >> / \(5,0+3) >>

Re: [algogeeks] Array problem

@sanjiv : wont work for this test case :- {1,5,3,6,2,7,8}; On Mon, Mar 12, 2012 at 10:54 AM, sanjiv yadav wrote: > @atul anand- It will still work as follows--- > > (3,0) > / \(5,0+3) > (1,0) \(6,0+3+5) > \(2,0+1)\(7,

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

@piyush : i dont think so BIT would work over here , we are not just reporting cumulative sum tilll index i. On Mon, Mar 12, 2012 at 12:58 AM, Piyush Kapoor wrote: > This can be done very easily with the help of a Binary Indexed Tree,and it > is very short to code as well.Simply process the numb

Re: [algogeeks] Array problem

@payal : what will be be the structure of the augmented tree , i add 2 to the given input. so input become. ar[]={3,5,1,6,7,8,2}; On Sun, Mar 11, 2012 at 11:07 PM, payal gupta wrote: > the algo vich i thought of is as follows- > > struct node{ > int data; > struct node *left,*right; > int lsum;

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

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 t

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

u r right payal but can u expln o(n) time complexity.. On Sun, Mar 11, 2012 at 6:10 PM, payal gupta wrote: > By Augmented BST- > TC-O(n) > > > On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli wrote: > >> given an array of size n... >> create an array of size n such that ai where ai is the eleme

Re: [algogeeks] Array problem

By Augmented BST- TC-O(n) On Sun, Mar 11, 2012 at 3:08 PM, Gaurav Popli wrote: > given an array of size n... > create an array of size n such that ai where ai is the element in the > new array at index location i is equal to sum of all elements in > original array which are smaller than element a

[algogeeks] Array problem

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 messa

Re: [algogeeks] array problem

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 Sci

Re: [algogeeks] array problem

if i am not wrong , solution is given in this thread and with less complexity :- http://groups.google.com/group/algogeeks/browse_thread/thread/44dd396b22595142/6632ae276b99d4ad?hl=en&lnk=gst&q=Array+Problem+%2B+tushar#6632ae276b99d4ad On Thu, Feb 16, 2012 at 5:54 PM, Devansh Gupta wrote: > On 2

Re: [algogeeks] array problem

On 2/16/12, Amol Sharma wrote: > k,n,b are known and 0 -- > > > Amol Sharma > Third Year Student > Computer Science and Engineering > MNNIT Allahabad > >

Re: [algogeeks] array problem

k,n and b are known to us? Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Wed, Feb 15, 2012 at 11:37 PM, Amol Sharma wrote: > Given an array of size n*k+b.In this array n elements are repeated k times > and 1 elements are repeated b times.find the Element

Re: [algogeeks] Array Problem

yeah...only if given array is sorted ..we can do it in O(n) and O(1) fetch with all given restriction On Wed, Feb 15, 2012 at 10:14 AM, Kartik Sachan wrote: > @atul if array is not sorted we have to take extra array for > this...otherwise this cannn't be done in O(n) time. > > -- > You received

Re: [algogeeks] Array Problem

@atul if array is not sorted we have to take extra array for this...otherwise this cannn't be done in O(n) time. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe f

Re: [algogeeks] Array Problem

@kartik : question says inplace . so using hashing would be violation... i dont think so it can be done if array is unsorted and with given restriction On Wed, Feb 15, 2012 at 10:05 AM, Kartik Sachan wrote: > if n is less than 10^6 hasing works fine ..and we count in O(1) time only > > -- >

Re: [algogeeks] Array Problem

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 algogeek

[algogeeks] Array Problem

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 b

[algogeeks] Array Problem??

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

Re: [algogeeks] ARRAY PROBLEM

First, you need change 0 to -1 Wladimir Araujo Tavares *Federal University of Ceará Homepage | Maratona| * On Thu, Sep 29, 2011 at 7:35 AM, Wladimir Tavares wrote: > Algorithm Kada

Re: [algogeeks] ARRAY PROBLEM

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

Re: [algogeeks] ARRAY PROBLEM

sachan!!amol ke rum par jaakar pooch le. On Thu, Sep 29, 2011 at 1:10 PM, kartik sachan wrote: > ok amol i will do it..but i am unable to convience myself that > this algo will give the desire result > > -- > You received this message because you are subscribed to the Google Groups >

Re: [algogeeks] ARRAY PROBLEM

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 f

Re: [algogeeks] ARRAY PROBLEM

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

Re: [algogeeks] ARRAY PROBLEM

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

Re: [algogeeks] ARRAY PROBLEM

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

Re: [algogeeks] ARRAY PROBLEM

O/P should be 00111010 and sub array is exclusive of start index, inclusive of end index. Nice solution On Thu, Sep 29, 2011 at 11:58 AM, UTKARSH SRIVASTAV wrote: > @Amol +1 > > On Thu, Sep 29, 2011 at 11:52 AM, Amol Sharma wrote: > >> given array- >> 1 0 0 1 1 1 0 1 0 1 >> for our co

Re: [algogeeks] ARRAY PROBLEM

@Amol +1 On Thu, Sep 29, 2011 at 11:52 AM, Amol Sharma wrote: > given array- > 1 0 0 1 1 1 0 1 0 1 > for our convenience lets replace 0 by -1 > array becomes > 1 -1 -1 1 1 1 -1 1 -1 1 > > take another array count which which represents the sum till that index > sum array becomes > 1

Re: [algogeeks] ARRAY PROBLEM

complexity O(n) extra space O(n) -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad On Thu, Sep 29, 2011 at 11

Re: [algogeeks] ARRAY PROBLEM

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

[algogeeks] ARRAY PROBLEM

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

Re: [algogeeks] array problem

+1 Sanjay On Sun, Aug 21, 2011 at 2:59 PM, Dheeraj Sharma wrote: > yeah bt..when we talk abt the complexity..we consider abt the worst case > > On 8/21/11, himanshu kansal wrote: > > problem: There is an array containing integers. > > for every bit in the integer,you have to print a 1 if no

Re: [algogeeks] array problem

yeah bt..when we talk abt the complexity..we consider abt the worst case On 8/21/11, himanshu kansal wrote: > problem: There is an array containing integers. > for every bit in the integer,you have to print a 1 if no of 1s > corresponding to that bit is more than no of 0s corresponding to tha

Re: [algogeeks] array problem

This problem can be reduced if we are taking whole 32 bits... Mean left most all 0's bits are also including then if number is less than 65535 (2^16-1) then make it 0 as 16 bits are at least zero in this case On Sun, Aug 21, 2011 at 2:19 PM, Sanjay Rajpal wrote: > let n be the no.of integers

Re: [algogeeks] array problem

let n be the no.of integers in the array : int i=1,a; int zero,one; for(int a=1;a<=32;a++) { zero=0; one=0; for(int j=0;j zero) { printf("1s are more \n"); } else { printf("0s are more \n"); }

Re: [algogeeks] array problem

yeah i took it in the another way..i ll post it v soon On 8/21/11, himanshu kansal wrote: > problem: There is an array containing integers. > for every bit in the integer,you have to print a 1 if no of 1s > corresponding to that bit is more than no of 0s corresponding to that > bit (counting

Re: [algogeeks] array problem

Similary as we are counting set bits count 0's nd cmpare nd set 1 if coutn(1)>count(0) for each integer in array On Sun, Aug 21, 2011 at 1:44 PM, Sanjay Rajpal wrote: > @Dheeraj : I think u should review the problem again. > What u have posted is a way to find no. of set bits in a number. > But

Re: [algogeeks] array problem

@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

Re: [algogeeks] array problem

while(a) ( a&=(a-1) count++ ) counts number of 1s in number 'a'.. Loop can be breaken if count exceeds 16.. On 8/21/11, himanshu kansal wrote: > problem: There is an array containing integers. > for every bit in the integer,you have to print a 1 if no of 1s > corresponding to that bit is more

Re: [algogeeks] array problem

for this problem, we will have to check all the bits i.e. 32*n where n is the number of integers in the array. n bits in one go. So i think your approach will be fine. Using bitwise operators will not make any difference. if someone knows better solution ,plz post it. Sanju :) On Sun, Aug 21,

[algogeeks] array problem

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

Re: [algogeeks] Array Problem

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 uns

Re: [algogeeks] Array problem

@ps: ..:-) On 5/22/11, Piyush Sinha wrote: > @MONSIEUR.. > someone once said"THE SECRET OF SUCCESS IS TO NEVER REVEAL YOUR > SOURCES..." ;)...:P..:P > > On 5/22/11, MONSIEUR wrote: >> @piyush: excellent buddybtw what was the initial >> spark...???.:-) >> >> On May 21, 1:0

Re: [algogeeks] Array problem

@Amit JaspalThe algo given by me works for the given case..check it On 5/20/11, Anurag Bhatia wrote: > Just need some clarification; sorry I joined the thread late. What are we > trying maximize? A[j] -A[i] such that i > --Anurag > > On Fri, May 20, 2011 at 12:34 AM, Kunal Patil wrote: >

Re: [algogeeks] Array problem

Just need some clarification; sorry I joined the thread late. What are we trying maximize? A[j] -A[i] such that i wrote: > @ Piyush: Excellent Solution...It appears both Correct and O(n)...Good work > !![?] > > Just a minor correction in your algo.[?] > > * while(B[i] * j++; > must

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

@ Piyush: Excellent Solution...It appears both Correct and O(n)...Good work !![?] Just a minor correction in your algo.[?] * while(B[i]http://groups.google.com/group/algogeeks?hl=en. <<363.gif>><<360.gif>>

Re: [algogeeks] Array problem

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 mini

Re: [algogeeks] Array problem

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 wrote: > @Amit: Ohh..Your test case is correct but not my solution..[?] > It only works if it is guaranteed that o

Re: [algogeeks] Array problem

@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

Re: [algogeeks] Array problem

i dnt htink a o(n) soln exists for this problem. On Wed, May 18, 2011 at 3:47 PM, amit kumar 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 wrote: > >> Ohh..If it is so...Sorry !![?] I understood it the different way...[?] >>

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

@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

Re: [algogeeks] Array problem

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

Re: [algogeeks] Array problem

@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 wrote: > Kunal, > Your soluti

Re: [algogeeks] Array problem

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 wrote: > @Piyush Sinha: I doubt correctness of your sol

Re: [algogeeks] Array problem

@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

Re: [algogeeks] Array problem

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(imax1) max1 =j-i; } i++; } return(max1>max2?max1:max2); } * On Mon, May 16, 2011 at 11:36 AM, anuj agarwal wrote: > How about create a BST and then, fo

Re: [algogeeks] Array problem

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:

Re: [algogeeks] Array problem

@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+unsub

Re: [algogeeks] Array problem

@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] wrote: > Given an array A[i..j] find out maximum j-i such that A[i] O(n) time. > > -- > You received t

[algogeeks] Array problem

Given an array A[i..j] find out maximum j-i such that A[i]http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] array problem

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 deve

Re: [algogeeks] Array Problem

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 wrote: > @Chonku: Your algo seems to fail with following input. > Arr1[]= {1,6} > Arr2[]={7} > > > > > On Wed, Aug 18, 2010

Re: [algogeeks] Array Problem

1 more correction .While multiplying we won't multiply by 0(if it is an element). On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan 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 wrote: > >> @Nikhil: Your

Re: [algogeeks] Array Problem

On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan 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 > wrote: > >> Sum all the ele

Re: [algogeeks] Array Problem

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 wrote: > @Chonku: Your algo seems t

Re: [algogeeks] Array Problem

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

  1   2   >