Re: [algogeeks] Re: array question

pl give the algo On Wed, Aug 17, 2011 at 2:50 PM, Sanjay Rajpal wrote: > Yes, sry abhishek , i didnt see the question carefully. > But this can be done with hash map requiring O(n) space and O(n) time. > Sanjay Kumar > B.Tech Final Year > Department of Computer Engineering > National Institute o

Re: [algogeeks] Re: array question

Yes, sry abhishek , i didnt see the question carefully. But this can be done with hash map requiring O(n) space and O(n) time. Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India On Wed, Aug 17, 2011

[algogeeks] Re: array question

Thats right...by doing xor this can't be done...hey sanjay please reconsider your answer. On Aug 17, 2:05 pm, sukran dhawan wrote: > when u xor nos with odd number of times we will get back the same no.only > even occurences will give 0.question is to find the no with even >  occurence.how will y

Re: [algogeeks] Re: array question

See when u xor two same numbers, the result is 0. So as mentioned in the question, all numbers occur twice, so the result will be 0 for them and the one occuring once will be left(as 0 ^ number gives number itself). Hope u got it :) Sanjay Kumar B.Tech Final Year Department of Computer Engineeri

Re: [algogeeks] Re: array question

Oh sorry, i didnt read the question carefully:) Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India On Wed, Aug 17, 2011 at 12:34 AM, Sanjay Rajpal wrote: > See when u xor two same numbers,

Re: [algogeeks] Re: array question

See when u xor two same numbers, the result is 0. So as mentioned in the question, all numbers occur twice, so the result will be 0 for them and the one occuring once will be left(as 0 ^ number gives number itself). Hope u got Sanjay Kumar B.Tech Final Year Department of Computer Engineering Nation

Re: [algogeeks] Re: array question

i cudnt understand how is it done here by using xor by chen.. aftergetting F it wud be the xor of of odd occuring elements, fine, then he wrote if(xor)A1 ==0 how is this logic used?? On Wed, Aug 17, 2011 at 8:17 AM, saurabh singh wrote: > +1 to dave.xor is the way to go. > > > On Tue, Au

Re: [algogeeks] Re: array question

+1 to dave.xor is the way to go. On Tue, Aug 16, 2011 at 7:06 PM, Dave wrote: > @Raghavan: But aren't maps implemented as binary search trees? That > would make insertion and searching O(log n), and the overall operation > O(n log n). > > Dave > > On Aug 16, 4:08 am, Raghavan wrote: > >

[algogeeks] Re: array question

@Raghavan: But aren't maps implemented as binary search trees? That would make insertion and searching O(log n), and the overall operation O(n log n). Dave On Aug 16, 4:08 am, Raghavan wrote: > @sukran: > If you were asking for the map based solution > > space and time complexity would be o(n).

Re: Re: [algogeeks] Re: array question

)logm On Mon, Aug 15, 2011 at 7:18 PM, mohit verma wrote: > thanks guys. > > On Mon, Aug 15, 2011 at 1:12 PM, Nikhil Veliath wrote: > >> Dave tu mahan hai . . . . >> -- Forwarded message -- >> From: "Dipankar Patro" >> Date: 14

Re: Re: [algogeeks] Re: array question

thanks guys. On Mon, Aug 15, 2011 at 1:12 PM, Nikhil Veliath wrote: > Dave tu mahan hai . . . . > -- Forwarded message -- > From: "Dipankar Patro" > Date: 14 Aug 2011 23:27 > Subject: Re: [algogeeks] Re: array question > To: > > @Dave nic

Fwd: Re: [algogeeks] Re: array question

Dave tu mahan hai . . . . -- Forwarded message -- From: "Dipankar Patro" Date: 14 Aug 2011 23:27 Subject: Re: [algogeeks] Re: array question To: @Dave nice algo. Really like it. So the whole complexity depends on the sorting. On 14 August 2011 22:58, D

Re: [algogeeks] Re: array question

@Dave nice algo. Really like it. So the whole complexity depends on the sorting. On 14 August 2011 22:58, Dave wrote: > @Dipankar: If extra space is not allowed, I think the optimal solution > is to sort the two arrays, which takes O(max(m log m, n log n)). Then > the common element can be foun

[algogeeks] Re: array question

@Dipankar: If extra space is not allowed, I think the optimal solution is to sort the two arrays, which takes O(max(m log m, n log n)). Then the common element can be found in O(m + n) by a simple search that starts at i = j = 0 and increments the index of the lesser of a[i] and b[j]. Overall compl

Re: [algogeeks] Re: Array question

@Shikhar 1) Push the first element to stack. 2) for i = 1 to n-1 a) temp =a[i] b) while(stack not empty) int x = pop(&stack) if(x>temp) print(temp); else push(x,stack) break; c) push(temp,stack) 3) After th

Re: [algogeeks] Re: Array question

sorry for the typo ankit, its if(stk.empty()) l = arr.length-1; else l = stk.top; On Tue, Jul 26, 2011 at 6:19 PM, ankit sambyal wrote: > @Akshata : Plz explain ur algo... Its not clear. > Like in the first iteration, > else > l = stk.top; > is getting executed. but stack is empty, so how

Re: [algogeeks] Re: Array question

@Akshata : Plz explain ur algo... Its not clear. Like in the first iteration, else l = stk.top; is getting executed. but stack is empty, so how r u assigning value to l -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group,

Re: [algogeeks] Re: Array question

