[algogeeks] Re: Array problem
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 constraint makes no sense. For example, if K=1, you must remember the largest number you have seen using zero memory. If I give you one 32-bit number, and you later give it back to me, you must have used 32 bits of storage to keep that number. Or are you distinguishing between disk storage and memory? Don On Thursday, August 8, 2013 1:02:08 AM UTC-4, payel roy wrote: 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 subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Array Problem
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.* *Kerala- 673601* *+91 7849080702* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Array of intergers with repeating elements
Hi, we can calculate the frequency of all element, Assign sort them in increasing order of frequency. then the first element of sorted list will be the return element. 0bn we can implement it by Min Heap(which is based upon the frequency and reorganise itself as the frequency of element change (dynamically)). On Thu, May 9, 2013 at 12:41 AM, MAC macatad...@gmail.com wrote: sry link was not pasted http://stackoverflow.com/questions/7338070/finding-an-element-in-an-array-where-every-element-is-repeated-odd-number-of-tim thanks --mac On Thu, May 9, 2013 at 12:40 AM, MAC macatad...@gmail.com wrote: if one can explin me this i think this problem will get solved thanks --mac On Wed, May 8, 2013 at 12:02 AM, MAC macatad...@gmail.com wrote: I was asked this in recent amazon onsite interview and asked o write code Given an Array of integers . N elements occur k times and one element occurs b times, in other words there are n+1 distinct Elements. Given that 0 b k find the element occurring b times. We know k is NOT even . thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. -- Regards, Pankaj Kumar Joshi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Array of intergers with repeating elements
@Pankaj: Can you give more details of your algorithm, including the big-O order of time and space. It certainly is not difficult to do it in O(n log n) time and O(n) space, as this can be accomplished by a merge-sort. For fixed data size, O(n) time and O(n) space can be achieved by a radix sort. Once the data is sorted, it is easy to find the unique element. On Friday, May 10, 2013 3:26:13 AM UTC-5, pankaj joshi wrote: Hi, we can calculate the frequency of all element, Assign sort them in increasing order of frequency. then the first element of sorted list will be the return element. 0bn we can implement it by Min Heap(which is based upon the frequency and reorganise itself as the frequency of element change (dynamically)). On Thu, May 9, 2013 at 12:41 AM, MAC macat...@gmail.com javascript:wrote: sry link was not pasted http://stackoverflow.com/questions/7338070/finding-an-element-in-an-array-where-every-element-is-repeated-odd-number-of-tim thanks --mac On Thu, May 9, 2013 at 12:40 AM, MAC macat...@gmail.com javascript:wrote: if one can explin me this i think this problem will get solved thanks --mac On Wed, May 8, 2013 at 12:02 AM, MAC macat...@gmail.com javascript:wrote: I was asked this in recent amazon onsite interview and asked o write code Given an Array of integers . N elements occur k times and one element occurs b times, in other words there are n+1 distinct Elements. Given that 0 b k find the element occurring b times. We know k is NOT even . thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+...@googlegroups.com javascript:. -- Regards, Pankaj Kumar Joshi -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Array of intergers with repeating elements
if one can explin me this i think this problem will get solved thanks --mac On Wed, May 8, 2013 at 12:02 AM, MAC macatad...@gmail.com wrote: I was asked this in recent amazon onsite interview and asked o write code Given an Array of integers . N elements occur k times and one element occurs b times, in other words there are n+1 distinct Elements. Given that 0 b k find the element occurring b times. We know k is NOT even . thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Array of intergers with repeating elements
sry link was not pasted http://stackoverflow.com/questions/7338070/finding-an-element-in-an-array-where-every-element-is-repeated-odd-number-of-tim thanks --mac On Thu, May 9, 2013 at 12:40 AM, MAC macatad...@gmail.com wrote: if one can explin me this i think this problem will get solved thanks --mac On Wed, May 8, 2013 at 12:02 AM, MAC macatad...@gmail.com wrote: I was asked this in recent amazon onsite interview and asked o write code Given an Array of integers . N elements occur k times and one element occurs b times, in other words there are n+1 distinct Elements. Given that 0 b k find the element occurring b times. We know k is NOT even . thanks --mac -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Array Problem
@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
to solve the problem:
/* I have excluded the base condition initializations..*/
F(i, j, k) = ( (i j) ? F(i-1,j, k) : 0 ) || F( i-1, j-1, k - v[i] )
Only those values of F would be calculated for which the condition i=j
holds true..
Here,
v - unsorted array..
i - sub-array of first i elements of v
j - no. of elements picked out of the first i elements
k - the sum obtained by picking j elements out of the first i element
subarray..
Calculate all the values from F(0,0,0) -- F(N, N/2, S) ( for all F(i, j,
k) 's where i=j )
where S = (sum of the unsorted array) / 2 ...
F(i,j,k) will hold only one of the either 2 values :
0 - not possible to make a sum of K for (i, j) pick
1 - possible to make a sum of K for (i, j) pick..
Once all the values have been calculated we have to pick the max { R }
for which F(N, N/2, R) = 1, where 0 = R = S
Thereafter the min difference of 2 equal arrays would be:
(Sum of the unsorted array) - 2*R
On Wednesday, 7 November 2012 19:43:12 UTC+5:30, Arun wrote:
Given an unsorted array, how to divide them into two equal arrays whose
difference of sum is minimum.
--
[algogeeks] Re: Array Problem
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, 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 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 the same array itself i guess but you have to do some
kind of shifting.
by doing this for all the elements and dividing them into two groups.
I hope this helps.
Vishal
On Fri, Nov 16, 2012 at 9:46 AM, bharat b
bagana.bharatku...@gmail.comwrote:
@ 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.com wrote:
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 going to take O(nlogn) complexity.
Kindly share an alternative algorithm if you find one with lower
complexity.
Vishal
On Wed, Nov 7, 2012 at 7:43 PM, Arun Kindra reserve4placem...@gmail.com
wrote:
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 group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array problem
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 to y-th. It means
that the sum for the set {1, 2, 3, 2, 7} will be equal to 13 (1+2+3+7).
1=N=5 and
t is the number of test cases where 1=t=10
all numbers fit in the 32 bit integer range...
suggest some solution..
here is my solution
but it is giving wrong answer fo some unknown test case...plz suggest me
the test case where i am getting wrong answer
#includestdio.h
#includemath.h
int main()
{
int list[5],i,n,j,sum,k,l;char c;long t;
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,n);
for(i=0;in;i++)
{
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,list[i]);
}
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%ld,t);
t=2*t;
while(t)
{
sum=0;
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%c,c);
fflush(stdin);
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d
%d,k,l);
if(c=='Q')
{
for(i=k-1;il-1;i++)
{
for(j=i+1;jl;j++)
{
if(list[i]==list[j])
break;
else if((j==l-1) (list[i]!=list[j]))
{
sum=sum+list[i];
}
}
}
printf
http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(%d\n,sum+list[l-1]);
}
if(c=='U')
{
list[k-1]=l;
}
t--;
}
return 0;
}
--
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/-/wLRpyiBiLuoJ.
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array problem
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 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/ On Fri, Feb 17, 2012 at 12:25 PM, atul anand atul.87fri...@gmail.comwrote: @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 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 is the number repeating b times... next time go through the array again and see whether any number when added with itself b times gives the same result as x, if yes, out put that number. I had seen a solution to a problem where in an array of size 3n+1, each element except one repeating thrice, we need to find the non repeating element in O(n) time O(1) space, i tried to generalize the proof to fit this case... -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array problem
@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 Elements which is repeated b time.( O(n*k+b) expected ) -- 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/ -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array problem
@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 17, 2012 at 4:19 AM, Dave dave_and_da...@juno.com wrote: @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 Elements which is repeated b time.( O(n*k+b) expected ) -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99 http://in.linkedin.com/pub/amol-sharma/21/79b/507 http://www.simplyamol.blogspot.com/ -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array problem
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 http://gplus.to/amolsharma99 http://twitter.com/amolsharma99http://in.linkedin.com/pub/amol-sharma/21/79b/507http://www.simplyamol.blogspot.com/ On Fri, Feb 17, 2012 at 9:39 AM, atul anand atul.87fri...@gmail.com wrote: @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 17, 2012 at 4:19 AM, Dave dave_and_da...@juno.com wrote: @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 Elements which is repeated b time.( O(n*k+b) expected ) -- Amol Sharma Third Year Student Computer Science and Engineering MNNIT Allahabad http://gplus.to/amolsharma99 http://twitter.com/amolsharma99 http://in.linkedin.com/pub/amol-sharma/21/79b/507 http://www.simplyamol.blogspot.com/ -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array problem
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 is the number repeating b times... next time go through the array again and see whether any number when added with itself b times gives the same result as x, if yes, out put that number. I had seen a solution to a problem where in an array of size 3n+1, each element except one repeating thrice, we need to find the non repeating element in O(n) time O(1) space, i tried to generalize the proof to fit this case... -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array problem
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 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 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 is the number repeating b times... next time go through the array again and see whether any number when added with itself b times gives the same result as x, if yes, out put that number. I had seen a solution to a problem where in an array of size 3n+1, each element except one repeating thrice, we need to find the non repeating element in O(n) time O(1) space, i tried to generalize the proof to fit this case... -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array problem
@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 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 is the number repeating b times... next time go through the array again and see whether any number when added with itself b times gives the same result as x, if yes, out put that number. I had seen a solution to a problem where in an array of size 3n+1, each element except one repeating thrice, we need to find the non repeating element in O(n) time O(1) space, i tried to generalize the proof to fit this case... -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
@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 tusharkanta.r...@gmail.com wrote: 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- AMRIT -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
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 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 tusharkanta.r...@gmail.com wrote: 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- AMRIT -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Priyatosh Tiwari* *B. Tech. Third Year(CSE)* *MNNIT Allahabad* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
@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] 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; k=A[i] mod N = k=2 = A[2] = A[2] + 5 = A=1,7,6,0,4 i=2: k=A[i]=6; A[i] 5; k=A[i] mod N = k=1 = A[1] = A[1] + 5 = A=1,12,6,0,4 i=3: k=A[i]=0; A[i] 5; k=0 = A[0] = A[0] + 5 = A=6,12,6,0,4 i=4: k=A[i]=4; A[i] 5; k=4 = A[4] = A[4] + 5 = A=6,12,6,0,9 I'm using the fact that: (c*n + a) mod n =a Now, while searching, for say i=1, k=A[i] = k=12 count=int(k/5) Let me know if any test case fails. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
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)
int arr[]={1,2,1,0,4};
int sz=sizeof(arr)/sizeof(int);
int x,y;
for(int i=0;isz;i++)
{
while(arr[i]!=arr[arr[i]])
{
x=arr[i];
y=arr[arr[i]];
arr[i]=y;
arr[x]=x;
}
}
This will take O(n) time ...as for every loop we are setting one number to
its respective index and then moving to the next number.
2. Now set the count to -1 for all i..such that arr[i] equal to i.
for(int i=0;isz;i++)
{
if(arr[i]==i)
arr[i]=-1;
}
3. Now for all the numbers that are 0 ,we need to increment the count in
their respective index.And set their count =0 as there is no such number
for which arr[i]==i.
for(int i=0;isz;i++)
{
if(arr[i]0)
{
arr[arr[i]]--;
arr[i]=0;
}
}
4.Now this array contains the count at their respective index.
int fun(int arr[],int x)
{
return -arr[x];
}
On Wed, Feb 15, 2012 at 10:48 PM, Dave dave_and_da...@juno.com wrote:
@Tushar: If we are going to use A[i] as an index into the array A[],
we must have 0 = A[i] N.
We can use a negative in A[i] to indicate that i occurs -A[i] times.
The code would look something like this:
//preprocessing...
int i, j, m;
for( i = 0 ; i N, ++i )
{
j = A[i];
while( j = 0 )
{
if( A[j] = 0 )
{
m = A[j];
A[j] = -1;
j = m;
if( j = i ) break;
}
else
{
A[j]--;
break;
}
}
}
Here is how this works: For each value of i, if A[i] 0, we already
have processed it, so nothing more is required. Otherwise, suppose
that A[i] has the value j. Then if A[j] 0 then we already have
processed at least one occurrence of j, so we just decrement A[j] to
indicate that an additional value j has occurred in A. But if A[j] =
0, this is the first time j has occurred. We set the value of A[j] to
-1 to indicate that j has occurred once, but before we lose the value
of A[j], we have to process its value. This results in the while loop
to run through the chain of numbers until we get to an entry we
already have processed.
Prerocessing is O(N) because the statement A[j] = -1 in the while loop
can be executed at most k times and A[j]-- can be executed at most N-1
times during all iterations of the for loop. And since one of these is
executed on every iteration of the while loop, the while loop itself
can be executed no more than N+k-1 2*N times during all iterations
of the for loop.
//determining count of number of original A[i] == x...
count = A[x] 0 ? -x : 0;
Dave
On Feb 14, 10:10 pm, TUSHAR tusharkanta.r...@gmail.com wrote:
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 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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Dheeraj Sharma*
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
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; k=A[i] mod N = k=2 = A[2] = A[2] + 5 = A=1,7,6,0,4 i=2: k=A[i]=6; A[i] 5; k=A[i] mod N = k=1 = A[1] = A[1] + 5 = A=1,12,6,0,4 i=3: k=A[i]=0; A[i] 5; k=0 = A[0] = A[0] + 5 = A=6,12,6,0,4 i=4: k=A[i]=4; A[i] 5; k=4 = A[4] = A[4] + 5 = A=6,12,6,0,9 I'm using the fact that: (c*n + a) mod n =a Now, while searching, for say i=1, k=A[i] = k=12 count=int(k/5) Let me know if any test case fails. -- 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/-/wh65xNNjRksJ. 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
@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 11:16 AM, TUSHAR tusharkanta.r...@gmail.comwrote: 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 this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- AMRIT -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array searching
I don't think it can be done in better than O(n) space and time. On Tue, Nov 22, 2011 at 9:28 PM, himanshu kansal himanshukansal...@gmail.com wrote: @SAM: in your first step, where you are xoring the unique elements, you must be using some DS such as hashtable or something. so space complexity will be O(n). can someone reduces this O(n) space complexity.because it wont be a good approach if there are many elements in the array On Fri, Nov 18, 2011 at 9:26 AM, SAMM somnath.nit...@gmail.com wrote: On 11/18/11, SAMM somnath.nit...@gmail.com wrote: For example the array has .. 1 4 2 6 7 4 8 3.. xor the elements in the array will give (1^2^6^7^8^3). now xor the unique elements using hash table ,It gives (1^4^2^6^7^8^3). Now xor these two value which gives 4. On 11/18/11, Dave dave_and_da...@juno.com wrote: @SAMM: It sounds like a circular argument. How do you XOR all of the unique elements without first finding the repeated ones? Dave On Nov 17, 11:24 am, SAMM somnath.nit...@gmail.com wrote: Yes we can do so in O(n) . First find the XOR of all unique elements using hash table or some other DS. Secondly XOR all the elements of the array .which will hav the xor of elements other thn the element repeated twice. Now XOR the above two value which will give the answer.. On 11/17/11, himanshu kansal himanshukansal...@gmail.com wrote: consider an array having n elements.out of which one number is repeated twiceother number are repeated odd number of times(for simplicity, assume other numbers are occurring just once) can you find the number that is repeated twice in O(n) time??? PS: numbers are not from a particular range. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- Somnath Singh -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Himanshu Kansal Msc Comp. sc. (University of Delhi) -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array searching
@SAM: in your first step, where you are xoring the unique elements, you must be using some DS such as hashtable or something. so space complexity will be O(n). can someone reduces this O(n) space complexity.because it wont be a good approach if there are many elements in the array On Fri, Nov 18, 2011 at 9:26 AM, SAMM somnath.nit...@gmail.com wrote: On 11/18/11, SAMM somnath.nit...@gmail.com wrote: For example the array has .. 1 4 2 6 7 4 8 3.. xor the elements in the array will give (1^2^6^7^8^3). now xor the unique elements using hash table ,It gives (1^4^2^6^7^8^3). Now xor these two value which gives 4. On 11/18/11, Dave dave_and_da...@juno.com wrote: @SAMM: It sounds like a circular argument. How do you XOR all of the unique elements without first finding the repeated ones? Dave On Nov 17, 11:24 am, SAMM somnath.nit...@gmail.com wrote: Yes we can do so in O(n) . First find the XOR of all unique elements using hash table or some other DS. Secondly XOR all the elements of the array .which will hav the xor of elements other thn the element repeated twice. Now XOR the above two value which will give the answer.. On 11/17/11, himanshu kansal himanshukansal...@gmail.com wrote: consider an array having n elements.out of which one number is repeated twiceother number are repeated odd number of times(for simplicity, assume other numbers are occurring just once) can you find the number that is repeated twice in O(n) time??? PS: numbers are not from a particular range. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- Somnath Singh -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Regards Himanshu Kansal Msc Comp. sc. (University of Delhi) -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array searching
@SAMM: It sounds like a circular argument. How do you XOR all of the unique elements without first finding the repeated ones? Dave On Nov 17, 11:24 am, SAMM somnath.nit...@gmail.com wrote: Yes we can do so in O(n) . First find the XOR of all unique elements using hash table or some other DS. Secondly XOR all the elements of the array .which will hav the xor of elements other thn the element repeated twice. Now XOR the above two value which will give the answer.. On 11/17/11, himanshu kansal himanshukansal...@gmail.com wrote: consider an array having n elements.out of which one number is repeated twiceother number are repeated odd number of times(for simplicity, assume other numbers are occurring just once) can you find the number that is repeated twice in O(n) time??? PS: numbers are not from a particular range. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array searching
On 11/18/11, SAMM somnath.nit...@gmail.com wrote: For example the array has .. 1 4 2 6 7 4 8 3.. xor the elements in the array will give (1^2^6^7^8^3). now xor the unique elements using hash table ,It gives (1^4^2^6^7^8^3). Now xor these two value which gives 4. On 11/18/11, Dave dave_and_da...@juno.com wrote: @SAMM: It sounds like a circular argument. How do you XOR all of the unique elements without first finding the repeated ones? Dave On Nov 17, 11:24 am, SAMM somnath.nit...@gmail.com wrote: Yes we can do so in O(n) . First find the XOR of all unique elements using hash table or some other DS. Secondly XOR all the elements of the array .which will hav the xor of elements other thn the element repeated twice. Now XOR the above two value which will give the answer.. On 11/17/11, himanshu kansal himanshukansal...@gmail.com wrote: consider an array having n elements.out of which one number is repeated twiceother number are repeated odd number of times(for simplicity, assume other numbers are occurring just once) can you find the number that is repeated twice in O(n) time??? PS: numbers are not from a particular range. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Somnath Singh -- Somnath Singh -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
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;
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, n-1, 0)
}
}
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
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 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
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, n-1, 0)
}
}
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem??
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], 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). You are given with any such A. Find out corresponding B? 2). You are given with any such B. Find out corresponding A? Please provide solution in O(n),if possible?? -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
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 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],
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). You are given with any such A. Find out corresponding B?
2). You are given with any such B. Find out corresponding A?
Please provide solution in O(n),if possible??
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
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 = that element.
if the next element is smaller, assign 0 and repeat LOOP
if the next element's index is 0, check and exit
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 0;
max = 2;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 1;
max = 2;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 2;
max = 2;
3 max i.e. 2
b[n - 3] = counter = b[1] = 2
max = 3;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 3;
max = 3;
4 max i.e. 3
b[n - 4] = counter = b[0] = 3
Edge Cases: It shall remain all 0's for all same numbers as well as
ascending numbers.
On Tue, Oct 4, 2011 at 7:13 AM, DIVIJ WADHAWAN divij...@gmail.com wrote:
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 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],
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). You are given with any such A. Find out corresponding B?
2). You are given with any such B. Find out corresponding A?
Please provide solution in O(n),if possible??
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Anup Ghatage
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
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,
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 = that element.
if the next element is smaller, assign 0 and repeat LOOP
if the next element's index is 0, check and exit
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 0;
max = 2;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 1;
max = 2;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 2;
max = 2;
3 max i.e. 2
b[n - 3] = counter = b[1] = 2
max = 3;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 3;
max = 3;
4 max i.e. 3
b[n - 4] = counter = b[0] = 3
Edge Cases: It shall remain all 0's for all same numbers as well as
ascending numbers.
On Tue, Oct 4, 2011 at 7:13 AM, DIVIJ WADHAWAN divij...@gmail.com wrote:
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 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],
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). You are given with any such A. Find out corresponding B?
2). You are given with any such B. Find out corresponding A?
Please provide solution in O(n),if possible??
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Anup Ghatage
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
@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 ashg...@gmail.com wrote:
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,
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 = that element.
if the next element is smaller, assign 0 and repeat LOOP
if the next element's index is 0, check and exit
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 0;
max = 2;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 1;
max = 2;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 2;
max = 2;
3 max i.e. 2
b[n - 3] = counter = b[1] = 2
max = 3;
\/
A : ( 4, 3, 1, 2 )
B : ( 0, 0, 0, 0 )
counter = 3;
max = 3;
4 max i.e. 3
b[n - 4] = counter = b[0] = 3
Edge Cases: It shall remain all 0's for all same numbers as well as
ascending numbers.
On Tue, Oct 4, 2011 at 7:13 AM, DIVIJ WADHAWAN divij...@gmail.comwrote:
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 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],
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). You are given with any such A. Find out corresponding B?
2). You are given with any such B. Find out corresponding A?
Please provide solution in O(n),if possible??
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Anup Ghatage
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
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 algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
@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 this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array ques based on correlation factor
thanks a lot guys...
On Sep 19, 7:22 pm, Don dondod...@gmail.com wrote:
This depends on rnd being a good pseudo-random generator. I don't
suggest using the RNG built into many compilers. Instead use something
like the Mersenne Twister which produces much better results with an
extremely long period. My Random class has a gen method which
returns an integer in the range 0..n-1.
int *shuffle(int n)
{
int *result = (int *)malloc(n * sizeof(int));
result[0] = 0;
for(int i = 1; i n; ++i)
{
int j = rnd.gen(i+1);
result[i] = result[j];
result[j] = i;
}
return result;
}
On Sep 17, 12:12 pm, sivaviknesh s sivavikne...@gmail.com wrote:
Write a method fill up an array of size n - and returns the array to the
caller - with the following conditions
1. the numbers shud be between 0 to n-1
2. no repeated numbers
3. the method should have a deterministic time to fill the arrays
4. arrays returned from the method should have low-correlation factor
...btw what does 4 th point mean? what is a correlation factor?? Plz provide
code and explain...
--
Regards,
$iva
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array ques based on correlation factor
This depends on rnd being a good pseudo-random generator. I don't
suggest using the RNG built into many compilers. Instead use something
like the Mersenne Twister which produces much better results with an
extremely long period. My Random class has a gen method which
returns an integer in the range 0..n-1.
int *shuffle(int n)
{
int *result = (int *)malloc(n * sizeof(int));
result[0] = 0;
for(int i = 1; i n; ++i)
{
int j = rnd.gen(i+1);
result[i] = result[j];
result[j] = i;
}
return result;
}
On Sep 17, 12:12 pm, sivaviknesh s sivavikne...@gmail.com wrote:
Write a method fill up an array of size n - and returns the array to the
caller - with the following conditions
1. the numbers shud be between 0 to n-1
2. no repeated numbers
3. the method should have a deterministic time to fill the arrays
4. arrays returned from the method should have low-correlation factor
...btw what does 4 th point mean? what is a correlation factor?? Plz provide
code and explain...
--
Regards,
$iva
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array problem
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)
{
one++;
}
else
{
zero++;
}
}
if(one zero)
{
printf(1s are more \n);
}
else
{
printf(0s are more \n);
}
i=i1;
}
Correct me if m wrong.
Sanju
:)
On Sun, Aug 21, 2011 at 1:28 AM, Dheeraj Sharma dheerajsharma1...@gmail.com
wrote:
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 to that
bit (counting that bit in all the integers) otherwise print a 0(if no
of 0s corresponding to that bit are more).
this you have to do for all bits in the integers.
assumption:integers are of 32bits.
no of integers in array are odd...(i.e. there is no case like no. of
1s=no. of 0s)
i have done this by counting the no of 1s and 0s for all bits.
but can anyone suggest any other efficient approach (somewhat using
bitwise operators).
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Dheeraj Sharma*
Comp Engg.
NIT Kurukshetra
+91 8950264227
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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 National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286, +91-9729683720 On Tue, Aug 16, 2011 at 10:07 PM, Anika Jain anika.jai...@gmail.com wrote: 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 saurab...@gmail.comwrote: +1 to dave.xor is the way to go. On Tue, Aug 16, 2011 at 7:06 PM, Dave dave_and_da...@juno.com 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 its...@gmail.com wrote: @sukran: If you were asking for the map based solution space and time complexity would be o(n). On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan sukrandha...@gmail.com wrote: what is the complexity in which it has been done ? On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote: Given an array of integers. Each number in the array repeats ODD number of times, but only 1 number repeated for EVEN number of times. Find that number. -- thanks --mac -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards, Raghavan KL -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 sanjay.raj...@live.inwrote: 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 National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India Contact: +91-8053566286, +91-9729683720 On Tue, Aug 16, 2011 at 10:07 PM, Anika Jain anika.jai...@gmail.comwrote: 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 saurab...@gmail.comwrote: +1 to dave.xor is the way to go. On Tue, Aug 16, 2011 at 7:06 PM, Dave dave_and_da...@juno.com 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 its...@gmail.com wrote: @sukran: If you were asking for the map based solution space and time complexity would be o(n). On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan sukrandha...@gmail.comwrote: what is the complexity in which it has been done ? On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote: Given an array of integers. Each number in the array repeats ODD number of times, but only 1 number repeated for EVEN number of times. Find that number. -- thanks --mac -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards, Raghavan KL -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India On Tue, Aug 16, 2011 at 10:07 PM, Anika Jain anika.jai...@gmail.com wrote: 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 saurab...@gmail.comwrote: +1 to dave.xor is the way to go. On Tue, Aug 16, 2011 at 7:06 PM, Dave dave_and_da...@juno.com 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 its...@gmail.com wrote: @sukran: If you were asking for the map based solution space and time complexity would be o(n). On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan sukrandha...@gmail.com wrote: what is the complexity in which it has been done ? On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote: Given an array of integers. Each number in the array repeats ODD number of times, but only 1 number repeated for EVEN number of times. Find that number. -- thanks --mac -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards, Raghavan KL -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[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 sukrandha...@gmail.com 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 you find that no? On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote: Given an array of integers. Each number in the array repeats ODD number of times, but only 1 number repeated for EVEN number of times. Find that number. -- thanks --mac -- You wreceived 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 at 2:15 AM, Abhishek Yadav abhishek30.nit...@gmail.com wrote: Thats right...by doing xor this can't be done...hey sanjay please reconsider your answer. On Aug 17, 2:05 pm, sukran dhawan sukrandha...@gmail.com 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 you find that no? On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote: Given an array of integers. Each number in the array repeats ODD number of times, but only 1 number repeated for EVEN number of times. Find that number. -- thanks --mac -- You wreceived 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array question
pl give the algo On Wed, Aug 17, 2011 at 2:50 PM, Sanjay Rajpal srn...@gmail.com 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 of Technology Kurukshetra Kurukshetra - 136119 Haryana, India On Wed, Aug 17, 2011 at 2:15 AM, Abhishek Yadav abhishek30.nit...@gmail.com wrote: Thats right...by doing xor this can't be done...hey sanjay please reconsider your answer. On Aug 17, 2:05 pm, sukran dhawan sukrandha...@gmail.com 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 you find that no? On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote: Given an array of integers. Each number in the array repeats ODD number of times, but only 1 number repeated for EVEN number of times. Find that number. -- thanks --mac -- You wreceived 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text - - Show quoted text - -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[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 its...@gmail.com wrote: @sukran: If you were asking for the map based solution space and time complexity would be o(n). On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan sukrandha...@gmail.comwrote: what is the complexity in which it has been done ? On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote: Given an array of integers. Each number in the array repeats ODD number of times, but only 1 number repeated for EVEN number of times. Find that number. -- thanks --mac -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards, Raghavan KL -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array question
+1 to dave.xor is the way to go. On Tue, Aug 16, 2011 at 7:06 PM, Dave dave_and_da...@juno.com 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 its...@gmail.com wrote: @sukran: If you were asking for the map based solution space and time complexity would be o(n). On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan sukrandha...@gmail.com wrote: what is the complexity in which it has been done ? On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote: Given an array of integers. Each number in the array repeats ODD number of times, but only 1 number repeated for EVEN number of times. Find that number. -- thanks --mac -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards, Raghavan KL -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 saurab...@gmail.com wrote: +1 to dave.xor is the way to go. On Tue, Aug 16, 2011 at 7:06 PM, Dave dave_and_da...@juno.com 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 its...@gmail.com wrote: @sukran: If you were asking for the map based solution space and time complexity would be o(n). On Tue, Aug 16, 2011 at 2:34 PM, sukran dhawan sukrandha...@gmail.com wrote: what is the complexity in which it has been done ? On Tue, Aug 16, 2011 at 1:41 PM, MAC macatad...@gmail.com wrote: Given an array of integers. Each number in the array repeats ODD number of times, but only 1 number repeated for EVEN number of times. Find that number. -- thanks --mac -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks and Regards, Raghavan KL -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Saurabh Singh B.Tech (Computer Science) MNNIT ALLAHABAD -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Fwd: Re: [algogeeks] Re: array question
Dave tu mahan hai . . . . -- Forwarded message -- From: Dipankar Patro dip10c...@gmail.com Date: 14 Aug 2011 23:27 Subject: Re: [algogeeks] Re: array question To: algogeeks@googlegroups.com @Dave nice algo. Really like it. So the whole complexity depends on the sorting. On 14 August 2011 22:58, Dave dave_and_da...@juno.com 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 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 complexity is O(max(m log m, n log n)). Dave On Aug 14, 8:24 am, Dipankar Patro dip10c...@gmail.com wrote: @ Sagar: What if extra space in not allowed? I think then we have to use the binary search method... On 14 August 2011 18:50, sagar pareek sagarpar...@gmail.com wrote: Hashing O(n+m) On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro dip10c...@gmail.com wrote: how about binary search of each element from array 1 on array 2? overall complexity : O(nlogn) On 14 August 2011 18:46, mohit verma mohit89m...@gmail.com wrote: example: array 1 :: 1 2 3 4 5 6 7 8 9 10 15 array 2:: 23 34 56 13 15 57 432 348 On Sun, Aug 14, 2011 at 6:44 PM, shady sinv...@gmail.com wrote: meaning ? what is a common element ? example ??? On Sun, Aug 14, 2011 at 6:37 PM, mohit verma mohit89m...@gmail.com wrote: given two arrays : with all distinct elements but one element in common. Find the common element in optimal time. -- *MOHIT VERMA* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *MOHIT VERMA* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ** Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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, visit this group at http
Re: Re: [algogeeks] Re: array question
thanks guys. On Mon, Aug 15, 2011 at 1:12 PM, Nikhil Veliath nve...@gmail.com wrote: Dave tu mahan hai . . . . -- Forwarded message -- From: Dipankar Patro dip10c...@gmail.com Date: 14 Aug 2011 23:27 Subject: Re: [algogeeks] Re: array question To: algogeeks@googlegroups.com @Dave nice algo. Really like it. So the whole complexity depends on the sorting. On 14 August 2011 22:58, Dave dave_and_da...@juno.com 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 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 complexity is O(max(m log m, n log n)). Dave On Aug 14, 8:24 am, Dipankar Patro dip10c...@gmail.com wrote: @ Sagar: What if extra space in not allowed? I think then we have to use the binary search method... On 14 August 2011 18:50, sagar pareek sagarpar...@gmail.com wrote: Hashing O(n+m) On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro dip10c...@gmail.com wrote: how about binary search of each element from array 1 on array 2? overall complexity : O(nlogn) On 14 August 2011 18:46, mohit verma mohit89m...@gmail.com wrote: example: array 1 :: 1 2 3 4 5 6 7 8 9 10 15 array 2:: 23 34 56 13 15 57 432 348 On Sun, Aug 14, 2011 at 6:44 PM, shady sinv...@gmail.com wrote: meaning ? what is a common element ? example ??? On Sun, Aug 14, 2011 at 6:37 PM, mohit verma mohit89m...@gmail.comwrote: given two arrays : with all distinct elements but one element in common. Find the common element in optimal time. -- *MOHIT VERMA* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *MOHIT VERMA* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ** Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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
Re: Re: [algogeeks] Re: array question
Step 1: Sort the smaller array mlogm Step 2: For every element in the bigger array, do a binary search on this sorted smaller array. n*logm Total complexity (m+n)logm You could sort the other array and binary search from the smaller array but then it would be (m+n)logn which is bigger than (m+n)logm On Mon, Aug 15, 2011 at 7:18 PM, mohit verma mohit89m...@gmail.com wrote: thanks guys. On Mon, Aug 15, 2011 at 1:12 PM, Nikhil Veliath nve...@gmail.com wrote: Dave tu mahan hai . . . . -- Forwarded message -- From: Dipankar Patro dip10c...@gmail.com Date: 14 Aug 2011 23:27 Subject: Re: [algogeeks] Re: array question To: algogeeks@googlegroups.com @Dave nice algo. Really like it. So the whole complexity depends on the sorting. On 14 August 2011 22:58, Dave dave_and_da...@juno.com 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 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 complexity is O(max(m log m, n log n)). Dave On Aug 14, 8:24 am, Dipankar Patro dip10c...@gmail.com wrote: @ Sagar: What if extra space in not allowed? I think then we have to use the binary search method... On 14 August 2011 18:50, sagar pareek sagarpar...@gmail.com wrote: Hashing O(n+m) On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro dip10c...@gmail.com wrote: how about binary search of each element from array 1 on array 2? overall complexity : O(nlogn) On 14 August 2011 18:46, mohit verma mohit89m...@gmail.com wrote: example: array 1 :: 1 2 3 4 5 6 7 8 9 10 15 array 2:: 23 34 56 13 15 57 432 348 On Sun, Aug 14, 2011 at 6:44 PM, shady sinv...@gmail.com wrote: meaning ? what is a common element ? example ??? On Sun, Aug 14, 2011 at 6:37 PM, mohit verma mohit89m...@gmail.comwrote: given two arrays : with all distinct elements but one element in common. Find the common element in optimal time. -- *MOHIT VERMA* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *MOHIT VERMA* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ** Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en
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 dave_and_da...@juno.com 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 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 complexity is O(max(m log m, n log n)). Dave On Aug 14, 8:24 am, Dipankar Patro dip10c...@gmail.com wrote: @ Sagar: What if extra space in not allowed? I think then we have to use the binary search method... On 14 August 2011 18:50, sagar pareek sagarpar...@gmail.com wrote: Hashing O(n+m) On Sun, Aug 14, 2011 at 6:48 PM, Dipankar Patro dip10c...@gmail.com wrote: how about binary search of each element from array 1 on array 2? overall complexity : O(nlogn) On 14 August 2011 18:46, mohit verma mohit89m...@gmail.com wrote: example: array 1 :: 1 2 3 4 5 6 7 8 9 10 15 array 2:: 23 34 56 13 15 57 432 348 On Sun, Aug 14, 2011 at 6:44 PM, shady sinv...@gmail.com wrote: meaning ? what is a common element ? example ??? On Sun, Aug 14, 2011 at 6:37 PM, mohit verma mohit89m...@gmail.com wrote: given two arrays : with all distinct elements but one element in common. Find the common element in optimal time. -- *MOHIT VERMA* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *MOHIT VERMA* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ** Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- ___ Please do not print this e-mail until urgent requirement. Go Green!! Save Papers = Save Trees -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array
yes we can. On Aug 3, 10:08 pm, Arshad Alam alam3...@gmail.com wrote: can we insert 16 elements of one dimension array in 4*4 of double dimension array? -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array constant
in my compiler its not showing any error !! -- 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/-/fXDj3Q29epwJ. 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array doubt
take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.comwrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array doubt
any specific reason fr maintaining a BST...can we simply have 2 more arrays...one dat keeps order and the oder that keeps count correspondingly... is a BST more efficient than an array?? On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array doubt
nivedita: wts the use to maintaining BST.. if the same purpose can be fulfilled by an array .. but this can be a good method if the range of numbers is pretty large.. den making a hash count can be difficult.. On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array doubt
maintaining the bst of n element in worst case will take n square time complexity ..do we have a better solution for worst case On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh sukhmeet2...@gmail.comwrote: nivedita: wts the use to maintaining BST.. if the same purpose can be fulfilled by an array .. but this can be a good method if the range of numbers is pretty large.. den making a hash count can be difficult.. On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array doubt
i tried making a program using arrays...bt im getting segmentation error...can anybody expalin y... http://ideone.com/bEUUv On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora vivaciousnived...@gmail.com wrote: @rahul- balanced BST can be maintained.to remove worst case ! @sukhmeet- i did not gt your method completely ..u are trying to maintain hashmap or double dimension array of number and count? @aditi- for array we will have overhead of searching if element is present or not ..in O(n) time while it will be O(logn) in BST. in array we cannot do binary search as it will not be sorted to improve search . On Jul 31, 12:31 am, rahul mittal rahulmitta...@gmail.com wrote: maintaining the bst of n element in worst case will take n square time complexity ..do we have a better solution for worst case On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh sukhmeet2...@gmail.com wrote: nivedita: wts the use to maintaining BST.. if the same purpose can be fulfilled by an array .. but this can be a good method if the range of numbers is pretty large.. den making a hash count can be difficult.. On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Aditi Garg Undergraduate Student Electronics Communication Divison NETAJI SUBHAS INSTITUTE OF TECHNOLOGY Sector 3, Dwarka New Delhi -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array doubt
@nivedita:can u do this in o(n) time , i suppose your algorithm takes 0(nlogn) time On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora vivaciousnived...@gmail.com wrote: @rahul- balanced BST can be maintained.to remove worst case ! @sukhmeet- i did not gt your method completely ..u are trying to maintain hashmap or double dimension array of number and count? @aditi- for array we will have overhead of searching if element is present or not ..in O(n) time while it will be O(logn) in BST. in array we cannot do binary search as it will not be sorted to improve search . On Jul 31, 12:31 am, rahul mittal rahulmitta...@gmail.com wrote: maintaining the bst of n element in worst case will take n square time complexity ..do we have a better solution for worst case On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh sukhmeet2...@gmail.com wrote: nivedita: wts the use to maintaining BST.. if the same purpose can be fulfilled by an array .. but this can be a good method if the range of numbers is pretty large.. den making a hash count can be difficult.. On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array doubt
Create a balance BST. Maintain counter. Whenever You hit duplicate increase the counter while inserting. O(nlogn) for creating it and O(N) space. Now while traverse the array. If you find the element, then print it acco the counter value. After printing delete it. if not found continue traversing. - Show quoted text - On Sun, Jul 31, 2011 at 1:21 AM, rahul mittal rahulmitta...@gmail.comwrote: @nivedita:can u do this in o(n) time , i suppose your algorithm takes 0(nlogn) time On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora vivaciousnived...@gmail.com wrote: @rahul- balanced BST can be maintained.to remove worst case ! @sukhmeet- i did not gt your method completely ..u are trying to maintain hashmap or double dimension array of number and count? @aditi- for array we will have overhead of searching if element is present or not ..in O(n) time while it will be O(logn) in BST. in array we cannot do binary search as it will not be sorted to improve search . On Jul 31, 12:31 am, rahul mittal rahulmitta...@gmail.com wrote: maintaining the bst of n element in worst case will take n square time complexity ..do we have a better solution for worst case On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh sukhmeet2...@gmail.comwrote: nivedita: wts the use to maintaining BST.. if the same purpose can be fulfilled by an array .. but this can be a good method if the range of numbers is pretty large.. den making a hash count can be difficult.. On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array doubt
@neeraj:deleting after printing will adds to complexity.. On Sun, Jul 31, 2011 at 1:34 AM, Neeraj Gupta neeraj.gupta...@gmail.comwrote: Create a balance BST. Maintain counter. Whenever You hit duplicate increase the counter while inserting. O(nlogn) for creating it and O(N) space. Now while traverse the array. If you find the element, then print it acco the counter value. After printing delete it. if not found continue traversing. - Show quoted text - On Sun, Jul 31, 2011 at 1:21 AM, rahul mittal rahulmitta...@gmail.comwrote: @nivedita:can u do this in o(n) time , i suppose your algorithm takes 0(nlogn) time On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora vivaciousnived...@gmail.com wrote: @rahul- balanced BST can be maintained.to remove worst case ! @sukhmeet- i did not gt your method completely ..u are trying to maintain hashmap or double dimension array of number and count? @aditi- for array we will have overhead of searching if element is present or not ..in O(n) time while it will be O(logn) in BST. in array we cannot do binary search as it will not be sorted to improve search . On Jul 31, 12:31 am, rahul mittal rahulmitta...@gmail.com wrote: maintaining the bst of n element in worst case will take n square time complexity ..do we have a better solution for worst case On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh sukhmeet2...@gmail.comwrote: nivedita: wts the use to maintaining BST.. if the same purpose can be fulfilled by an array .. but this can be a good method if the range of numbers is pretty large.. den making a hash count can be difficult.. On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at
[algogeeks] Re: Array doubt
ok lets think in terms of hashmap of number and frequency we definitly have to maintain an order array . traverse original array , we check if its present in hashmap ..if not - 1)add it to hashmap and set frequency to 1 2)add it in order array if yes then increment frequency by 1. searching taking O(1) time . now traverse order array..search for corresponding freq and print this should take o(n) time...let me know if i faultered anywhere. @aditi- pls dont use just arrays..its not efficient way. On Jul 31, 12:51 am, rahul mittal rahulmitta...@gmail.com wrote: @nivedita:can u do this in o(n) time , i suppose your algorithm takes 0(nlogn) time On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora vivaciousnived...@gmail.com wrote: @rahul- balanced BST can be maintained.to remove worst case ! @sukhmeet- i did not gt your method completely ..u are trying to maintain hashmap or double dimension array of number and count? @aditi- for array we will have overhead of searching if element is present or not ..in O(n) time while it will be O(logn) in BST. in array we cannot do binary search as it will not be sorted to improve search . On Jul 31, 12:31 am, rahul mittal rahulmitta...@gmail.com wrote: maintaining the bst of n element in worst case will take n square time complexity ..do we have a better solution for worst case On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh sukhmeet2...@gmail.com wrote: nivedita: wts the use to maintaining BST.. if the same purpose can be fulfilled by an array .. but this can be a good method if the range of numbers is pretty large.. den making a hash count can be difficult.. On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array doubt
Yes, i agree, it will increase the code complexity only. you can just set the counter to -ve value only. On Sun, Jul 31, 2011 at 1:38 AM, Kamakshii Aggarwal kamakshi...@gmail.comwrote: @neeraj:deleting after printing will adds to complexity.. On Sun, Jul 31, 2011 at 1:34 AM, Neeraj Gupta neeraj.gupta...@gmail.comwrote: Create a balance BST. Maintain counter. Whenever You hit duplicate increase the counter while inserting. O(nlogn) for creating it and O(N) space. Now while traverse the array. If you find the element, then print it acco the counter value. After printing delete it. if not found continue traversing. - Show quoted text - On Sun, Jul 31, 2011 at 1:21 AM, rahul mittal rahulmitta...@gmail.comwrote: @nivedita:can u do this in o(n) time , i suppose your algorithm takes 0(nlogn) time On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora vivaciousnived...@gmail.com wrote: @rahul- balanced BST can be maintained.to remove worst case ! @sukhmeet- i did not gt your method completely ..u are trying to maintain hashmap or double dimension array of number and count? @aditi- for array we will have overhead of searching if element is present or not ..in O(n) time while it will be O(logn) in BST. in array we cannot do binary search as it will not be sorted to improve search . On Jul 31, 12:31 am, rahul mittal rahulmitta...@gmail.com wrote: maintaining the bst of n element in worst case will take n square time complexity ..do we have a better solution for worst case On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh sukhmeet2...@gmail.comwrote: nivedita: wts the use to maintaining BST.. if the same purpose can be fulfilled by an array .. but this can be a good method if the range of numbers is pretty large.. den making a hash count can be difficult.. On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email
Re: [algogeeks] Re: Array doubt
@nivedita :hashing will not work if the range of nos is high On Sun, Jul 31, 2011 at 1:40 AM, nivedita arora vivaciousnived...@gmail.com wrote: ok lets think in terms of hashmap of number and frequency we definitly have to maintain an order array . traverse original array , we check if its present in hashmap ..if not - 1)add it to hashmap and set frequency to 1 2)add it in order array if yes then increment frequency by 1. searching taking O(1) time . now traverse order array..search for corresponding freq and print this should take o(n) time...let me know if i faultered anywhere. @aditi- pls dont use just arrays..its not efficient way. On Jul 31, 12:51 am, rahul mittal rahulmitta...@gmail.com wrote: @nivedita:can u do this in o(n) time , i suppose your algorithm takes 0(nlogn) time On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora vivaciousnived...@gmail.com wrote: @rahul- balanced BST can be maintained.to remove worst case ! @sukhmeet- i did not gt your method completely ..u are trying to maintain hashmap or double dimension array of number and count? @aditi- for array we will have overhead of searching if element is present or not ..in O(n) time while it will be O(logn) in BST. in array we cannot do binary search as it will not be sorted to improve search . On Jul 31, 12:31 am, rahul mittal rahulmitta...@gmail.com wrote: maintaining the bst of n element in worst case will take n square time complexity ..do we have a better solution for worst case On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh sukhmeet2...@gmail.com wrote: nivedita: wts the use to maintaining BST.. if the same purpose can be fulfilled by an array .. but this can be a good method if the range of numbers is pretty large.. den making a hash count can be difficult.. On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at
[algogeeks] Re: Array doubt
that is why i gave BST algo first :) but rahul wanted me to give O(n) algo On Jul 31, 1:15 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote: @nivedita :hashing will not work if the range of nos is high On Sun, Jul 31, 2011 at 1:40 AM, nivedita arora vivaciousnived...@gmail.com wrote: ok lets think in terms of hashmap of number and frequency we definitly have to maintain an order array . traverse original array , we check if its present in hashmap ..if not - 1)add it to hashmap and set frequency to 1 2)add it in order array if yes then increment frequency by 1. searching taking O(1) time . now traverse order array..search for corresponding freq and print this should take o(n) time...let me know if i faultered anywhere. @aditi- pls dont use just arrays..its not efficient way. On Jul 31, 12:51 am, rahul mittal rahulmitta...@gmail.com wrote: @nivedita:can u do this in o(n) time , i suppose your algorithm takes 0(nlogn) time On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora vivaciousnived...@gmail.com wrote: @rahul- balanced BST can be maintained.to remove worst case ! @sukhmeet- i did not gt your method completely ..u are trying to maintain hashmap or double dimension array of number and count? @aditi- for array we will have overhead of searching if element is present or not ..in O(n) time while it will be O(logn) in BST. in array we cannot do binary search as it will not be sorted to improve search . On Jul 31, 12:31 am, rahul mittal rahulmitta...@gmail.com wrote: maintaining the bst of n element in worst case will take n square time complexity ..do we have a better solution for worst case On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh sukhmeet2...@gmail.com wrote: nivedita: wts the use to maintaining BST.. if the same purpose can be fulfilled by an array .. but this can be a good method if the range of numbers is pretty large.. den making a hash count can be difficult.. On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- You received this message because you are subscribed to the Google
Re: [algogeeks] Re: Array doubt
@nivedita:ohhh :P On Sun, Jul 31, 2011 at 1:46 AM, nivedita arora vivaciousnived...@gmail.com wrote: that is why i gave BST algo first :) but rahul wanted me to give O(n) algo On Jul 31, 1:15 am, Kamakshii Aggarwal kamakshi...@gmail.com wrote: @nivedita :hashing will not work if the range of nos is high On Sun, Jul 31, 2011 at 1:40 AM, nivedita arora vivaciousnived...@gmail.com wrote: ok lets think in terms of hashmap of number and frequency we definitly have to maintain an order array . traverse original array , we check if its present in hashmap ..if not - 1)add it to hashmap and set frequency to 1 2)add it in order array if yes then increment frequency by 1. searching taking O(1) time . now traverse order array..search for corresponding freq and print this should take o(n) time...let me know if i faultered anywhere. @aditi- pls dont use just arrays..its not efficient way. On Jul 31, 12:51 am, rahul mittal rahulmitta...@gmail.com wrote: @nivedita:can u do this in o(n) time , i suppose your algorithm takes 0(nlogn) time On Sun, Jul 31, 2011 at 1:14 AM, nivedita arora vivaciousnived...@gmail.com wrote: @rahul- balanced BST can be maintained.to remove worst case ! @sukhmeet- i did not gt your method completely ..u are trying to maintain hashmap or double dimension array of number and count? @aditi- for array we will have overhead of searching if element is present or not ..in O(n) time while it will be O(logn) in BST. in array we cannot do binary search as it will not be sorted to improve search . On Jul 31, 12:31 am, rahul mittal rahulmitta...@gmail.com wrote: maintaining the bst of n element in worst case will take n square time complexity ..do we have a better solution for worst case On Sun, Jul 31, 2011 at 12:53 AM, sukhmeet singh sukhmeet2...@gmail.com wrote: nivedita: wts the use to maintaining BST.. if the same purpose can be fulfilled by an array .. but this can be a good method if the range of numbers is pretty large.. den making a hash count can be difficult.. On Sun, Jul 31, 2011 at 12:43 AM, nivedita arora vivaciousnived...@gmail.com wrote: take a BST whose node has an element of frequency .and another array which will store order of elements. for each array element search BST if node already exists increase the freq count ..other wise add that element in the order array we took and insert new node in BST. now , scan the order array find its corresponding element in BST and its frequency, print it that many times. let me know if there is any bttr method thx! On Jul 30, 11:58 pm, sukhmeet singh sukhmeet2...@gmail.com wrote: maintain a count array of all elements.. now traverse the array again and the count array .. and build the new array On Sun, Jul 31, 2011 at 12:24 AM, aditi garg aditi.garg.6...@gmail.com wrote: Q1) Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. Please provide a gud algo fr dis -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *With Regards * *RAHUL MITTAL* *3rd YEAR* *CSE* *MNNIT ALLAHABAD* -- 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] Re: Array doubt
@ Aditi: you forgot to initialize the arrays and elements. Thats why the for(i=0;ik;i++) for(j=0;jcount[i];j++) a[p++]=order[i]; was creating some fault while accessing one of the arrays. I just initialized the arrays and it worked: http://codepad.org/UO8riyjs ^^ You might want to change some lines, the output is not pretty good. -- 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/-/uVqtIVry-PUJ. 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[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 ecstasy.piy...@gmail.com wrote: Sorry for the above mistakeits not O(n) On Tue, Jul 26, 2011 at 5:29 PM, Piyush Sinha ecstasy.piy...@gmail.comwrote: Use stack On Tue, Jul 26, 2011 at 5:22 PM, Shikhar shikharko...@gmail.com wrote: Given an array of integers, for each element of the array, print the first number on the right side of the element which is smaller than it. print -1 is there is no such element. eg: 3,4,2,18,19,1,10 Ans: 2,2,1,10,10,-1,-1 O(n^2) solution is trivial. One solution could be: Insert the elements of the array in a binary search tree. The moment a node in the binary tree gets a left child, it is the element we are looking for. All the nodes in the right subtree of a node which has just received a left child can be assigned the value of the parents' left child as the first smaller element to the right. Thus, this solution is O(nlogn). Does this solution work for all possible cases of input? Is an O(n) solution possible? -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array question
@ankit: you are right...sorry about the error On Jul 26, 5:11 pm, ankit sambyal ankitsamb...@gmail.com 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, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 shikharko...@gmail.com wrote: @ankit: you are right...sorry about the error On Jul 26, 5:11 pm, ankit sambyal ankitsamb...@gmail.com 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, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array question
a crude algo,
for(i=end to start)
{
while(!stk.empty())
{
if(arr[i]arr[stk.top])
pop();
else
break;
}
if(!stk.empty())
l = arr.length-1;
else
l = stk.top;
output[i]=l-i-1;
stk.puch(i);
}
This will be O(n). Correct me I am wrong anywhere..
On Tue, Jul 26, 2011 at 5:49 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:
@Piyush, using stack i guess it can be done in O(n)
On Tue, Jul 26, 2011 at 5:42 PM, Shikhar shikharko...@gmail.com wrote:
@ankit: you are right...sorry about the error
On Jul 26, 5:11 pm, ankit sambyal ankitsamb...@gmail.com 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, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
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, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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 ankitsamb...@gmail.comwrote: @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, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
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(xtemp) print(temp); else push(x,stack) break; c) push(temp,stack) 3) After the loop in step 2 is over, pop all the elements from stack and print -1 as next element for them. -- *Piyush Sinha* *IIIT, Allahabad* *+91-7483122727* * https://www.facebook.com/profile.php?id=10655377926 NEVER SAY NEVER * -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array or matrix problems...anyone?
Try the Array Section on geeksforgeeks.org obviously without looking at the solutions. -- 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/-/XsqWbXVJ8CkJ. 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array or matrix problems...anyone?
try rotaion of matrix by 90, 180, 270 and 360 degree in both clockwise and anti clockwise directand try printing matirx in spiral order... On Sat, Jul 9, 2011 at 12:08 AM, Nitish Garg nitishgarg1...@gmail.comwrote: Try the Array Section on geeksforgeeks.org obviously without looking at the solutions. -- 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/-/XsqWbXVJ8CkJ. 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- regards Apoorve Mohan -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array size problem
due to constant folding On Jul 4, 6:54 am, Navneet Gupta navneetn...@gmail.com wrote: If you can, refer to Constants chapter in Bruce Eckel. He he smartly explained how const are different for C C++. The e-book is free to download from net. On Mon, Jul 4, 2011 at 2:50 AM, Gene gene.ress...@gmail.com wrote: Why do bicycles have 2 wheels and tricycles 3? The designers made them that way. So you're probably asking why they were designed that way. C++ came after C. In general C++ seeks to de-emphasize use of the pre- processor because macro substitution is generally considered to make maintenance more difficult. Consequently, in C you would say #define ArraySize 100 and this will work in C++, too. But C++ gives you the addtional preferred way. On Jul 3, 4:17 pm, Deoki Nandan deok...@gmail.com wrote: WHY? In C++, you can do something like const int ArraySize = 100; int Array[ArraySize]; while in ANSI C, this would be flagged as an error. -- **With Regards Deoki Nandan Vishwakarma * * -- 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, visit this group athttp://groups.google.com/group/algogeeks?hl=en. -- --Navneet -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array size problem
Why do bicycles have 2 wheels and tricycles 3? The designers made them that way. So you're probably asking why they were designed that way. C++ came after C. In general C++ seeks to de-emphasize use of the pre- processor because macro substitution is generally considered to make maintenance more difficult. Consequently, in C you would say #define ArraySize 100 and this will work in C++, too. But C++ gives you the addtional preferred way. On Jul 3, 4:17 pm, Deoki Nandan deok...@gmail.com wrote: WHY? In C++, you can do something like const int ArraySize = 100; int Array[ArraySize]; while in ANSI C, this would be flagged as an error. -- **With Regards Deoki Nandan Vishwakarma * * -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array size problem
If you can, refer to Constants chapter in Bruce Eckel. He he smartly explained how const are different for C C++. The e-book is free to download from net. On Mon, Jul 4, 2011 at 2:50 AM, Gene gene.ress...@gmail.com wrote: Why do bicycles have 2 wheels and tricycles 3? The designers made them that way. So you're probably asking why they were designed that way. C++ came after C. In general C++ seeks to de-emphasize use of the pre- processor because macro substitution is generally considered to make maintenance more difficult. Consequently, in C you would say #define ArraySize 100 and this will work in C++, too. But C++ gives you the addtional preferred way. On Jul 3, 4:17 pm, Deoki Nandan deok...@gmail.com wrote: WHY? In C++, you can do something like const int ArraySize = 100; int Array[ArraySize]; while in ANSI C, this would be flagged as an error. -- **With Regards Deoki Nandan Vishwakarma * * -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- --Navneet -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Merge Problem
@ross: I couldn't get reddy's solution. Please explain.
On Sun, Jun 5, 2011 at 10:50 PM, Deepak Jha deepak.127.0@gmail.comwrote:
the below solution should work given the input array is sorted ( I am
assuming ascending order)
void rearrangeArray(int[] a, int[] b){
int m = a.length;
int n = b.length;
int i = m - 1;
int j = 0;
while((i =0) (j = n-1)){
if(a[i] b[j]){
int temp = a[i];
a[i] = b[j];
b[j] = temp;
}
i--;
j++;
}
}
On Sat, Jun 4, 2011 at 2:29 PM, ross jagadish1...@gmail.com wrote:
Hi Rohit all,
Sorry that there was a small typo in the 'n' 'm' texts.
The example given by me is anyway the correct one.
Sravan Reddy's solution worked fine.
On Jun 4, 10:08 am, rohit rajuljain...@gmail.com wrote:
i think solution would be like this
eg:
A : 1 2 3 B: 0 1.5 4 5 9
Output:
A can contain any combination of nos 0,1,1.5
and B should contain 2 3 4 5 9 (in any order.)
this example is given by ROSS itself.
so sravanreddy solution is right , correct me if i'm wrong.
On Jun 3, 8:07 pm, bittu shashank7andr...@gmail.com wrote:
@sravanreddy...logical bugs if A is size of n B is size m from your
example assuming nm so if you want smallest m elements in A then u
only capacity of n elements didn't allocate memory so these elements
initialized by INT_MIN for m-n nodes so thatarrayA can hold m
smallest elements then what r u swapping u dude..isn't garbage
value ?? you will get at 1st step only just run it ?? in you algo
A_End=m-1(which 4th position inArraythat DNE)..?? also you have to
free memory for m-n inarrayB as it contains n largest elements .
take
A= 1,2,3 n=3
B= 0,1,4,5,9 m=5
after allocating memory toArrayA for m-n elements A will looks
likes 1 2 3 INT_Max INT_Max
now what you wants A should contains m smallest elements B have n
largest elements
so O/P should be A=1,2,3,1,0 B=INT_Max,INT_Max,4,5,9 now free
memory used by 1st elements inarrayB so that A will represent M
smallest elements B will have n Largest elements
so that above will work.
Hope I am Correct let me know if any issue with explanation
Thanks
ShashankThe Best Way To Escape From Theproblemis To Solve It
CSE,BIT Mesra
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Merge Problem
@aakash Johari:
Let a and b be the 2 arrays.
At each stage of the process, if an element of A is greater than B,
then swap the largest element of A with the smallest element of B
and adjust pointers.
A : 2 4 15 12
B : 0.2 1 33 44
Now, 20, therefore swap 0 with 12..
Every step of the process, gets in the smallest elemnt of A and swaps
it
with the largest element of B.
Hope its clear.
On Jun 6, 11:15 am, Aakash Johari aakashj@gmail.com wrote:
@ross: I couldn't get reddy's solution. Please explain.
On Sun, Jun 5, 2011 at 10:50 PM, Deepak Jha deepak.127.0@gmail.comwrote:
the below solution should work given the input array is sorted ( I am
assuming ascending order)
void rearrangeArray(int[] a, int[] b){
int m = a.length;
int n = b.length;
int i = m - 1;
int j = 0;
while((i =0) (j = n-1)){
if(a[i] b[j]){
int temp = a[i];
a[i] = b[j];
b[j] = temp;
}
i--;
j++;
}
}
On Sat, Jun 4, 2011 at 2:29 PM, ross jagadish1...@gmail.com wrote:
Hi Rohit all,
Sorry that there was a small typo in the 'n' 'm' texts.
The example given by me is anyway the correct one.
Sravan Reddy's solution worked fine.
On Jun 4, 10:08 am, rohit rajuljain...@gmail.com wrote:
i think solution would be like this
eg:
A : 1 2 3 B: 0 1.5 4 5 9
Output:
A can contain any combination of nos 0,1,1.5
and B should contain 2 3 4 5 9 (in any order.)
this example is given by ROSS itself.
so sravanreddy solution is right , correct me if i'm wrong.
On Jun 3, 8:07 pm, bittu shashank7andr...@gmail.com wrote:
@sravanreddy...logical bugs if A is size of n B is size m from your
example assuming nm so if you want smallest m elements in A then u
only capacity of n elements didn't allocate memory so these elements
initialized by INT_MIN for m-n nodes so thatarrayA can hold m
smallest elements then what r u swapping u dude..isn't garbage
value ?? you will get at 1st step only just run it ?? in you algo
A_End=m-1(which 4th position inArraythat DNE)..?? also you have to
free memory for m-n inarrayB as it contains n largest elements .
take
A= 1,2,3 n=3
B= 0,1,4,5,9 m=5
after allocating memory toArrayA for m-n elements A will looks
likes 1 2 3 INT_Max INT_Max
now what you wants A should contains m smallest elements B have n
largest elements
so O/P should be A=1,2,3,1,0 B=INT_Max,INT_Max,4,5,9 now free
memory used by 1st elements inarrayB so that A will represent M
smallest elements B will have n Largest elements
so that above will work.
Hope I am Correct let me know if any issue with explanation
Thanks
ShashankThe Best Way To Escape From Theproblemis To Solve It
CSE,BIT Mesra
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Merge Problem
the below solution should work given the input array is sorted ( I am
assuming ascending order)
void rearrangeArray(int[] a, int[] b){
int m = a.length;
int n = b.length;
int i = m - 1;
int j = 0;
while((i =0) (j = n-1)){
if(a[i] b[j]){
int temp = a[i];
a[i] = b[j];
b[j] = temp;
}
i--;
j++;
}
}
On Sat, Jun 4, 2011 at 2:29 PM, ross jagadish1...@gmail.com wrote:
Hi Rohit all,
Sorry that there was a small typo in the 'n' 'm' texts.
The example given by me is anyway the correct one.
Sravan Reddy's solution worked fine.
On Jun 4, 10:08 am, rohit rajuljain...@gmail.com wrote:
i think solution would be like this
eg:
A : 1 2 3 B: 0 1.5 4 5 9
Output:
A can contain any combination of nos 0,1,1.5
and B should contain 2 3 4 5 9 (in any order.)
this example is given by ROSS itself.
so sravanreddy solution is right , correct me if i'm wrong.
On Jun 3, 8:07 pm, bittu shashank7andr...@gmail.com wrote:
@sravanreddy...logical bugs if A is size of n B is size m from your
example assuming nm so if you want smallest m elements in A then u
only capacity of n elements didn't allocate memory so these elements
initialized by INT_MIN for m-n nodes so thatarrayA can hold m
smallest elements then what r u swapping u dude..isn't garbage
value ?? you will get at 1st step only just run it ?? in you algo
A_End=m-1(which 4th position inArraythat DNE)..?? also you have to
free memory for m-n inarrayB as it contains n largest elements .
take
A= 1,2,3 n=3
B= 0,1,4,5,9 m=5
after allocating memory toArrayA for m-n elements A will looks
likes 1 2 3 INT_Max INT_Max
now what you wants A should contains m smallest elements B have n
largest elements
so O/P should be A=1,2,3,1,0 B=INT_Max,INT_Max,4,5,9 now free
memory used by 1st elements inarrayB so that A will represent M
smallest elements B will have n Largest elements
so that above will work.
Hope I am Correct let me know if any issue with explanation
Thanks
ShashankThe Best Way To Escape From Theproblemis To Solve It
CSE,BIT Mesra
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Merge Problem
i think solution would be like this eg: A : 1 2 3 B: 0 1.5 4 5 9 Output: A can contain any combination of nos 0,1,1.5 and B should contain 2 3 4 5 9 (in any order.) this example is given by ROSS itself. so sravanreddy solution is right , correct me if i'm wrong. On Jun 3, 8:07 pm, bittu shashank7andr...@gmail.com wrote: @sravanreddy...logical bugs if A is size of n B is size m from your example assuming nm so if you want smallest m elements in A then u only capacity of n elements didn't allocate memory so these elements initialized by INT_MIN for m-n nodes so thatarrayA can hold m smallest elements then what r u swapping u dude..isn't garbage value ?? you will get at 1st step only just run it ?? in you algo A_End=m-1(which 4th position inArraythat DNE)..?? also you have to free memory for m-n inarrayB as it contains n largest elements . take A= 1,2,3 n=3 B= 0,1,4,5,9 m=5 after allocating memory toArrayA for m-n elements A will looks likes 1 2 3 INT_Max INT_Max now what you wants A should contains m smallest elements B have n largest elements so O/P should be A=1,2,3,1,0 B=INT_Max,INT_Max,4,5,9 now free memory used by 1st elements inarrayB so that A will represent M smallest elements B will have n Largest elements so that above will work. Hope I am Correct let me know if any issue with explanation Thanks ShashankThe Best Way To Escape From Theproblemis To Solve It CSE,BIT Mesra -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Merge Problem
Hi Rohit all, Sorry that there was a small typo in the 'n' 'm' texts. The example given by me is anyway the correct one. Sravan Reddy's solution worked fine. On Jun 4, 10:08 am, rohit rajuljain...@gmail.com wrote: i think solution would be like this eg: A : 1 2 3 B: 0 1.5 4 5 9 Output: A can contain any combination of nos 0,1,1.5 and B should contain 2 3 4 5 9 (in any order.) this example is given by ROSS itself. so sravanreddy solution is right , correct me if i'm wrong. On Jun 3, 8:07 pm, bittu shashank7andr...@gmail.com wrote: @sravanreddy...logical bugs if A is size of n B is size m from your example assuming nm so if you want smallest m elements in A then u only capacity of n elements didn't allocate memory so these elements initialized by INT_MIN for m-n nodes so thatarrayA can hold m smallest elements then what r u swapping u dude..isn't garbage value ?? you will get at 1st step only just run it ?? in you algo A_End=m-1(which 4th position inArraythat DNE)..?? also you have to free memory for m-n inarrayB as it contains n largest elements . take A= 1,2,3 n=3 B= 0,1,4,5,9 m=5 after allocating memory toArrayA for m-n elements A will looks likes 1 2 3 INT_Max INT_Max now what you wants A should contains m smallest elements B have n largest elements so O/P should be A=1,2,3,1,0 B=INT_Max,INT_Max,4,5,9 now free memory used by 1st elements inarrayB so that A will represent M smallest elements B will have n Largest elements so that above will work. Hope I am Correct let me know if any issue with explanation Thanks ShashankThe Best Way To Escape From Theproblemis To Solve It CSE,BIT Mesra -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Merge Problem
@sravanreddy...logical bugs if A is size of n B is size m from your example assuming nm so if you want smallest m elements in A then u only capacity of n elements didn't allocate memory so these elements initialized by INT_MIN for m-n nodes so that array A can hold m smallest elements then what r u swapping u dude..isn't garbage value ?? you will get at 1st step only just run it ?? in you algo A_End=m-1(which 4th position in Array that DNE)..?? also you have to free memory for m-n in array B as it contains n largest elements . take A= 1,2,3 n=3 B= 0,1,4,5,9 m=5 after allocating memory to Array A for m-n elements A will looks likes 1 2 3 INT_Max INT_Max now what you wants A should contains m smallest elements B have n largest elements so O/P should be A=1,2,3,1,0 B=INT_Max,INT_Max,4,5,9 now free memory used by 1st elements in array B so that A will represent M smallest elements B will have n Largest elements so that above will work. Hope I am Correct let me know if any issue with explanation Thanks ShashankThe Best Way To Escape From The problem is To Solve It CSE,BIT Mesra -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Merge Problem
Please try this solution. And tell if it fails at any case. If it works
fine, I will tell the logic.
#include stdio.h
#include stdlib.h
void merge(int *a, int m, int *b, int n)
{
int i, j, k;
int t;
i = j = 0;
k = -1;
while ( i m a[i] b[j] ) {
i++;
}
while ( i m j n ) {
if ( k == -1 b[j] a[i] ) {
t = a[i]; a[i] = b[j]; b[j] = t;
k = j;
j++;
i++;
} else if ( b[j] b[k] ) {
t = a[i]; a[i] = b[j]; b[j] = t;
j++;
i++;
} else {
t = a[i]; a[i] = b[k]; b[k] = t;
i++;
}
}
}
int main()
{
int m, n;
int *a, *b;
int i;
scanf (%d%d, m, n);
a = (int*) malloc(sizeof(int) * m);
b = (int*) malloc(sizeof(int) * n);
for ( i = 0; i m; i++ )
scanf (%d, a + i);
for ( i = 0; i n; i++ )
scanf (%d, b + i);
merge (a, m, b, n);
printf (After Merge Operation : \n);
printf (1st Array : );
for ( i = 0; i m; i++ ) {
printf (%d , a[i]);
}
printf (\n2nd Array : );
for ( i = 0; i n; i++ ) {
printf (%d , b[i]);
}
return 0;
}
On Fri, Jun 3, 2011 at 8:07 AM, bittu shashank7andr...@gmail.com wrote:
@sravanreddy...logical bugs if A is size of n B is size m from your
example assuming nm so if you want smallest m elements in A then u
only capacity of n elements didn't allocate memory so these elements
initialized by INT_MIN for m-n nodes so that array A can hold m
smallest elements then what r u swapping u dude..isn't garbage
value ?? you will get at 1st step only just run it ?? in you algo
A_End=m-1(which 4th position in Array that DNE)..?? also you have to
free memory for m-n in array B as it contains n largest elements .
take
A= 1,2,3 n=3
B= 0,1,4,5,9 m=5
after allocating memory to Array A for m-n elements A will looks
likes 1 2 3 INT_Max INT_Max
now what you wants A should contains m smallest elements B have n
largest elements
so O/P should be A=1,2,3,1,0 B=INT_Max,INT_Max,4,5,9 now free
memory used by 1st elements in array B so that A will represent M
smallest elements B will have n Largest elements
so that above will work.
Hope I am Correct let me know if any issue with explanation
Thanks
ShashankThe Best Way To Escape From The problem is To Solve It
CSE,BIT Mesra
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Merge Problem
it can be done in O(m) . Use something like binary search .
code is here ...
#includestdio.h
void splitMN(int a[],int m , int b[], int n){
int al = 0 , bl = 0 ;
int ah = m-1 , bh = n-1 ;
int ai = (ah+al+1)/2;
int bi = (bh+bl+1)/2;
while(ai+bi!=m){
printf(Enter ai = %d, bi = %d\n ,ai,bi);
if(ai+bi m){
if(a[ai] b[bi]){
al = ai ;
if(al == ai) break;
ai = (ah+al+1)/2;
}else{
bl = bi ;
if(bh == bi) break;
bi = (bh+bl+1)/2;
}
}else{
if(a[ai] b[bi]){
ah = ai ;
if(ah == ai) break;
ai = (ah+al+1)/2;
}else{
bh = bi ;
if(bh == bi) break;
bi = (bh+bl+1)/2;
}
}
}
bi = 0 ;
ai ;
while(ai m){
a[ai] = a[ai]^b[bi]^(b[bi] = a[ai]);
ai++ ; bi++ ;
}
}
int main(){
int m , n ;
printf(Enter m , n : );
scanf(%d%d,m,n);
int a[m] , b[n] ;
int i ;
for(i = 0 ; i m ; i++)
scanf(%d,a[i]);
for(i = 0 ; i n ; i++)
scanf(%d,b[i]);
printf(Enter m , n : );
splitMN(a,m,b,n);
for(i = 0 ; i m ; i++)
printf(%d\t,a[i]);
printf(\n);
for(i = 0 ; i n ; i++)
printf(%d\t,b[i]);
printf(\n);
}
On Sat, Jun 4, 2011 at 4:03 AM, Aakash Johari aakashj@gmail.com wrote:
Please try this solution. And tell if it fails at any case. If it works
fine, I will tell the logic.
#include stdio.h
#include stdlib.h
void merge(int *a, int m, int *b, int n)
{
int i, j, k;
int t;
i = j = 0;
k = -1;
while ( i m a[i] b[j] ) {
i++;
}
while ( i m j n ) {
if ( k == -1 b[j] a[i] ) {
t = a[i]; a[i] = b[j]; b[j] = t;
k = j;
j++;
i++;
} else if ( b[j] b[k] ) {
t = a[i]; a[i] = b[j]; b[j] = t;
j++;
i++;
} else {
t = a[i]; a[i] = b[k]; b[k] = t;
i++;
}
}
}
int main()
{
int m, n;
int *a, *b;
int i;
scanf (%d%d, m, n);
a = (int*) malloc(sizeof(int) * m);
b = (int*) malloc(sizeof(int) * n);
for ( i = 0; i m; i++ )
scanf (%d, a + i);
for ( i = 0; i n; i++ )
scanf (%d, b + i);
merge (a, m, b, n);
printf (After Merge Operation : \n);
printf (1st Array : );
for ( i = 0; i m; i++ ) {
printf (%d , a[i]);
}
printf (\n2nd Array : );
for ( i = 0; i n; i++ ) {
printf (%d , b[i]);
}
return 0;
}
On Fri, Jun 3, 2011 at 8:07 AM, bittu shashank7andr...@gmail.com wrote:
@sravanreddy...logical bugs if A is size of n B is size m from your
example assuming nm so if you want smallest m elements in A then u
only capacity of n elements didn't allocate memory so these elements
initialized by INT_MIN for m-n nodes so that array A can hold m
smallest elements then what r u swapping u dude..isn't garbage
value ?? you will get at 1st step only just run it ?? in you algo
A_End=m-1(which 4th position in Array that DNE)..?? also you have to
free memory for m-n in array B as it contains n largest elements .
take
A= 1,2,3 n=3
B= 0,1,4,5,9 m=5
after allocating memory to Array A for m-n elements A will looks
likes 1 2 3 INT_Max INT_Max
now what you wants A should contains m smallest elements B have n
largest elements
so O/P should be A=1,2,3,1,0 B=INT_Max,INT_Max,4,5,9 now free
memory used by 1st elements in array B so that A will represent M
smallest elements B will have n Largest elements
so that above will work.
Hope I am Correct let me know if any issue with explanation
Thanks
ShashankThe Best Way To Escape From The problem is To Solve It
CSE,BIT Mesra
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
-Aakash Johari
(IIIT Allahabad)
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*With Regards :*
Ravinder Kumar
B.Tech 3rd Year
Computer Science and Engineering
MNNIT Allahabad
--
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
[algogeeks] Re: Array Merge Problem
Maintain a pointer A_end = m-1;
doing a comparision something similar to merge sort
int i=0;j=0;
while (i m){
if (a[i] b[j])
i++;
else{
swap(a[A_end],b[j])
A_end --;
j++;
}
}
This runs in O(m) time and no extra space, also the sort order is not
guarenteed.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Merge Problem
@sravanreddy:
Hey, Nice Solution :) cool!
On May 29, 7:44 am, sravanreddy001 sravanreddy...@gmail.com wrote:
Maintain a pointer A_end = m-1;
doing a comparision something similar to merge sort
int i=0;j=0;
while (i m){
if (a[i] b[j])
i++;
else{
swap(a[A_end],b[j])
A_end --;
j++;
}
}
This runs in O(m) time and no extra space, also the sort order is not
guarenteed.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Merge Problem
@sravanreddy: it won't work. Try 3,91,9 and 90,1,8,2,5 . correct me
if i m wrong.
Thanks,
Ankit Sambyal
On Sat, May 28, 2011 at 9:16 PM, ross jagadish1...@gmail.com wrote:
@sravanreddy:
Hey, Nice Solution :) cool!
On May 29, 7:44 am, sravanreddy001 sravanreddy...@gmail.com wrote:
Maintain a pointer A_end = m-1;
doing a comparision something similar to merge sort
int i=0;j=0;
while (i m){
if (a[i] b[j])
i++;
else{
swap(a[A_end],b[j])
A_end --;
j++;
}
}
This runs in O(m) time and no extra space, also the sort order is not
guarenteed.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Merge Problem
@Ankit, The input should be 2 sorted arrays
Thanks,
Immanuel
On Sun, May 29, 2011 at 10:48 AM, ankit sambyal ankitsamb...@gmail.comwrote:
@sravanreddy: it won't work. Try 3,91,9 and 90,1,8,2,5 . correct
me if i m wrong.
Thanks,
Ankit Sambyal
On Sat, May 28, 2011 at 9:16 PM, ross jagadish1...@gmail.com wrote:
@sravanreddy:
Hey, Nice Solution :) cool!
On May 29, 7:44 am, sravanreddy001 sravanreddy...@gmail.com wrote:
Maintain a pointer A_end = m-1;
doing a comparision something similar to merge sort
int i=0;j=0;
while (i m){
if (a[i] b[j])
i++;
else{
swap(a[A_end],b[j])
A_end --;
j++;
}
}
This runs in O(m) time and no extra space, also the sort order is not
guarenteed.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Merge Problem
Oh I didn't read the question properly, Thanks for pointing out...
On Sat, May 28, 2011 at 10:28 PM, immanuel kingston
kingston.imman...@gmail.com wrote:
@Ankit, The input should be 2 sorted arrays
Thanks,
Immanuel
On Sun, May 29, 2011 at 10:48 AM, ankit sambyal ankitsamb...@gmail.comwrote:
@sravanreddy: it won't work. Try 3,91,9 and 90,1,8,2,5 . correct
me if i m wrong.
Thanks,
Ankit Sambyal
On Sat, May 28, 2011 at 9:16 PM, ross jagadish1...@gmail.com wrote:
@sravanreddy:
Hey, Nice Solution :) cool!
On May 29, 7:44 am, sravanreddy001 sravanreddy...@gmail.com wrote:
Maintain a pointer A_end = m-1;
doing a comparision something similar to merge sort
int i=0;j=0;
while (i m){
if (a[i] b[j])
i++;
else{
swap(a[A_end],b[j])
A_end --;
j++;
}
}
This runs in O(m) time and no extra space, also the sort order is not
guarenteed.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array problem
@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 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 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 J goes out of bound and we try to reference C[j]. Nywayz..thnx for the solution and algo !! -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* 363.gif 1KViewDownload 360.gif 1KViewDownload -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array problem
@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 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 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 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 J goes out of bound and we try to reference C[j]. Nywayz..thnx for the solution and algo !! -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926* 363.gif 1KViewDownload 360.gif 1KViewDownload -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- *Piyush Sinha* *IIIT, Allahabad* *+91-8792136657* *+91-7483122727* *https://www.facebook.com/profile.php?id=10655377926 * -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array , Number Missing or Duplicate ..
@Dave: Can you please explain it? I am not getting you. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array(amazon microsoft)
@all after 32 Message Discussion I know Everyone is looking for O(N)
solution well it seems odd how we can search an element in a O(m*n)
matrix in O(n) but answer of this question is given already in the
question that all row column are sorted so why O(n) solution
exist it really matters play very important role if one will
think out of boxwell i think inside the box.not outside...lol
here we go for O(n) Clean ,Elegant ,Simple Best Solution as i
think for this problem
boolean FindElem(int[][] mat, int elem, int M, int N)
{
int row = 0;
int col = N-1;
while (row M col = 0)
{
if (mat[row][col] == elem)//done
{
return true;
}
else if (mat[row][col] elem) //obvious as all call are sorted
because all value in col[j] col[j+1] given test below program for
searching element 2
{
col--;
}
else // its all same as all row are sorted so if element not found
in a[i][] then got a[i+1][] row because all all value in row[i]
row[i+1] its given
{ //
test below program for searching element 9
row++;
}
}
return false;
}
Working Code https://ideone.com/64HJg
If u found for any counter test case its failing then plz let me know
still f any has doubt i will try to explain my best
Thanks Regards
Shashank Mani the Best way to escape from The Problem is Solve 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
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array , Number Missing or Duplicate ..
@Mannu. You said that the complexity of the counting sort is O(n). Doesn't the complexity depends on the data? In particular, I'm asking you to explain more completely how you obtain O(n) complexity with the counting sort on a particular data set where the range of the data depends on n. Can you do it? Or were you too cavalier in throwing out the counting sort and O(n)? Dave On Mar 1, 10:20 am, MANNU manishkr2...@gmail.com wrote: @Dave: Can you please explain it? I am not getting you. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array , Number Missing or Duplicate ..
I can think of 2 methods if Hashing is not allowed. 1. Plain comparison of every element with an other element, which takes O(n2) 2. We can sort the array, and the best we could achieve is O(nlogn) after that use simple comparision, like the code here : http://codepad.org/RtRbnyAN; Overall we can optimize it best to O(n) http://codepad.org/RtRbnyAN Best Regards Abhijit On Sun, Feb 27, 2011 at 7:15 PM, Dave dave_and_da...@juno.com wrote: If hashing is disallowed, then I think the best method is to sort the data and check for consecutive triplicates. O(n log n). Dave On Feb 27, 6:35 am, bittu shashank7andr...@gmail.com wrote: @Gaurav Hey I forgot to say Hashing is not allowed sum thing other then this better solution @radha i don't think ur method works here chk out ur methodhttp:// codepad.org/oTDNSoeu Thanks Shashank -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- 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, visit this group at http://groups.google.com/group/algogeeks?hl=en.
