[algogeeks] Re: THANX ALGOGEEKS !!!!!!
Hey please post the written test questions ! Thanks On Sep 22, 8:29 am, saurabh sah.saurab...@gmail.com wrote: I sincerely thank this group as i got selected in MicrosoftIDConly because of this group . It was a wonderful experience for me at the interviews because the some of questions were closely related to the questions discussed here . And i also got to know about book Crackin the Coding Interviews which is more than sufficient for any company interviews from this group only . Finally i thank all those group members who shared their experiences and others who replied to their queries . GOOD LUCK to all Saurabh Sah Final Year, B.Tech MNIT JAIPUR -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: ARTICULATION POINT ALGO
It is also an application of depth first traversal. Articulation point is a vertex which if removed will leave the graph unconnected. Since i do not completely remember the algorithm myself, i would recommend you to refer Mark Allan Weiss's book on Data Structures and Algorithms in C++ and Graphs chapter. He has nicely explained this algorithm. On Oct 24, 2:23 am, kartik sachan kartik.sac...@gmail.com wrote: yup but didn't get much out of it... -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Search an element in an Infinite array
What is the logic on choosing power of two as search indexes ? On Oct 24, 12:56 am, Ankur Garg ankurga...@gmail.com wrote: Use Binary Search start = 2^n-1 high =2^n where n=0,1 On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal sunny816.i...@gmail.comwrote: hint 1: try to find 2 indexes i, j such that a[i] = K = a[j] On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.com wrote: Given a sorted array of Infinite size, find an element ‘K’ in the array without using extra memory in O (lgn) time -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. V 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Search an element in an Infinite array
+1 ankur On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.com wrote: Use Binary Search start = 2^n-1 high =2^n where n=0,1 On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal sunny816.i...@gmail.comwrote: hint 1: try to find 2 indexes i, j such that a[i] = K = a[j] On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.comwrote: Given a sorted array of Infinite size, find an element ‘K’ in the array without using extra memory in O (lgn) time -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. V 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Amazon Onsite
Suppose there is a circle. You have five points on that circle. Each point corresponds to a petrol pump. You are given two sets of data. 1. The amount of petrol that petrol pump will give. 2. Distance from that petrol pump tp the next petrol pump. (Assume for 1 lit Petrol the truck will go 1 km) Now calculate the first point from where a truck will be able to complete the circle. (The truck will stop at each petrol pump and it has infinite capacity). Give o(n) solution. You may use o(n) 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 algogeeks@googlegroups.com. To unsubscribe from 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] Search an element in an Infinite array
@Ankur Don't think there's any major reason for using powers of 2 except the fact that computing the powers of 2 can be done very efficiently than computing the powers of any other number. Complexity in any case remains the same. On 24 October 2011 10:29, rahul sharma rahul23111...@gmail.com wrote: +1 ankur On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.com wrote: Use Binary Search start = 2^n-1 high =2^n where n=0,1 On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal sunny816.i...@gmail.comwrote: hint 1: try to find 2 indexes i, j such that a[i] = K = a[j] On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.comwrote: Given a sorted array of Infinite size, find an element ‘K’ in the array without using extra memory in O (lgn) time -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. V 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Bittu Sarkar 5th Year Dual Degree Student Department of Computer Science Engineering Indian Institute of Technology Kharagpur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Amazon Onsite
I will choose the point where amount of fuel is maximum choose the shortest path from two direction (clockwise or anticlockwise).. With regards, Praveen Raj DCE-IT 3rd yr 735993 praveen0...@gmail.com On Mon, Oct 24, 2011 at 4:36 PM, Aniket aniket...@gmail.com wrote: Suppose there is a circle. You have five points on that circle. Each point corresponds to a petrol pump. You are given two sets of data. 1. The amount of petrol that petrol pump will give. 2. Distance from that petrol pump tp the next petrol pump. (Assume for 1 lit Petrol the truck will go 1 km) Now calculate the first point from where a truck will be able to complete the circle. (The truck will stop at each petrol pump and it has infinite capacity). Give o(n) solution. You may use o(n) 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 algogeeks@googlegroups.com. To unsubscribe from 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] Search an element in an Infinite array
@Bittu...When we choose low as 2^(n-1) and high as 2^n we are reducing the complexity from O(n) (Linear Search ) to logn (base2) . Here the thing is to apply normal binary search between low and high and thats where we decrease the complexity . If the required element is not in this range we change low=high and high = 2*high and again apply Binary Search. In the code before applying binary search u each time check whether k a[high] . If not we change low and high else apply binary search here . Ideally the complexity would be lot less than log(n) but since the no is infinite and k can also be taken very very high then say k lies between 2*(10^9) and 4*(10^9) which is a very high number in Itself . n is that very high number This approach wont work if the infinite array is not sorted Regards Ankur On Mon, Oct 24, 2011 at 7:09 PM, Bittu Sarkar bittu...@gmail.com wrote: @Ankur Don't think there's any major reason for using powers of 2 except the fact that computing the powers of 2 can be done very efficiently than computing the powers of any other number. Complexity in any case remains the same. On 24 October 2011 10:29, rahul sharma rahul23111...@gmail.com wrote: +1 ankur On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.com wrote: Use Binary Search start = 2^n-1 high =2^n where n=0,1 On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal sunny816.i...@gmail.com wrote: hint 1: try to find 2 indexes i, j such that a[i] = K = a[j] On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.comwrote: Given a sorted array of Infinite size, find an element ‘K’ in the array without using extra memory in O (lgn) time -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. V 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. -- Bittu Sarkar 5th Year Dual Degree Student Department of Computer Science Engineering Indian Institute of Technology Kharagpur -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Amazon Onsite
Lets say the Amount of petrol is Pi and distance to next petrol pump is Di for ith petrol pump. start from i=1, j=1 S =0 while (i=n) S += Pj - Dj; if S = 0 j = i-1 return i if S 0 j = i-1 return 0 else if S = 0 j++ mod n; else if S 0 j ++ mod n, i = j , S = 0; return 0 it will traverse atmost twice, and hence O(n). no extra space required. On Mon, Oct 24, 2011 at 4:06 AM, Aniket aniket...@gmail.com wrote: Suppose there is a circle. You have five points on that circle. Each point corresponds to a petrol pump. You are given two sets of data. 1. The amount of petrol that petrol pump will give. 2. Distance from that petrol pump to the next petrol pump. (Assume for 1 lit Petrol the truck will go 1 km) Now calculate the first point from where a truck will be able to complete the circle. (The truck will stop at each petrol pump and it has infinite capacity). Give o(n) solution. You may use o(n) 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Nitin Garg Personality can open doors, but only Character can keep them open -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Search an element in an Infinite array
using power of 2 approach doubles the scope of search each time.
How about using approximation. Say I have lower bound lb and upper bound ub.
Now -
initially lb = 0, ub = 1;
while (a[ub] k)
{
lb = ub;
ub = (ub*k) / a[ub];
}
after end of this loop we'll have a lower bound and upper which should
provide a narrow scope.
Feedback welcome :-),
- Ravindra
On Mon, Oct 24, 2011 at 7:09 PM, Bittu Sarkar bittu...@gmail.com wrote:
@Ankur Don't think there's any major reason for using powers of 2 except
the fact that computing the powers of 2 can be done very efficiently than
computing the powers of any other number. Complexity in any case remains the
same.
On 24 October 2011 10:29, rahul sharma rahul23111...@gmail.com wrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.com wrote:
Use Binary Search
start = 2^n-1 high =2^n where n=0,1
On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal sunny816.i...@gmail.com
wrote:
hint 1: try to find 2 indexes i, j such that a[i] = K = a[j]
On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.comwrote:
Given a sorted array of Infinite size, find an element ‘K’ in the
array without using extra memory in O (lgn) time
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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. V 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.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] K-best assignment problem
Its like a queen problem ...with row and column are not same.. With regards, Praveen Raj DCE-IT 3rd yr 735993 praveen0...@gmail.com On Tue, Oct 18, 2011 at 12:06 AM, Don dondod...@gmail.com wrote: Given a cost matrix with N columns and M rows such that M=N, find the K lowest total cost ways to select one item from each column, with the restriction that only one item may be selected from any row. Don -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] choosing numbers
for 3 set .. set value stored in array a[3] and p is the sum
for( i=0;i=a[0];i++)
{
for(j=0;j=a[1];j++)
{
for(k=a[2];k=0;k--)
{
if((i+j+k)p) // improve running time
break;
if((i+j+k)==p)
coutijk;
}
}
}
With regards,
Praveen Raj
DCE-IT 3rd yr
735993
praveen0...@gmail.com
On Mon, Oct 24, 2011 at 3:00 AM, Piyush Kapoor pkjee2...@gmail.com wrote:
Suppose u choose ith element from the Kth set,then
dp[K][Sum]=sum(from i=0 to number of elements in the Kth set)
dp[K-1][Sum-(ith element of Kth set)]
On Sun, Oct 23, 2011 at 3:31 PM, cegprakash cegprak...@gmail.com wrote:
hi i recently came across this problem..
there are K sets
each sets can contain n numbers from 0 to n
we've to choose exactly one number from each set
the sum of all the elements that we chose should be equal to P.
we have to find how many such possibilities are there to choose so..
for example
assume there are 3 sets containing 1,2,3 elements in them
so the first set contains 0 and 1
second set contains 0,1 and 2
third set contains 0,1,2 and 3
assume P=2
in this case there are 5 possibilities
(0,0,2), (0,1,1), (0,2,0), (1,0,1), (1,1,0)
i'm struggling for a DP solution!! help me out
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
*Regards,*
*Piyush Kapoor,*
*2nd year,CSE
IT-BHU*
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Amazon Onsite
@Nitin, excellent algo. if S 0 j = i-1 return 0 // I believe this mean there is no solution, you might want to return -1. Thanks, - Ravindra On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg nitin.garg.i...@gmail.comwrote: Lets say the Amount of petrol is Pi and distance to next petrol pump is Di for ith petrol pump. start from i=1, j=1 S =0 while (i=n) S += Pj - Dj; if S = 0 j = i-1 return i if S 0 j = i-1 return 0 else if S = 0 j++ mod n; else if S 0 j ++ mod n, i = j , S = 0; return 0 it will traverse atmost twice, and hence O(n). no extra space required. On Mon, Oct 24, 2011 at 4:06 AM, Aniket aniket...@gmail.com wrote: Suppose there is a circle. You have five points on that circle. Each point corresponds to a petrol pump. You are given two sets of data. 1. The amount of petrol that petrol pump will give. 2. Distance from that petrol pump to the next petrol pump. (Assume for 1 lit Petrol the truck will go 1 km) Now calculate the first point from where a truck will be able to complete the circle. (The truck will stop at each petrol pump and it has infinite capacity). Give o(n) solution. You may use o(n) 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Nitin Garg Personality can open doors, but only Character can keep them open -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Amazon Onsite
I think this can be solved like this . Start from the first petrol pump i.e first point in the circle . Now if the petrol finishes befor reaching the second petrol pump that means we chose the incorrect point . So , choose second petrol pump now. If u reach third, fill ur tanker and move to 4th . Now if before 4th we again run out of petrol that means our choice was incorrect . Start from 4th and so on .. If u reach the starting point again this is the choice we need to make ..and thats the answer . Programatically , it can be thought of Kadane Algo ..(seems to me ..not sure of algo) but I think this way we just make at most 2 pass (in case the petrol pump of choice is just before the first point ) . Please comment in case you think its right/wrong Regards Ankur On Mon, Oct 24, 2011 at 10:15 PM, ravindra patel ravindra.it...@gmail.comwrote: @Nitin, excellent algo. if S 0 j = i-1 return 0 // I believe this mean there is no solution, you might want to return -1. Thanks, - Ravindra On Mon, Oct 24, 2011 at 8:39 PM, Nitin Garg nitin.garg.i...@gmail.comwrote: Lets say the Amount of petrol is Pi and distance to next petrol pump is Di for ith petrol pump. start from i=1, j=1 S =0 while (i=n) S += Pj - Dj; if S = 0 j = i-1 return i if S 0 j = i-1 return 0 else if S = 0 j++ mod n; else if S 0 j ++ mod n, i = j , S = 0; return 0 it will traverse atmost twice, and hence O(n). no extra space required. On Mon, Oct 24, 2011 at 4:06 AM, Aniket aniket...@gmail.com wrote: Suppose there is a circle. You have five points on that circle. Each point corresponds to a petrol pump. You are given two sets of data. 1. The amount of petrol that petrol pump will give. 2. Distance from that petrol pump to the next petrol pump. (Assume for 1 lit Petrol the truck will go 1 km) Now calculate the first point from where a truck will be able to complete the circle. (The truck will stop at each petrol pump and it has infinite capacity). Give o(n) solution. You may use o(n) 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Nitin Garg Personality can open doors, but only Character can keep them open -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: How to Solve This
Correct me if I am wrong,
If the given number is lets say 'p'. We have to find N such that
N=(10^m-1)/9 for least m,that is divisible by 'p'.
(10^m-1)/9 = 0 (mod p)
(10^m-1) = 0 (mod p)
10^m = 1 (mod p)
Since the given number 'p' always ends with a 3 in its units place, 10^m and
p are always co-prime. So using Fermat's Little Theorem we can calculate
m = euler_totient_function(p)
However you can only get a valid solution, but if we want the smalled such
possible 'm', then we have to use Carmichael Function, which will give you
the lowest such possible 'm'.
http://math-it.org/Mathematik/Zahlentheorie/Carmichael.html
On Thu, Oct 13, 2011 at 6:26 PM, Gene gene.ress...@gmail.com wrote:
I should have noted that this can handle inputs up to about 2^32 / (10
* x). Run time is proportional to the number of 1's. You can also add
a bit of code to discover the digits of the multiplicand.
I was able to verify with lisp bignums that: 25,514 1's is equal to
76543 * ( a 25,509 digit number )
An unverified one because my machine ran out of memory while
multiplying (but which took about .05 seconds to find) is:
1,638,726 1's = 9,876,543 times (a 1,638,719 digit number )
On Oct 12, 4:35 pm, Gene gene.ress...@gmail.com wrote:
First note:
0 * 3 = 0
7 * 3 = 21
4 * 3 = 12
1 * 3 = 3
8 * 3 = 24
5 * 3 = 15
2 * 3 = 6
9 * 3 = 27
6 * 3 = 18
3 * 3 = 9
Important is that the final digits of each line count 0 to 9.
Now you can build an answer right to left.
Example: 123.
Check the table to get the rightmost 1.
7 * 123 = 861
Now you need to add ...50 to make the 10's digit a 1. So
50 * 123 = 6150 + 861 = 7011
And now add 100 to get the third 1...
700 * 123 = 86,100 + 7011 = 93,111
Following this pattern:
6000 * 123 = 738,000 + 93,111 = 831,111
6 * 123 = 7,380,000 + 831,111 = 8,211,111
30 * 123 = 36,900,000 + 8,211,111 = 45,111,111
Okay. That's enough. We stop when the carry digits finally turn out
to be all 1's.
In a program once we've arranged for a rightmost 1 we can shift it out
of the calculation by dividing everything by 10. At the same time we
can shift out the trailing zeros in the multiplicands.
So here's a quick implementation. Sorry in advance for mistakes, but
it seems to be working okay:
#include stdio.h
// If x is all 1's (including zero of them), return
// how many there are. Otherwise return ~0u.
unsigned all_ones(unsigned x)
{
unsigned n = 0;
while (x) {
if (x % 10 != 1)
return ~0u;
x /= 10;
++n;
}
return n;
}
// A table s.t. (x + 3 * mul[x % 10]) ends in 1.
unsigned mul[] = {7,0,3,6,9,2,5,8,1,4};
// Return n s.t. x divides sum_{i=0 to n-1} 10^i .
// x must be congruent to 3 mod 10.
unsigned ones(unsigned x)
{
unsigned n, carry = x;
for (n = 0; all_ones(carry) == ~0u; n++) {
carry = (carry + mul[carry % 10] * x) / 10;
// printf(%d\n, carry);
}
return n + all_ones(carry);
}
int main(void)
{
unsigned x;
if (scanf(%u, x) == 1 x % 10 == 3)
printf(%u divides %u 1's\n, x, ones(x));
return 0;
}
On Oct 10, 9:20 am, VIHARRI viharri@gmail.com wrote:
For every number that has 3 in its units place has one multiple which
has all one's i.e. 111 is
such multiple and 13 has a multiple 11. Write a program to find
such multiple for any
number that has 3 at its units place.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
B.Prabhat Kiran
CS08B014
4th Year UnderGrad
Comp Sci Engg
IIT-Madras
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Search an element in an Infinite array
suppose the element doesn't lies in the array and is bigger than the biggest
number:D
everything will fail...
On Mon, Oct 24, 2011 at 9:43 PM, ravindra patel ravindra.it...@gmail.comwrote:
using power of 2 approach doubles the scope of search each time.
How about using approximation. Say I have lower bound lb and upper bound
ub. Now -
initially lb = 0, ub = 1;
while (a[ub] k)
{
lb = ub;
ub = (ub*k) / a[ub];
}
after end of this loop we'll have a lower bound and upper which should
provide a narrow scope.
Feedback welcome :-),
- Ravindra
On Mon, Oct 24, 2011 at 7:09 PM, Bittu Sarkar bittu...@gmail.com wrote:
@Ankur Don't think there's any major reason for using powers of 2 except
the fact that computing the powers of 2 can be done very efficiently than
computing the powers of any other number. Complexity in any case remains the
same.
On 24 October 2011 10:29, rahul sharma rahul23111...@gmail.com wrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.comwrote:
Use Binary Search
start = 2^n-1 high =2^n where n=0,1
On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal
sunny816.i...@gmail.com wrote:
hint 1: try to find 2 indexes i, j such that a[i] = K = a[j]
On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.comwrote:
Given a sorted array of Infinite size, find an element ‘K’ in the
array without using extra memory in O (lgn) time
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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. V 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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
--
Saurabh Singh
B.Tech (Computer Science)
MNNIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: FACEBOOK ONLINE CODING ROUND
is this contest still going? if so, where ? i have a solution that does (100, 1267650600228229401496703205376 )(just one hundred 1's) in 0.03 seconds in an older ruby on an older pc I'd like to submit ;P On Oct 21, 10:48 pm, sunny agrawal sunny816.i...@gmail.com wrote: yea i know 1st Approach is much better and is Only O(N^2) for precomputing all the values for nck and then O(k) for finding no of bits set in The Kth number and another loop of O(k) to find the required number i posted 2nd approach in the context to vandana's tree approach of sorting 2^N numbers, rather simply sort the numbers in the array... and this approach is O(N*2^N) On 10/21/11, sravanreddy001 sravanreddy...@gmail.com wrote: @Sunny.. why do we need an O(2^N) complexity? for a value of N=40-50, the solution is not useful.. but, your 1st approach is lot better and i have got it too.. 1. O(N) complexity to search the k. (k bits in the numbers) x- (sigma 1-k (n C i)) 2. again, keep substracting (k-i) for i= 0-k-1 so.. O(k) here and recursively performing step 2. (worst case complexity is O(T)) where T = nCk O(N) + O(T) == O(T) as it dominates the given number. unless it doesn't fall in the range.. or equivalently -- max( O(T), O(N) ) -- 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/-/NJR9l-UB7c8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. V 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.
[algogeeks] Find all possible combination of integers for a given sum
Hi, my question is given sum=N and combination constraint=M (the number of elements), how to find all possible combinations of integers? For example, given sum=6, combination=3; how to get the result as following: 1+1+4; 1+2+3; 2+2+2; We don't care about order of the elements, which means 1+1+4 and 1+4+1 are considered as same combination. Thanks a lot! Meng -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Search an element in an Infinite array
@Ankur I know that the complexity reduces from linear time (constant length
range checks) to logarithmic time (exponential length range checks). I was
just explaining the reason for not choosing any other number like say 3 to
compute the exponential ranges [3^(k-1)...3^k] in which case the complexity
still remains logarithmic.
On 24 October 2011 21:43, ravindra patel ravindra.it...@gmail.com wrote:
using power of 2 approach doubles the scope of search each time.
How about using approximation. Say I have lower bound lb and upper bound
ub. Now -
initially lb = 0, ub = 1;
while (a[ub] k)
{
lb = ub;
ub = (ub*k) / a[ub];
}
after end of this loop we'll have a lower bound and upper which should
provide a narrow scope.
Feedback welcome :-),
- Ravindra
On Mon, Oct 24, 2011 at 7:09 PM, Bittu Sarkar bittu...@gmail.com wrote:
@Ankur Don't think there's any major reason for using powers of 2 except
the fact that computing the powers of 2 can be done very efficiently than
computing the powers of any other number. Complexity in any case remains the
same.
On 24 October 2011 10:29, rahul sharma rahul23111...@gmail.com wrote:
+1 ankur
On Mon, Oct 24, 2011 at 1:26 AM, Ankur Garg ankurga...@gmail.comwrote:
Use Binary Search
start = 2^n-1 high =2^n where n=0,1
On Mon, Oct 24, 2011 at 12:28 AM, sunny agrawal
sunny816.i...@gmail.com wrote:
hint 1: try to find 2 indexes i, j such that a[i] = K = a[j]
On Sun, Oct 23, 2011 at 11:23 PM, Ankuj Gupta ankuj2...@gmail.comwrote:
Given a sorted array of Infinite size, find an element ‘K’ in the
array without using extra memory in O (lgn) time
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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. V 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.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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.
--
Bittu Sarkar
5th Year Dual Degree Student
Department of Computer Science Engineering
Indian Institute of Technology Kharagpur
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: FACEBOOK ONLINE CODING ROUND
the contests are over... this was a question asked in a college... but now that you have already written such an awesome code, would you mind sharing it??? or atleast the algorithm of your code??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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] Hash Table
I have read that Hash table provides storing/search operations in constant time. Is it true?? How to prove it?? I have not found any sort of proof for it... -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Hash Table
When the number of elements increases gradually ,the complexity must increase .so it the situtaion is like it has to store all the 'n' elements then all the basic operations require O(log n) time.so how it is constant always i am not getting... On 24 October 2011 22:15, kumar raja rajkumar.cs...@gmail.com wrote: I have read that Hash table provides storing/search operations in constant time. Is it true?? How to prove it?? I have not found any sort of proof for it... -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: FACEBOOK ONLINE CODING ROUND
@icy It's still there except that you'll get a different question. That page promises you a telephone interview if you solve the challenge but I don't know how true that is for non-US guys .. i solved one question two weeks back .. and no one contacted me till now .. ~raju On Tue, Oct 25, 2011 at 3:27 AM, icy` vipe...@gmail.com wrote: is this contest still going? if so, where ? i have a solution that does (100, 1267650600228229401496703205376 )(just one hundred 1's) in 0.03 seconds in an older ruby on an older pc I'd like to submit ;P On Oct 21, 10:48 pm, sunny agrawal sunny816.i...@gmail.com wrote: yea i know 1st Approach is much better and is Only O(N^2) for precomputing all the values for nck and then O(k) for finding no of bits set in The Kth number and another loop of O(k) to find the required number i posted 2nd approach in the context to vandana's tree approach of sorting 2^N numbers, rather simply sort the numbers in the array... and this approach is O(N*2^N) On 10/21/11, sravanreddy001 sravanreddy...@gmail.com wrote: @Sunny.. why do we need an O(2^N) complexity? for a value of N=40-50, the solution is not useful.. but, your 1st approach is lot better and i have got it too.. 1. O(N) complexity to search the k. (k bits in the numbers) x- (sigma 1-k (n C i)) 2. again, keep substracting (k-i) for i= 0-k-1 so.. O(k) here and recursively performing step 2. (worst case complexity is O(T)) where T = nCk O(N) + O(T) == O(T) as it dominates the given number. unless it doesn't fall in the range.. or equivalently -- max( O(T), O(N) ) -- 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/-/NJR9l-UB7c8J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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. V 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. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