a crude algo, for(i=end to start) { while(!stk.empty()) { if(arr[i]wrote: > @Piyush, using stack i guess it can be done in O(n) > > > On Tue, Jul 26, 2011 at 5:42 PM, Shikhar wrote: > >> @ankit: you are right...sorry about the error >> >> On Jul 26, 5:11 pm, ankit sambyal wrote: >> > The O/

Re: [algogeeks] Re: Array question

@Piyush, using stack i guess it can be done in O(n) On Tue, Jul 26, 2011 at 5:42 PM, Shikhar wrote: > @ankit: you are right...sorry about the error > > On Jul 26, 5:11 pm, ankit sambyal wrote: > > The O/P of ur example should be 2,2,1,1,1,-1,-1 > > or am I getting it wrong ?? > > -- > You recei

[algogeeks] Re: Array question

@ankit: you are right...sorry about the error On Jul 26, 5:11 pm, ankit sambyal wrote: > The O/P of ur example should be 2,2,1,1,1,-1,-1 > or am I getting it wrong ?? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, se

[algogeeks] Re: Array question

@piyush: Just curious, how exactly can a stack be used in this problem? On Jul 26, 5:00 pm, Piyush Sinha wrote: > Sorry for the above mistakeits not O(n) > > On Tue, Jul 26, 2011 at 5:29 PM, Piyush Sinha wrote: > > > > > > > > > > > Use stack > > > On Tue, Jul 26, 2011 at 5:22 PM, Shikhar wr

[algogeeks] Re: Array Question

Look up the "Subset Sum" problem. I think you may find that you can put together a hybrid algorithm based on the classic method of performing subset sum calculations. I did something similar a few years back. It worked out pretty good as I recall. Dan:-) -- You received this message beca

[algogeeks] Re: Array Question

In O(n^2). Sort two of the arrays, say B and C, into ascending order. For each element in A, search forward in B and backwards in C looking for a zero sum. Something like this, using zero-based arrays of length n: int i, j, k; for( i = 0 ; i < n ; ++i ) { j = 0; k = n-1; while( (j < n)

[algogeeks] Re: array question

How will it be 12 12 5 6 6?? I can understand that the first number in the list is place first so it could be 12 12 6 6 5. How will it be 12 12 5 6 6? On Jun 6, 7:47 am, divya jain wrote: > output willl be 12 12 5 6 6 > > On 6 June 2010 18:27, souravsain wrote: > > > > > @divya: Does your proble

Re: [algogeeks] Re: array question

@Anand Depending upon the sequence of data in the input, an insertion/search into the (unbalanced) BST will take O(n) time causing the overall complexity to shoot up to O(n^2) for each element counted once. Sourav's approach requires a balanced binary search tree. @Divya.. If you know something a

Re: [algogeeks] Re: array question

@souravsain :Your approach works really well.. Here is the Implementation: http://codepad.org/ricAcQtu On Sun, Jun 6, 2010 at 11:40 AM, souravsain wrote: > @divya:go through the elements and keep inserting them in a BST. While > inserting if elements already exists in BST, increase its freque

Re: [algogeeks] Re: array question

The link http://geeksforgeeks.org/?p=1488 has many different solutions and implementation of hashing method. On Mon, Jun 7, 2010 at 12:59 AM, Raj N wrote: > @Anand :Your approach will turn out very crude if elements are something > like 1000, 2000 > keeping an array i.e count[1000] is not feasib

Re: [algogeeks] Re: array question

@Anand :Your approach will turn out very crude if elements are something like 1000, 2000 keeping an array i.e count[1000] is not feasible. I think souravsain's approach is better. On Mon, Jun 7, 2010 at 3:57 AM, Anand wrote: > Here is my approch which runs in O(n). > > http://codepad.org/d3pzYQt

[algogeeks] Re: array question

@Anand: Your solution will take huge space and can easily be made to run out of memory! If arr5[] = {12,12,6,6,635}, you will run into n^3 space complexity. For arr[5]={12,12,6,6,390625} it will be n^6. Sain On Jun 7, 3:27 am, Anand wrote: > Here is my approch which runs in O(n). > > http://cod

Re: [algogeeks] Re: array question

Here is my approch which runs in O(n). http://codepad.org/d3pzYQtW On Sun, Jun 6, 2010 at 7:47 AM, divya jain wrote: > output willl be 12 12 5 6 6 > > > On 6 June 2010 18:27, souravsain wrote: > >> @divya: Does your problem require the output to be sorted also? Wh

[algogeeks] Re: array question

@divya:go through the elements and keep inserting them in a BST. While inserting if elements already exists in BST, increase its frequency (Node of BST has element a nd frequency). Also if elemengs is newly inserted then also place it in a seperate array. So this array (say Array M) will become som

Re: [algogeeks] Re: array question

output willl be 12 12 5 6 6 On 6 June 2010 18:27, souravsain wrote: > @divya: Does your problem require the output to be sorted also? What > will be the output required if inout is 12,5,6,12,6? Will it be > 12,12,6,6,5 or 12,12,5,6,6,? > > Sain > > On Jun 6, 12:01 am, divya wrote: > > Given an

[algogeeks] Re: array question

@divya: Does your problem require the output to be sorted also? What will be the output required if inout is 12,5,6,12,6? Will it be 12,12,6,6,5 or 12,12,5,6,6,? Sain On Jun 6, 12:01 am, divya wrote: > Given an array with some repeating numbers. Like 12,6,5,12,6 > > output: 12,12,6,6,5 > 12 shud

[algogeeks] Re: array question

@sharad: Your code seems will seem to give output 12,3,4 and not 12,3,3,3,4. It semes from the original description of the problem that you also need to keep count of frequency of occurance of items in the map. Secondly, you have iterated through the map and got the elemenst in same order as you h