[algogeeks] Find Largest number in log(n)
Hi every one. Can we find largest number from an unsorted array in log(n) ? -- **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.
Re: [algogeeks] Find the number of occurences of maximum sum in given array.
use kadane 's algorithm On Mon, Aug 15, 2011 at 8:46 PM, Bharat Kul Ratan bharat.kra...@gmail.comwrote: We've to count how many the times the maximum sum occurs in an array. Value of maximum sum includes only contiguous elements and is defined as addition of elements. For example, if given array is: 0 1 1 2 ; maxsum is 4 and count is 2 1 0 1 ; maxsum is 2 and count is 1 1 0 -1 -1 1 0 ; maxsum is 1 and count is 4 0 0 0 0 ; maxusm is 0 and count is 10 -- 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/-/ZflOcnPTItAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Find the number of occurences of maximum sum in given array.
u can use count sort or bucket sort, hashing Regards, Adi Srikanth. Mob No 9887233349 Personal Pages: adisrikanth.co.nr On Mon, Aug 15, 2011 at 8:54 PM, sukran dhawan sukrandha...@gmail.comwrote: use kadane 's algorithm On Mon, Aug 15, 2011 at 8:46 PM, Bharat Kul Ratan bharat.kra...@gmail.com wrote: We've to count how many the times the maximum sum occurs in an array. Value of maximum sum includes only contiguous elements and is defined as addition of elements. For example, if given array is: 0 1 1 2 ; maxsum is 4 and count is 2 1 0 1 ; maxsum is 2 and count is 1 1 0 -1 -1 1 0 ; maxsum is 1 and count is 4 0 0 0 0 ; maxusm is 0 and count is 10 -- 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/-/ZflOcnPTItAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Find the number of occurences of maximum sum in given array.
@sukran: I've gone through Kadane's algo but I was looking for the number of times the sum appears especially cases involving zeros. -- 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/-/oxoVhP3i8lYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Find the number of occurences of maximum sum in given array.
u can keep a counter for the number of max values.not sure whether the algo works for zero.u can extend the algo i guess.correct me if i m wrong On Mon, Aug 15, 2011 at 9:34 PM, Bharat Kul Ratan bharat.kra...@gmail.comwrote: @sukran: I've gone through Kadane's algo but I was looking for the number of times the sum appears especially cases involving zeros. -- 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/-/oxoVhP3i8lYJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Find the number of occurences of maximum sum in given array.
i think this wl work. #includecstdio long long int myread() { char str[20]; long long int sum,i; scanf(%s,str); for(i=0,sum=0;str[i];i++) sum =(sum*10)+str[i]-'0'; return sum; } long long arr[50020]; #define MOD 19LL long long modulo(int a,long long b) { long long x=1,y=a; while(b) { if((b1)==1) x=(x*y)%MOD;y=(y*y)%MOD;b=1;} return x; } int main() { int test,c,pc; test=myread(); long long n,num,maxsum,cnt; while(test--) {n=myread(); maxsum=-11,c=0,pc=0,cnt=0; int index=-1; for(int i=0;in;i++) { scanf(%lld,num);arr[++index]=num; if(num0){if(maxsum0) maxsum=0;maxsum+=num,pc++;} else if(num0) { if(nummaxsum) maxsum=num;} else if(num==0) {if(nummaxsum) maxsum=num;c++;} } long long mod=modulo(2,c); printf(%lld,maxsum); if(pc0) cnt=mod; else if(c0c!=n) {cnt=mod-1;} else { if(c==n) cnt=mod-1; else {c=0;for(int i=0;i=index;i++) if(arr[i]==maxsum)c++; cnt=c;}} printf( %lld\n,cnt); } return 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] Find the number of solutions.
x^(x^x) - (x^x)^x = 0 Thus, x^(x^x) = (x^x)^x Let's open it up by taking log on both sides... (x^x)*log(x) = x* log(x^x) (x^x)*log(x) = x*x*log(x) If x==1 equation is satisfied as log(x) becomes 0.. so x=1 is definitely a solution. what if when x != 1 cancelling log(x) on both the sides.. x^x = x^2 Taking log on both sides.. x*log(x) = 2*log(x) As x !=1 we can cancel log(x) on both the sides to get x = 2 Thus, final solution is {1,2} -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Find the number of solutions.
how many values of x are possible in the following equation. x^(x^x) - (x^x)^x = 0 where a^b =power(a,b). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Find the number of solutions.
2 solutions - {1,2} On Fri, Jul 29, 2011 at 11:10 AM, vaibhav_iiit honeys...@gmail.com wrote: how many values of x are possible in the following equation. x^(x^x) - (x^x)^x = 0 where a^b =power(a,b). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Find the number of solutions.
this question is from http://www.facebook.com/groups/150933398312351/?ap=1 -- *WITH BEST REGARDS : AASHISH SUMAN MCA FINAL YEAR * *NIT DURGAPUR* *+91-9547969906* -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] find the number.
Given range of numbers between A and B (A= B) Find the number within given range which has more number of iterations as per the following n { stop ; return iteration number } if n=1; n = 3n+1 if n is odd n = n/2 if n is even for eg : n=3 odd n=10; n=5; n=16; n=8; n=4; n=2; n=1; iterations : 7 -- * Time complexity= (n^2) * *NARESH ,A* ** -- 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.
[algogeeks] Find Max Number of Elephants
Maximum number of elephants alive Hello guyz, Every elephant has a birth_time and a death_time. Given N Elephants with birth times and death times.. How can we find 1) the maximum number of elephants that can be alive at any given point of time. 2) what is the year in which you can have maximum number of elephants alive. ex: E1 - 2000-2008 E2-2004-2012 E3-2006-2009 So in 2006 you have 3 elephants alive (maximum) PS: ignore months and all stuff .. if a elephants live in a year consider it lives that complete year I have O(year_max-year_min) solution and O(n^2) solution , where n=number of elephants . Can we do better ?? thanks -- 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] Find Max Number of Elephants
use interval trees. Anurag Sharma http://anuragsharma-sun.blogspot.com/ On Sat, Jun 5, 2010 at 6:16 PM, amit amitjaspal...@gmail.com wrote: Maximum number of elephants alive Hello guyz, Every elephant has a birth_time and a death_time. Given N Elephants with birth times and death times.. How can we find 1) the maximum number of elephants that can be alive at any given point of time. 2) what is the year in which you can have maximum number of elephants alive. ex: E1 - 2000-2008 E2-2004-2012 E3-2006-2009 So in 2006 you have 3 elephants alive (maximum) PS: ignore months and all stuff .. if a elephants live in a year consider it lives that complete year I have O(year_max-year_min) solution and O(n^2) solution , where n=number of elephants . Can we do better ?? thanks -- 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] Find Max Number of Elephants
@Amit : Query 1 : It can be solved in O(n) by checking which elephants life span contain the given year Query 2 : Picking up the fact that a elephant die only after its birth we can find the second query in O(nlogn) ALGO: 1. sort in increasing order birth year and death year seperately 2. increment the birth year till we get a value of year which is equal to first death year, keep count of current elephant alive in a value MAX_ELE. 3. Now as one element died decrement one count and increment till we get a year value in birth list which is greater or equal to second death date, keep track of elephents alive and if it is greater than previous,update MAX_ELE with current elephant count 4. continue till birth list empty sorting will require O(nlogn) and finding year in which max elephents were alive will take O(n).Total complexity O(nlogn) Correct me anything wrong -- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. 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 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] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
On Mon, May 31, 2010 at 10:01 PM, souravsain souravs...@gmail.com wrote: Hi All This is my first post to this community and so am exited. The problem is to find the no. that has maximum frequency in an array (size n) of integers. The approach to use a hash table, itereate through array (O(n)) and keep inserting into hash table (O(1)) and then scan the hash table (O(n)) to find entry with max frequency is known. You don't need to scan hash table again. Keep track of max while inserting. Update max when ever freq of some character is more than max. Not to mention that one more iteration is needed to find the maximum value in array so as to decide the sixe of hash table (to keep insertion perfectly O(N). I am looking for a solution which is having O(1) space complexity. The best I can think of is to sort the array in O(nlogn) and then make a pass through the array O(n) to find one with max frequency. So here time complexity is O(nlogn + n). Can we have a better solution? -- 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] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
This question has already been discussed here.There are 4-5 methods to do this ,best is 'Moore voting algorithm' . refer: http://geeksforgeeks.org/?p=503 On Mon, May 31, 2010 at 10:01 PM, souravsain souravs...@gmail.com wrote: Hi All This is my first post to this community and so am exited. The problem is to find the no. that has maximum frequency in an array (size n) of integers. The approach to use a hash table, itereate through array (O(n)) and keep inserting into hash table (O(1)) and then scan the hash table (O(n)) to find entry with max frequency is known. Not to mention that one more iteration is needed to find the maximum value in array so as to decide the sixe of hash table (to keep insertion perfectly O(N). I am looking for a solution which is having O(1) space complexity. The best I can think of is to sort the array in O(nlogn) and then make a pass through the array O(n) to find one with max frequency. So here time complexity is O(nlogn + n). Can we have a better solution? -- 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] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
see this .vote majority algorithm.. http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html -- 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] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
This is a different problem, where the requested number with maximum frequency is not necessary majority. On 2010-6-1 13:19, harit agarwal wrote: see this .vote majority algorithm.. http://userweb.cs.utexas.edu/~moore/best-ideas/mjrty/index.html http://userweb.cs.utexas.edu/%7Emoore/best-ideas/mjrty/index.html -- 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.
[algogeeks] Find the number with maximum frequency in an array. Better than O(nlogn + n) time complexity
Hi All This is my first post to this community and so am exited. The problem is to find the no. that has maximum frequency in an array (size n) of integers. The approach to use a hash table, itereate through array (O(n)) and keep inserting into hash table (O(1)) and then scan the hash table (O(n)) to find entry with max frequency is known. Not to mention that one more iteration is needed to find the maximum value in array so as to decide the sixe of hash table (to keep insertion perfectly O(N). I am looking for a solution which is having O(1) space complexity. The best I can think of is to sort the array in O(nlogn) and then make a pass through the array O(n) to find one with max frequency. So here time complexity is O(nlogn + n). Can we have a better solution? -- 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.
[algogeeks] Find the number of paths between two points on a grid
There are nodes as determined by given points, and you have to find the number of paths between two given points by going on the nodes, and you can't repeat a node for a path. You have to horizontal and vertical (no diagonal in a path) --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---