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 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.
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.
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.
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.
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 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.
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.
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 problem
This problem is close than this: http://uva.onlinejudge.org/external/103/10327.html I found this: http://en.wikipedia.org/wiki/Pancake_sorting Wladimir Araujo Tavares *Federal University of Ceará * On Fri, Feb 11, 2011 at 10:57 AM, juver++ avpostni...@gmail.com wrote: @jalaj please ignore my prevoius post, misread the problem. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to 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
@jalaj please ignore my prevoius post, misread the problem. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: array problem
@ dave assume reverse also O(1) @juver will you elaborate a bit dude On Thu, Feb 10, 2011 at 8:21 PM, juver++ avpostni...@gmail.com wrote: Cartesian tree will do. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, 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, *Jalaj Jaiswal* (+919019947895) Software developer, Cisco Systems B.Tech 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 Problem
can you please explain more in detail the logic for XORing the index. On 22.08.2010 07:53, UMarius wrote: @Nikhil : I considered the array to be a linked list. xoring the indexes helps when you don't know how many elements you have. Marius. On Aug 22, 5:04 am, Nikhil Agarwalnikhil.bhoja...@gmail.com wrote: @marius Why are you xorring the indexes along with nos.?any special reason? On Sun, Aug 22, 2010 at 7:19 AM, UMariusmar...@aseara.ro wrote: @Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1} the output is correct. Maybe I didn't explain the steps correctly. This is the code: for(int i = 0 ; i arr1.Length ; i++) { arr1XOR ^= arr1[i]; arr1XOR ^= i; arr1SUM += arr1[i]; arr1MUL *= arr1[i]; } for (int i = 0; i arr2.Length; i++) { arr2XOR ^= arr2[i]; arr2XOR ^= i; arr2SUM += arr2[i]; arr2MUL *= arr2[i]; } if(arr1XOR == arr2XOR arr1SUM == arr2SUM arr1MUL == arr2MUL) { //SAME VALUES - IDENTICAL ARRAYS } else { //NOT IDENTICAL } Please correct me if I'm wrong. Marius. On Aug 22, 3:45 am, Davedave_and_da...@juno.com wrote: @UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the original problem, you see that the question is not whether the arrays are identical (which is easily determined by simply comparing them element-by-element in O(n)), but whether they contain the same values, possibly in a different order. Dave On Aug 21, 11:01 am, UMariusmar...@aseara.ro wrote: What about this? 1. xor all elements of each array and their corresponding indexes sum all the elements of each array mul all elements of each array 2. if all results are the same then the arrays are identical Nice to meet you all, I just joined and this is my first post :) ... Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space?- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
a={1,2,2,3,4} b={1,2,3,3,4} in this case??? elements are not equal but they certainly consist equal set of integers(1,2,3,4) which is what question says. On Sun, Aug 22, 2010 at 7:53 AM, UMarius mar...@aseara.ro wrote: @Nikhil : I considered the array to be a linked list. xoring the indexes helps when you don't know how many elements you have. Marius. On Aug 22, 5:04 am, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: @marius Why are you xorring the indexes along with nos.?any special reason? On Sun, Aug 22, 2010 at 7:19 AM, UMarius mar...@aseara.ro wrote: @Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1} the output is correct. Maybe I didn't explain the steps correctly. This is the code: for(int i = 0 ; i arr1.Length ; i++) { arr1XOR ^= arr1[i]; arr1XOR ^= i; arr1SUM += arr1[i]; arr1MUL *= arr1[i]; } for (int i = 0; i arr2.Length; i++) { arr2XOR ^= arr2[i]; arr2XOR ^= i; arr2SUM += arr2[i]; arr2MUL *= arr2[i]; } if(arr1XOR == arr2XOR arr1SUM == arr2SUM arr1MUL == arr2MUL) { //SAME VALUES - IDENTICAL ARRAYS } else { //NOT IDENTICAL } Please correct me if I'm wrong. Marius. On Aug 22, 3:45 am, Dave dave_and_da...@juno.com wrote: @UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the original problem, you see that the question is not whether the arrays are identical (which is easily determined by simply comparing them element-by-element in O(n)), but whether they contain the same values, possibly in a different order. Dave On Aug 21, 11:01 am, UMarius mar...@aseara.ro wrote: What about this? 1. xor all elements of each array and their corresponding indexes sum all the elements of each array mul all elements of each array 2. if all results are the same then the arrays are identical Nice to meet you all, I just joined and this is my first post :) ... Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space?- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,Indiahttp://tech-nikk.blogspot.comhttp:// beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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
Its easier to look at a property of numbers. It will be interesting to evaluate/prove if two different arrays have same value for sum of elements and sum of squares of the elements. On Fri, Aug 20, 2010 at 9:38 AM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: Check this new algo: plz provide counter eg.(if any) step 1 : count the no. of elements,0s,1s,2s,3s in arr1 and arry2.if yes proceed to step 2 else print fail step2: if(sum of the elements and product of the non zero elements are same in both arrays ) print arrays are same else print fail. On Fri, Aug 20, 2010 at 4:26 AM, Dave dave_and_da...@juno.com wrote: @Saikat: Rather than challenging everyone to keep coming up with counterexamples, please provide a rationale as to why an algorithm such as this should work. It looks as if you have two equations in 2N unknowns and are trying to assert that the only solution is A_1 = B_1, A_2 = B_2, etc. (where I have assumed that each array is sorted). Usually, it takes 2N equations to determine 2N unknowns, although other information about the solutions can lessen that number in certain circumstances. At least if you are going to propose something, do so only after you have tested it on all of the combinations of up to four numbers between -5 and 5. Dave On Aug 19, 11:52 am, Saikat Debnath saikat@gmail.com wrote: 1. Add sum of squares of all numbers in respective groups, if equal goto step 2. 2. XOR all elements of both groups, (if==0) elements are same. On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote: @Nikhil Jindal: What you say is true for 2 numbers, but not for more than 2. 1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36. Dave On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote: Nikhil's algo is correct if the following is always true: Given: x + y = S, x * y = M and x' + y' = S', x' * y' = M' If: S' = S and M' = M, then x = x' and y = y' i.e for given sum and product, the elements are unique. On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . S1=0;S2=0; M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) M1!=M2 there fore it is correct. Code: bool check_arrays(vectorint v1,vectorint v2){ if(v1.size()!=v2.size()) return 0; if(v1.size()==0v2.size()==0) return 1; int sum,product1,product2; sum=0;product1=1;product2=1; for(int i=0;iv1.size();i++){ sum+=v1[i]; sum-=v2[i]; if(v1[i]!=0) product1*=v1[i]; if(v2[i]!=0) product2*=v2[i]; } if(sum==0(product1==product2)) return 1; return 0; } On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote: @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B = (0,2,-3). I was thinking ones-complement arithmetic instead of twos- complement. Dave On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote: @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2). Dave On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote: add one more thing to the solution suggested by nikhil i.e;count the number of elements in array 1 and number of elements in array2 if these two values are equal then after follow the algo proposed by nikhil agarwal.. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com algogeeks%2bunsubscr...@googlegroups.com
Re: [algogeeks] Re: Array Problem
@Nikhil Agarwal: You cannot take extra memory and neither the range of numbers is specified. Counting will not be a viable option. On Fri, Aug 20, 2010 at 9:38 AM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: Check this new algo: plz provide counter eg.(if any) step 1 : count the no. of elements,0s,1s,2s,3s in arr1 and arry2.if yes proceed to step 2 else print fail step2: if(sum of the elements and product of the non zero elements are same in both arrays ) print arrays are same else print fail. On Fri, Aug 20, 2010 at 4:26 AM, Dave dave_and_da...@juno.com wrote: @Saikat: Rather than challenging everyone to keep coming up with counterexamples, please provide a rationale as to why an algorithm such as this should work. It looks as if you have two equations in 2N unknowns and are trying to assert that the only solution is A_1 = B_1, A_2 = B_2, etc. (where I have assumed that each array is sorted). Usually, it takes 2N equations to determine 2N unknowns, although other information about the solutions can lessen that number in certain circumstances. At least if you are going to propose something, do so only after you have tested it on all of the combinations of up to four numbers between -5 and 5. Dave On Aug 19, 11:52 am, Saikat Debnath saikat@gmail.com wrote: 1. Add sum of squares of all numbers in respective groups, if equal goto step 2. 2. XOR all elements of both groups, (if==0) elements are same. On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote: @Nikhil Jindal: What you say is true for 2 numbers, but not for more than 2. 1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36. Dave On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote: Nikhil's algo is correct if the following is always true: Given: x + y = S, x * y = M and x' + y' = S', x' * y' = M' If: S' = S and M' = M, then x = x' and y = y' i.e for given sum and product, the elements are unique. On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . S1=0;S2=0; M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) M1!=M2 there fore it is correct. Code: bool check_arrays(vectorint v1,vectorint v2){ if(v1.size()!=v2.size()) return 0; if(v1.size()==0v2.size()==0) return 1; int sum,product1,product2; sum=0;product1=1;product2=1; for(int i=0;iv1.size();i++){ sum+=v1[i]; sum-=v2[i]; if(v1[i]!=0) product1*=v1[i]; if(v2[i]!=0) product2*=v2[i]; } if(sum==0(product1==product2)) return 1; return 0; } On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote: @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B = (0,2,-3). I was thinking ones-complement arithmetic instead of twos- complement. Dave On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote: @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2). Dave On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote: add one more thing to the solution suggested by nikhil i.e;count the number of elements in array 1 and number of elements in array2 if these two values are equal then after follow the algo proposed by nikhil agarwal.. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group
Re: [algogeeks] Re: Array Problem
@marius Why are you xorring the indexes along with nos.?any special reason? On Sun, Aug 22, 2010 at 7:19 AM, UMarius mar...@aseara.ro wrote: @Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1} the output is correct. Maybe I didn't explain the steps correctly. This is the code: for(int i = 0 ; i arr1.Length ; i++) { arr1XOR ^= arr1[i]; arr1XOR ^= i; arr1SUM += arr1[i]; arr1MUL *= arr1[i]; } for (int i = 0; i arr2.Length; i++) { arr2XOR ^= arr2[i]; arr2XOR ^= i; arr2SUM += arr2[i]; arr2MUL *= arr2[i]; } if(arr1XOR == arr2XOR arr1SUM == arr2SUM arr1MUL == arr2MUL) { //SAME VALUES - IDENTICAL ARRAYS } else { //NOT IDENTICAL } Please correct me if I'm wrong. Marius. On Aug 22, 3:45 am, Dave dave_and_da...@juno.com wrote: @UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the original problem, you see that the question is not whether the arrays are identical (which is easily determined by simply comparing them element-by-element in O(n)), but whether they contain the same values, possibly in a different order. Dave On Aug 21, 11:01 am, UMarius mar...@aseara.ro wrote: What about this? 1. xor all elements of each array and their corresponding indexes sum all the elements of each array mul all elements of each array 2. if all results are the same then the arrays are identical Nice to meet you all, I just joined and this is my first post :) ... Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space?- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
Nikhil's algo is correct if the following is always true: Given: x + y = S, x * y = M and x' + y' = S', x' * y' = M' If: S' = S and M' = M, then x = x' and y = y' i.e for given sum and product, the elements are unique. On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . S1=0;S2=0; M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) M1!=M2 there fore it is correct. Code: bool check_arrays(vectorint v1,vectorint v2){ if(v1.size()!=v2.size()) return 0; if(v1.size()==0v2.size()==0) return 1; int sum,product1,product2; sum=0;product1=1;product2=1; for(int i=0;iv1.size();i++){ sum+=v1[i]; sum-=v2[i]; if(v1[i]!=0) product1*=v1[i]; if(v2[i]!=0) product2*=v2[i]; } if(sum==0(product1==product2)) return 1; return 0; } On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote: @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B = (0,2,-3). I was thinking ones-complement arithmetic instead of twos- complement. Dave On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote: @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2). Dave On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote: add one more thing to the solution suggested by nikhil i.e;count the number of elements in array 1 and number of elements in array2 if these two values are equal then after follow the algo proposed by nikhil agarwal.. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text - - Show quoted text -- 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to
Re: [algogeeks] Re: Array Problem
@saikat ur algo fails with the test case a1=-2,-2 and a2=2,2 On Thu, Aug 19, 2010 at 10:22 PM, Saikat Debnath saikat@gmail.comwrote: 1. Add sum of squares of all numbers in respective groups, if equal goto step 2. 2. XOR all elements of both groups, (if==0) elements are same. On Aug 19, 9:21 pm, Dave dave_and_da...@juno.com wrote: @Nikhil Jindal: What you say is true for 2 numbers, but not for more than 2. 1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36. Dave On Aug 19, 6:00 am, Nikhil Jindal fundoon...@yahoo.co.in wrote: Nikhil's algo is correct if the following is always true: Given: x + y = S, x * y = M and x' + y' = S', x' * y' = M' If: S' = S and M' = M, then x = x' and y = y' i.e for given sum and product, the elements are unique. On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal nikhil.bhoja...@gmail.comwrote: @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} . S1=0;S2=0; M1=-1 and M2 =-4 (excluding 0 multiplication which i had corrected) M1!=M2 there fore it is correct. Code: bool check_arrays(vectorint v1,vectorint v2){ if(v1.size()!=v2.size()) return 0; if(v1.size()==0v2.size()==0) return 1; int sum,product1,product2; sum=0;product1=1;product2=1; for(int i=0;iv1.size();i++){ sum+=v1[i]; sum-=v2[i]; if(v1[i]!=0) product1*=v1[i]; if(v2[i]!=0) product2*=v2[i]; } if(sum==0(product1==product2)) return 1; return 0; } On Thu, Aug 19, 2010 at 11:26 AM, Dave dave_and_da...@juno.com wrote: @Srinivas, Make that: Your algorithm seems to fail on A = {0,1,-2), B = (0,2,-3). I was thinking ones-complement arithmetic instead of twos- complement. Dave On Aug 18, 11:59 pm, Dave dave_and_da...@juno.com wrote: @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B = (0,2,-2). Dave On Aug 18, 10:53 pm, srinivas reddy srinivaseev...@gmail.com wrote: add one more thing to the solution suggested by nikhil i.e;count the number of elements in array 1 and number of elements in array2 if these two values are equal then after follow the algo proposed by nikhil agarwal.. On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Chonku: Your algo seems to fail with following input. Arr1[]= {1,6} Arr2[]={7} On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan raiskhan.i...@gmail.com wrote: @Nikhil: Your algo seems to fail with following input. What do you say? Arr1[]= {1,2,3} Arr2[]={6} On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal nikhil.bhoja...@gmail.com wrote: Sum all the elements of both the arrays..let it be s1 and s2 Multiply the elements and call as m1 and m2 if(s1==s2) (m1==m2) return 1;else return 0; O(n) On Tue, Aug 17, 2010 at 11:33 PM, amit amitjaspal...@gmail.com wrote: Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com algogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Thanks Regards Nikhil Agarwal Senior Undergraduate Computer Science Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups .com
Re: [algogeeks] Re: Array Problem
i meant make an array of indexes.. index[]={0,1...,n-1} now sort the original array and move the elements of index array accordingly.. now follow modelling expert's algo nd while taking largest-smallest check if the index of largest in index array index of smallest in index array. On 13 June 2010 08:38, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: @Satya: I don't think what you have coded will work.. though i have not read the whole code. Don't you think a simple divide and conquer scheme would work...(almost like the mergesort) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Sat, Jun 12, 2010 at 9:06 PM, Satya satya...@gmail.com wrote: This problem seems to be finding the maxdiff in an array. int maxdiff ( int A[], int n ) { // write your code here int max_diff = A[1] - A[0]; int min_element = A[0]; int i; for(i = 1; i n; i++) { if(A[i] - min_element max_diff) max_diff = A[i] - min_element; if(A[i] min_element) min_element = A[i]; } if(max_diff 0) max_diff = 0; return max_diff; } . Satya On Sat, Jun 12, 2010 at 3:18 PM, divya jain sweetdivya@gmail.comwrote: i think we need to maintain an array of index as well such that while subtracting smallest element from largest element of sorted array we need to check if index of largest is greater than index of smallest. if no..then this is not the solution.. On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.comwrote: Let's say array A , 1 till n s_index = 1; e_index = n ; start = A[s_index] ; end = A[e_index]; result = 0; //! j - i if ( *end *start ){ result = index(end) - index(start) ( only of its greater than previous value of result ) break ; }else{ end-- ; //! till you reach start } now increment start , and repeat the process but only from A[n] till A[++result] , going further down is not required now. Average time o(n^2) Worst case : let's say we have descending array of ints, theno(n^2) Please suggest improvements On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote: given an array A of n elements. for indexes j , i such that ji maximize( j - i ) such that A[j] - A [ i ] 0 . Any Algorithm less than O(n^2) would do. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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
@BALARUKESH i think the problem is to maximize the diffrence j-i according to condition and in your solution j can be less than i. This problem can be solved by sorting the array first, then taking diffrence. this solution is done in O(nlogn). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
i think we need to maintain an array of index as well such that while subtracting smallest element from largest element of sorted array we need to check if index of largest is greater than index of smallest. if no..then this is not the solution.. On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.com wrote: Let's say array A , 1 till n s_index = 1; e_index = n ; start = A[s_index] ; end = A[e_index]; result = 0; //! j - i if ( *end *start ){ result = index(end) - index(start) ( only of its greater than previous value of result ) break ; }else{ end-- ; //! till you reach start } now increment start , and repeat the process but only from A[n] till A[++result] , going further down is not required now. Average time o(n^2) Worst case : let's say we have descending array of ints, theno(n^2) Please suggest improvements On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote: given an array A of n elements. for indexes j , i such that ji maximize( j - i ) such that A[j] - A [ i ] 0 . Any Algorithm less than O(n^2) would do. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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
yes we need to maintain an array that shows the real indexes before sorting and then loop on the elements and find the minimum index that appeared before a number in the sorted array and subtract it from it's index and find the maximum difference On 6/12/10, divya jain sweetdivya@gmail.com wrote: i think we need to maintain an array of index as well such that while subtracting smallest element from largest element of sorted array we need to check if index of largest is greater than index of smallest. if no..then this is not the solution.. On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.com wrote: Let's say array A , 1 till n s_index = 1; e_index = n ; start = A[s_index] ; end = A[e_index]; result = 0; //! j - i if ( *end *start ){ result = index(end) - index(start) ( only of its greater than previous value of result ) break ; }else{ end-- ; //! till you reach start } now increment start , and repeat the process but only from A[n] till A[++result] , going further down is not required now. Average time o(n^2) Worst case : let's say we have descending array of ints, theno(n^2) Please suggest improvements On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote: given an array A of n elements. for indexes j , i such that ji maximize( j - i ) such that A[j] - A [ i ] 0 . Any Algorithm less than O(n^2) would do. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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 algoge...@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
This problem seems to be finding the maxdiff in an array. int maxdiff ( int A[], int n ) { // write your code here int max_diff = A[1] - A[0]; int min_element = A[0]; int i; for(i = 1; i n; i++) { if(A[i] - min_element max_diff) max_diff = A[i] - min_element; if(A[i] min_element) min_element = A[i]; } if(max_diff 0) max_diff = 0; return max_diff; } . Satya On Sat, Jun 12, 2010 at 3:18 PM, divya jain sweetdivya@gmail.comwrote: i think we need to maintain an array of index as well such that while subtracting smallest element from largest element of sorted array we need to check if index of largest is greater than index of smallest. if no..then this is not the solution.. On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.comwrote: Let's say array A , 1 till n s_index = 1; e_index = n ; start = A[s_index] ; end = A[e_index]; result = 0; //! j - i if ( *end *start ){ result = index(end) - index(start) ( only of its greater than previous value of result ) break ; }else{ end-- ; //! till you reach start } now increment start , and repeat the process but only from A[n] till A[++result] , going further down is not required now. Average time o(n^2) Worst case : let's say we have descending array of ints, theno(n^2) Please suggest improvements On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote: given an array A of n elements. for indexes j , i such that ji maximize( j - i ) such that A[j] - A [ i ] 0 . Any Algorithm less than O(n^2) would do. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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
@Satya: I don't think what you have coded will work.. though i have not read the whole code. Don't you think a simple divide and conquer scheme would work...(almost like the mergesort) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 On Sat, Jun 12, 2010 at 9:06 PM, Satya satya...@gmail.com wrote: This problem seems to be finding the maxdiff in an array. int maxdiff ( int A[], int n ) { // write your code here int max_diff = A[1] - A[0]; int min_element = A[0]; int i; for(i = 1; i n; i++) { if(A[i] - min_element max_diff) max_diff = A[i] - min_element; if(A[i] min_element) min_element = A[i]; } if(max_diff 0) max_diff = 0; return max_diff; } . Satya On Sat, Jun 12, 2010 at 3:18 PM, divya jain sweetdivya@gmail.comwrote: i think we need to maintain an array of index as well such that while subtracting smallest element from largest element of sorted array we need to check if index of largest is greater than index of smallest. if no..then this is not the solution.. On 12 June 2010 14:20, Modeling Expert cs.modelingexp...@gmail.comwrote: Let's say array A , 1 till n s_index = 1; e_index = n ; start = A[s_index] ; end = A[e_index]; result = 0; //! j - i if ( *end *start ){ result = index(end) - index(start) ( only of its greater than previous value of result ) break ; }else{ end-- ; //! till you reach start } now increment start , and repeat the process but only from A[n] till A[++result] , going further down is not required now. Average time o(n^2) Worst case : let's say we have descending array of ints, theno(n^2) Please suggest improvements On Jun 12, 12:14 am, amit amitjaspal...@gmail.com wrote: given an array A of n elements. for indexes j , i such that ji maximize( j - i ) such that A[j] - A [ i ] 0 . Any Algorithm less than O(n^2) would do. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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.