[algogeeks] Re: Minimum sum of Array
Yes, that is true. However, trying to find the optimal partition is
equivalent to the 0-1 knapsack problem, which is exponential time. So
S*N is a huge improvement over that. Does someone have a better
solution?
Don
On Jan 7, 10:49 am, Nikhil Karnwal wrote:
> @ Don
> but ur's solution complexity is O(S*N) which is large in case of large N
> and large numbers.
> Like in case of s=100 and N=10^5.
> Correct me if I am wrong.
>
> Nikhil Karnwal
>
>
>
>
>
>
>
> On Mon, Jan 7, 2013 at 9:04 PM, Don wrote:
> > Note that you don't need to store the entire P matrix. You really just
> > need the last column.
> > Don
>
> > On Jan 7, 10:29 am, Don wrote:
> > > You want to partition the array A into to subsets S1 and S2 such that
> > > you minimize |Sum(S1)-Sum(S2)|.
>
> > > The optimal sum for the subsets is S=SUM(A)/2
>
> > > Use DP to build a matrix P:
> > > P[i][j] = 1 if some subset of {A[0]..A[i]} has a sum of j, 0 otherwise
>
> > > Now find a value of i such that P[n][i] = 1 which minimizes S-i.
>
> > > The minimum sum is 2S-2i.
>
> > > Don
>
> > > On Jan 5, 12:58 pm, mukesh tiwari
> > > wrote:
>
> > > > Hello All!
> > > > I have a given array of numbers and I have to change the sign of
> > numbers to
> > > > find out the minimum sum. The minimum sum will be 0 or greater than 0.
> > Here
> > > > is couple of test cases
> > > > 1. [ 1 , 2 , 3 , 2 , 4 ]. Changing the sign [ -1 , -2 , -3 , 2 , 4 ]
> > so
> > > > minimum sum will be 0.
> > > > 2. [ 3 , 5 , 7 , 11 , 13 ]. Changing the sign [ -3 , -5 , 7 , -11 ,
> > 13 ]
> > > > so minimum sum is 1.
>
> > > > So technically this problem boils down to divide the set into two
> > subset
> > > > and find out the minimum difference. I though of DP but the number of
> > > > element in array could 10^5 so could some one please tell me how to
> > solve
> > > > this problem ? I didn't assume that number will be positive because it
> > was
> > > > not given in the problem.
>
> > > > Regards
> > > > Mukesh Tiwari
>
> > --
--
[algogeeks] Re: perfect square condition checking....
Sure, Let's try two examples: x=1,038,381,081 The last digit is 1, so continue Now start with y=10,000 because that is half as many digits as x. y0 = 10,000 y1 = 56919 y2 = 37581 y3 = 32605 y4 = 32226 y5 = 32226 y6 = 32223 y7 = 32223 Y6=Y7 so you are done. Now square y7 giving 1,038,321,729. That is not equal to x, so x is not a perfect square. Second case x=1,038,579,529 Last digit is 9, so continue. y1 = 1 y2 = 56928 y3 = 37585 y4 = 32608 y5 = 32229 y6 = 32227 y7 = 32227 32227^2 = x, so x is a perfect square. Don On Jan 5, 8:08 am, bala bharath wrote: > @Don, > Can u explain with an Example...? > > With regards, > > Balasubramanian Naagarajan, > > Chettinad > College of Engg & Tech. > > > > > > > > On Sat, Jan 5, 2013 at 1:48 PM, Malathi wrote: > > Check this. It might help. > > >http://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-n... > > > On Sat, Jan 5, 2013 at 1:47 AM, Don wrote: > > >> start with a guess y. If you can arrange for y to be about half the > > > -- > > > With Regards, > > Malathi > > > -- --
[algogeeks] Re: sortin 2D array
Use a merge sort to merge the rows throwing out duplicates.
Don
On Jan 8, 12:59 pm, Ravi Ranjan wrote:
> You have a two dimensional array of size m*n. The
> elements in the rows are sorted and every row has
> unique elements means( in a row no two elements are same) but
> the elements can repeat across the rows.
> For example:
> you have following 2-D array:
> 2 5 7 9 14 16
> 3 6 8 10 15 21
> 4 7 9 15 22 35
> 7 8 9 22 40 58
> You are supposed to write an efficient function which
> will take upper 2-D array as input and will return a
> one-dimensional array with following properties:
> a) the 1-D array must contain all the elements of above
> 2-D array.
> b) the 1-D array should not have any repeated elements.
> c) all the elements should be in sorted order.
> For example:
> for the above 2-D array, the output should be:
> A [ ] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 16, 21, 22, 35,
> 40, 58 }
--
[algogeeks] Re: sortin 2D array
@Dave: Very nice.
If you merge pairs of rows and throw out dupicates, I believe that is
also O(m*n*log(m)). It takes log(m) times merging all of the rows. The
number and length of the rows changes, but the total number of
elements will be m*n or less.
Don
On Jan 8, 3:16 pm, Dave wrote:
> @Ravi: Construct a min-heap of the elements of the first column, each
> appended with its row and column number, i.e., form a heap whose elements
> contain (a[i][0], i, 0).
> While the heap is not empty:
> Output the top element of the heap.
> Insert the next element from its row, if any.
> If the output array is empty, or if the outputted heap top is different
> from the last element in the output array,
> then insert the outputted heap top into the output array.
>
> Complexity is m*n*log(m).
>
> Dave
>
>
>
>
>
>
>
> On Tuesday, January 8, 2013 11:59:55 AM UTC-6, Ravi Ranjan wrote:
> > You have a two dimensional array of size m*n. The
> > elements in the rows are sorted and every row has
> > unique elements means( in a row no two elements are same) but
> > the elements can repeat across the rows.
> > For example:
> > you have following 2-D array:
> > 2 5 7 9 14 16
> > 3 6 8 10 15 21
> > 4 7 9 15 22 35
> > 7 8 9 22 40 58
> > You are supposed to write an efficient function which
> > will take upper 2-D array as input and will return a
> > one-dimensional array with following properties:
> > a) the 1-D array must contain all the elements of above
> > 2-D array.
> > b) the 1-D array should not have any repeated elements.
> > c) all the elements should be in sorted order.
> > For example:
> > for the above 2-D array, the output should be:
> > A [ ] = { 2, 3, 4, 5, 6, 7, 8, 9, 10, 14, 15, 16, 21, 22, 35,
> > 40, 58 }
--
[algogeeks] Re: Minimum sum of Array
My solution is equivalent to using DP for the 0-1 knapsack, but the DP
approach does not identify the partition, it only determines if it
exists. In the same way, my solution does not determine which numbers
to make negative. It only determines what the smallest possible sum
is. The DP approach to 0-1 knapsack is not really a solution, if the
problem is stated in the usual way: what set of objects should I put
in the knapsack to maximize the total. It only solves the problem:
what is the maximum total I can achieve.
On Jan 9, 7:12 am, Carl Barton wrote:
> How is it a huge improvement? Your O(SN) is the same time as the dynamic
> programming solution for 0-1 knapsack isn't it?
>
> On 8 January 2013 14:44, Don wrote:
>
>
>
>
>
>
>
> > Yes, that is true. However, trying to find the optimal partition is
> > equivalent to the 0-1 knapsack problem, which is exponential time. So
> > S*N is a huge improvement over that. Does someone have a better
> > solution?
> > Don
>
> > On Jan 7, 10:49 am, Nikhil Karnwal wrote:
> > > @ Don
> > > but ur's solution complexity is O(S*N) which is large in case of large N
> > > and large numbers.
> > > Like in case of s=100 and N=10^5.
> > > Correct me if I am wrong.
>
> > > Nikhil Karnwal
>
> > > On Mon, Jan 7, 2013 at 9:04 PM, Don wrote:
> > > > Note that you don't need to store the entire P matrix. You really just
> > > > need the last column.
> > > > Don
>
> > > > On Jan 7, 10:29 am, Don wrote:
> > > > > You want to partition the array A into to subsets S1 and S2 such that
> > > > > you minimize |Sum(S1)-Sum(S2)|.
>
> > > > > The optimal sum for the subsets is S=SUM(A)/2
>
> > > > > Use DP to build a matrix P:
> > > > > P[i][j] = 1 if some subset of {A[0]..A[i]} has a sum of j, 0
> > otherwise
>
> > > > > Now find a value of i such that P[n][i] = 1 which minimizes S-i.
>
> > > > > The minimum sum is 2S-2i.
>
> > > > > Don
>
> > > > > On Jan 5, 12:58 pm, mukesh tiwari
> > > > > wrote:
>
> > > > > > Hello All!
> > > > > > I have a given array of numbers and I have to change the sign of
> > > > numbers to
> > > > > > find out the minimum sum. The minimum sum will be 0 or greater
> > than 0.
> > > > Here
> > > > > > is couple of test cases
> > > > > > 1. [ 1 , 2 , 3 , 2 , 4 ]. Changing the sign [ -1 , -2 , -3 , 2 ,
> > 4 ]
> > > > so
> > > > > > minimum sum will be 0.
> > > > > > 2. [ 3 , 5 , 7 , 11 , 13 ]. Changing the sign [ -3 , -5 , 7 , -11
> > ,
> > > > 13 ]
> > > > > > so minimum sum is 1.
>
> > > > > > So technically this problem boils down to divide the set into two
> > > > subset
> > > > > > and find out the minimum difference. I though of DP but the number
> > of
> > > > > > element in array could 10^5 so could some one please tell me how to
> > > > solve
> > > > > > this problem ? I didn't assume that number will be positive
> > because it
> > > > was
> > > > > > not given in the problem.
>
> > > > > > Regards
> > > > > > Mukesh Tiwari
>
> > > > --
>
> > --
--
[algogeeks] Re: Suggested the Data Structure to implement the solution in O(1)
I don't think that perfect hashing provides "nthentry" in constant time. You could store items in a vector indexed by the order in which they were inserted. Retrieving an item would be constant time, but what happens when you have thousands of items and you need to delete item 27? Now most of the items in the vector are in the wrong spot. If you move them all down one, that is not constant time anymore. I think I could do any 3 of the 4 operations, but all 4 is tough. Does anyone have a solution. Particularly one which does not rely on n being a fixed number of bits? Don On Jan 8, 11:40 am, "Karthikeyan V.B" wrote: > Hi, > > Use hashing, but with perfect hashing which does all these operations in > O(1). > > Refer to Introduction to Algorithms by CLRS to learn about perfect hashing. --
[algogeeks] Re: Minimum sum of Array
int q[S] = {0};
q[0] = 1;
for(i = 0; i < N; ++i)
for(j = S; j >= A[i]; --j)
q[j] |= q[j-A[i]];
Then find the largest value i where q[i]=1, and the smallest sum is
2(S-i).
As has been pointed out, S can be large and this method can take a
long time for big input cases.
On Jan 9, 3:04 pm, prankur gupta wrote:
> Hi,
>
> I have understood the solution, but here we are talking about knowing the
> path(elements in the subsets in this case).
> I saw we could use the back pointer technique, which I understood, but I'm
> not able to see how would I code this technique.
> Please try to explain me this thing.
>
> Thanks a lot in advance.
>
>
>
>
>
>
>
>
>
> On Wed, Jan 9, 2013 at 10:46 AM, Don wrote:
> > My solution is equivalent to using DP for the 0-1 knapsack, but the DP
> > approach does not identify the partition, it only determines if it
> > exists. In the same way, my solution does not determine which numbers
> > to make negative. It only determines what the smallest possible sum
> > is. The DP approach to 0-1 knapsack is not really a solution, if the
> > problem is stated in the usual way: what set of objects should I put
> > in the knapsack to maximize the total. It only solves the problem:
> > what is the maximum total I can achieve.
>
> > On Jan 9, 7:12 am, Carl Barton wrote:
> > > How is it a huge improvement? Your O(SN) is the same time as the dynamic
> > > programming solution for 0-1 knapsack isn't it?
>
> > > On 8 January 2013 14:44, Don wrote:
>
> > > > Yes, that is true. However, trying to find the optimal partition is
> > > > equivalent to the 0-1 knapsack problem, which is exponential time. So
> > > > S*N is a huge improvement over that. Does someone have a better
> > > > solution?
> > > > Don
>
> > > > On Jan 7, 10:49 am, Nikhil Karnwal wrote:
> > > > > @ Don
> > > > > but ur's solution complexity is O(S*N) which is large in case of
> > large N
> > > > > and large numbers.
> > > > > Like in case of s=1000000 and N=10^5.
> > > > > Correct me if I am wrong.
>
> > > > > Nikhil Karnwal
>
> > > > > On Mon, Jan 7, 2013 at 9:04 PM, Don wrote:
> > > > > > Note that you don't need to store the entire P matrix. You really
> > just
> > > > > > need the last column.
> > > > > > Don
>
> > > > > > On Jan 7, 10:29 am, Don wrote:
> > > > > > > You want to partition the array A into to subsets S1 and S2 such
> > that
> > > > > > > you minimize |Sum(S1)-Sum(S2)|.
>
> > > > > > > The optimal sum for the subsets is S=SUM(A)/2
>
> > > > > > > Use DP to build a matrix P:
> > > > > > > P[i][j] = 1 if some subset of {A[0]..A[i]} has a sum of j, 0
> > > > otherwise
>
> > > > > > > Now find a value of i such that P[n][i] = 1 which minimizes S-i.
>
> > > > > > > The minimum sum is 2S-2i.
>
> > > > > > > Don
>
> > > > > > > On Jan 5, 12:58 pm, mukesh tiwari
> > > > > > > wrote:
>
> > > > > > > > Hello All!
> > > > > > > > I have a given array of numbers and I have to change the sign
> > of
> > > > > > numbers to
> > > > > > > > find out the minimum sum. The minimum sum will be 0 or greater
> > > > than 0.
> > > > > > Here
> > > > > > > > is couple of test cases
> > > > > > > > 1. [ 1 , 2 , 3 , 2 , 4 ]. Changing the sign [ -1 , -2 , -3 ,
> > 2 ,
> > > > 4 ]
> > > > > > so
> > > > > > > > minimum sum will be 0.
> > > > > > > > 2. [ 3 , 5 , 7 , 11 , 13 ]. Changing the sign [ -3 , -5 , 7 ,
> > -11
> > > > ,
> > > > > > 13 ]
> > > > > > > > so minimum sum is 1.
>
> > > > > > > > So technically this problem boils down to divide the set into
> > two
> > > > > > subset
> > > > > > > > and find out the minimum difference. I though of DP but the
> > number
> > > > of
> > > > > > > > element in array could 10^5 so could some one please tell me
> > how to
> > > > > > solve
> > > > > > > > this problem ? I didn't assume that number will be positive
> > > > because it
> > > > > > was
> > > > > > > > not given in the problem.
>
> > > > > > > > Regards
> > > > > > > > Mukesh Tiwari
>
> > > > > > --
>
> > > > --
>
> > --
>
> --
> PRANKUR GUPTA
>
> Masters Student (CSE)
> State University of New York
> Stony Brook University
> prgu...@cs.stonybrook.edu
--
[algogeeks] Re: perfect square condition checking....
Can you show me a case where it diverges if the initial guess is half the digits of X? Don On Jan 14, 3:09 am, bharat b wrote: > @Don : But, newton's formulae doesn't always converge.. if our guess is bad > enough, it may diverge also. > > > > > > > > On Tue, Jan 8, 2013 at 8:30 PM, Don wrote: > > Sure, > > > Let's try two examples: > > x=1,038,381,081 > > > The last digit is 1, so continue > > Now start with y=10,000 because that is half as many digits as x. > > y0 = 10,000 > > y1 = 56919 > > y2 = 37581 > > y3 = 32605 > > y4 = 32226 > > y5 = 32226 > > y6 = 32223 > > y7 = 32223 > > > Y6=Y7 so you are done. Now square y7 giving 1,038,321,729. That is not > > equal to x, so x is not a perfect square. > > > Second case > > x=1,038,579,529 > > Last digit is 9, so continue. > > y1 = 1 > > y2 = 56928 > > y3 = 37585 > > y4 = 32608 > > y5 = 32229 > > y6 = 32227 > > y7 = 32227 > > > 32227^2 = x, so x is a perfect square. > > > Don > > > On Jan 5, 8:08 am, bala bharath wrote: > > > @Don, > > > Can u explain with an Example...? > > > > With regards, > > > > Balasubramanian Naagarajan, > > > > Chettinad > > > College of Engg & Tech. > > > > On Sat, Jan 5, 2013 at 1:48 PM, Malathi wrote: > > > > Check this. It might help. > > > > >http://www.johndcook.com/blog/2008/11/17/fast-way-to-test-whether-a-n. > > .. > > > > > On Sat, Jan 5, 2013 at 1:47 AM, Don wrote: > > > > >> start with a guess y. If you can arrange for y to be about half the > > > > > -- > > > > > With Regards, > > > > Malathi > > > > > -- > > > -- --
[algogeeks] Re: Amazon Dynamic Programming problem
If it is your turn and there are 1 or 2 balls in the basket you take them and win. If it is your turn an there are 3 balls in the basket, you must leave 1 or 2 after your turn, so you lose. If the number of balls on your turn is not divisible by 3, you can take 1 or 2 balls and make it divisible by three. Your opponent will then have to make it not divisible by three, so the process repeats until you win. So the first player wins if N is not divisible by 3. Don On Jan 12, 8:03 am, siva wrote: > consider there are N balls in a basket. 2 players play the turns > alternatively ..AT each turn,the player > > can take 1 or 2 balls from the basket. the first player starts the game.. > Both the players play optimally. > > i) Given N,tell whether the 1st player win or loss ? > > ii) If player 1 wins, how many balls he should take at this first turn(1 > or 2) ? --
[algogeeks] Re: Amazon Dynamic Programming problem
This problem was a team challenge in Survivor Amazon, except they were allowed to take 1,2,3, or 4 flags. The winning strategy is to leave a multiple of 5 flags. But none of the contestants figured it out. Don On Jan 12, 8:03 am, siva wrote: > consider there are N balls in a basket. 2 players play the turns > alternatively ..AT each turn,the player > > can take 1 or 2 balls from the basket. the first player starts the game.. > Both the players play optimally. > > i) Given N,tell whether the 1st player win or loss ? > > ii) If player 1 wins, how many balls he should take at this first turn(1 > or 2) ? --
[algogeeks] Re: Amazon Dynamic Programming problem
Sprague–Grundy theorem On Jan 12, 6:28 pm, Nguyễn Thành Danh wrote: > Can you please explain by which theorem you use to find out that? > > > > > > > > On Sat, Jan 12, 2013 at 11:41 AM, Lucifer wrote: > > if (n%3 == 0) > > "Player 1 will lose" > > else > > "Player 1 will win. The no. of balls picked in the first turn will > > be n%3" --
[algogeeks] Re: Detect Cycles in a Graph.
The length of the cycles could be related to N, and the number of the cycles could be exponentially related to N, so printing them in linear time is not possible, even if you could detect them. Don On Jan 16, 12:00 am, marti wrote: > Detect and *print *all the cycles present in a Directed Graph in linear > time. --
[algogeeks] Re: Amazon Dynamic Programming problem
Sure, but why? The solution is n%3. DP will by more complex and slower. On Jan 16, 11:43 am, siva wrote: > Thanks all for solutions, but this problem can also be solved using DP > right ??? > > > > > > > > On Wednesday, 16 January 2013 01:57:26 UTC+5:30, Don wrote: > > > Sprague–Grundy theorem > > > On Jan 12, 6:28 pm, Nguyễn Thành Danh > > wrote: > > > Can you please explain by which theorem you use to find out that? > > > > On Sat, Jan 12, 2013 at 11:41 AM, Lucifer > > wrote: > > > > if (n%3 == 0) > > > > "Player 1 will lose" > > > > else > > > > "Player 1 will win. The no. of balls picked in the first turn > > will > > > > be n%3" --
[algogeeks] Re: Amazon Dynamic Programming problem
The DP solution is to mark the winning position as winning. Then mark any positions which can move to a winning position as losing and the rest as winning. On Jan 16, 12:21 pm, siva wrote: > Ya I'm aware, Just wanted to confirm. Suppose if the problem can't be > reduced to a mathematical formulae , then DP must be the reliable solution > for this kind of problems. > That's why wanted to know exact DP solution also.. > > > > > > > > On Wednesday, 16 January 2013 22:42:52 UTC+5:30, Don wrote: > > > Sure, but why? The solution is n%3. DP will by more complex and > > slower. > > > On Jan 16, 11:43 am, siva wrote: > > > Thanks all for solutions, but this problem can also be solved using DP > > > right ??? > > > > On Wednesday, 16 January 2013 01:57:26 UTC+5:30, Don wrote: > > > > > Sprague–Grundy theorem > > > > > On Jan 12, 6:28 pm, Nguyễn Thành Danh > > > > wrote: > > > > > Can you please explain by which theorem you use to find out that? > > > > > > On Sat, Jan 12, 2013 at 11:41 AM, Lucifer > > > > wrote: > > > > > > if (n%3 == 0) > > > > > > "Player 1 will lose" > > > > > > else > > > > > > "Player 1 will win. The no. of balls picked in the first > > turn > > > > will > > > > > > be n%3" --
[algogeeks] Re: Detect Cycles in a Graph.
Tarjan's Algorithm can be used to find strongly connected sets of nodes in linear time. Each strongly connected component contains one or more cycles. But there could be a lot of them, so enumerating them will not be O(N) if N is the number of nodes. On Jan 16, 12:40 pm, marti wrote: > Okay,in the best complexity, whats your method?? > > > > > > > > On Wednesday, January 16, 2013 8:57:46 PM UTC+5:30, Don wrote: > > > The length of the cycles could be related to N, and the number of the > > cycles could be exponentially related to N, so printing them in linear > > time is not possible, even if you could detect them. > > Don > > > On Jan 16, 12:00 am, marti wrote: > > > Detect and *print *all the cycles present in a Directed Graph in linear > > > time. --
[algogeeks] Re: maximum subsquare such that all four borders are filled black
int countRight[n][n];
int countDown[n][n];
int i,j,s;
int bestI, bestJ, max=0;
int lastRight = n;
int lastDown = n;
// Start by setting countRight[i][j] to the number of consecutive
black pixels starting at (i,j) and moving right
// and countDown[i][j] to the number of consecutive black pixels
starting at (i,j) and moving down
for(i = 0; i < n; ++i)
for(j = n-1; j >= 0; --j)
{
if (m[i][j] == white) lastRight = j;
if (m[j][i] == white) lastDown = j;
countRight[i][j] = lastRight - j;
countDown[j][i] = lastDown - j;
}
// Now look for largest square with top left corner at (i,j)
for(i = 0; (i+max) < n; ++i)
for(j = 0; (j+max) < n; ++j)
for(s = Min(countRight[i][j], countDown[i][j]); s > max; --s)
if ((countRight[i+s][j] >= s) && (countDown[i][j+s] >= s))
{
bestI = i; bestJ = j; max = s;
}
Don
On Jan 16, 2:08 pm, marti wrote:
> Imagine there is a square matrix with n x n cells. Each cell is either
> filled with a black pixel or a white pixel. Design an algorithm to find the
> maximum subsquare such that all four borders are filled with black pixels;
> optimize the algorithm as much as possible
--
[algogeeks] Re: maximum subsquare such that all four borders are filled black
Looking at this, I realized that I need to reset lastRight=lastDown=n
inside the first loop, before the for(j=n-1 loop
On Jan 16, 2:59 pm, Don wrote:
> int countRight[n][n];
> int countDown[n][n];
>
> int i,j,s;
> int bestI, bestJ, max=0;
> int lastRight = n;
> int lastDown = n;
>
> // Start by setting countRight[i][j] to the number of consecutive
> black pixels starting at (i,j) and moving right
> // and countDown[i][j] to the number of consecutive black pixels
> starting at (i,j) and moving down
> for(i = 0; i < n; ++i)
> for(j = n-1; j >= 0; --j)
> {
> if (m[i][j] == white) lastRight = j;
> if (m[j][i] == white) lastDown = j;
> countRight[i][j] = lastRight - j;
> countDown[j][i] = lastDown - j;
> }
>
> // Now look for largest square with top left corner at (i,j)
> for(i = 0; (i+max) < n; ++i)
> for(j = 0; (j+max) < n; ++j)
> for(s = Min(countRight[i][j], countDown[i][j]); s > max; --s)
> if ((countRight[i+s][j] >= s) && (countDown[i][j+s] >= s))
> {
> bestI = i; bestJ = j; max = s;
> }
>
> Don
>
> On Jan 16, 2:08 pm, marti wrote:
>
>
>
>
>
>
>
> > Imagine there is a square matrix with n x n cells. Each cell is either
> > filled with a black pixel or a white pixel. Design an algorithm to find the
> > maximum subsquare such that all four borders are filled with black pixels;
> > optimize the algorithm as much as possible
--
[algogeeks] Re: maximum subsquare such that all four borders are filled black
int countRight[n][n];
int countDown[n][n];
int i,j,s;
int bestI, bestJ, max=0;
int lastRight, lastDown = n;
// Start by setting countRight[i][j] to the number of consecutive
// black pixels starting at (i,j) and moving right
// and countDown[i][j] to the number of consecutive black pixels
// starting at (i,j) and moving down
for(i = 0; i < n; ++i)
{
lastDown = lastRight = n;
for(j = n-1; j >= 0; --j)
{
if (m[i][j] == white) lastRight = j;
if (m[j][i] == white) lastDown = j;
countRight[i][j] = lastRight - j;
countDown[j][i] = lastDown - j;
}
}
// Now look for largest square with top left corner at (i,j)
for(i = 0; (i+max) < n; ++i)
for(j = 0; (j+max) < n; ++j)
for(s = Min(countRight[i][j], countDown[i][j]); s > max; --s)
if ((countRight[i+s-1][j] >= s) && (countDown[i][j+s-1] >=
s))
{
bestI = i; bestJ = j; max = s;
}
// Now the biggest square has top left corner at (bestI, bestJ) and
size s.
Don
On Jan 16, 2:08 pm, marti wrote:
> Imagine there is a square matrix with n x n cells. Each cell is either
> filled with a black pixel or a white pixel. Design an algorithm to find the
> maximum subsquare such that all four borders are filled with black pixels;
> optimize the algorithm as much as possible
--
[algogeeks] Re: maximum subsquare such that all four borders are filled black
The downside is that it uses a bunch of extra space. The upside is that it is pretty fast. It only does the time-consuming task of scanning the matrix for contiguous pixels once, it only searches for squares larger than what it has already found, and it doesn't look in places where such squares could not be. In practice it performs at O(n^2) or better for most inputs I tried. But if you are devious you can come up with an input which takes longer. Don On Jan 17, 10:14 am, marti wrote: > awesome solution Don . Thanks. > > > > > > > > On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti wrote: > > > Imagine there is a square matrix with n x n cells. Each cell is either > > filled with a black pixel or a white pixel. Design an algorithm to find the > > maximum subsquare such that all four borders are filled with black pixels; > > optimize the algorithm as much as possible --
[algogeeks] Re: Find all words in given character Matrix
Store the word list in a trie. Starting at each location in the matrix, search the trie for the patterns formed in each direction. On Jan 17, 12:33 pm, Piyush wrote: > Given a MxN char array matrix, find all words in it. search left, right, > diagonally --
[algogeeks] Re: Check simple polygon
Dave is right that Bentley Ottmann is a good choice. It is O(n*log n) which is an improvement over a simplistic approach which would be O(n^2). Do be careful in implementation to ensure that it catches cases where two points are coincident or one edge passes exactly through another vertex. I saw an implementation which worked fine in all other cases but missed polygons which intersected with itself at a vertex. Don On Jan 20, 7:27 pm, Dave wrote: > @Shady: Seehttp://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm. > > Dave > > > > > > > > On Sunday, January 20, 2013 10:02:19 AM UTC-6, shady wrote: > > How to check if polygon is simple based on given list of points ? --
[algogeeks] Re: maximum subsquare such that all four borders are filled black
I'm not sure I understand your case. However, I stated that there are cases where it is worse than O(N^2). The runtime is highly dependent on the contents of the matrix. In many cases it takes fewer than N^2 iterations. Occasionally it takes more. On average it seems to be roughly O(N^2), but again that depends a lot on what is in the matrix. I got that result by trying different ways of filling the matrix. I tried things like randomly setting each pixel with various probabilities, placing random horizontal and vertical segments, placing random squares, or placing random filled squares. I did all of those both in black on white and white on black. In all of those cases, going from n=1000 to n=2000 resulted in a runtime increase of less than a factor of 4. Don On Jan 23, 10:33 pm, bharat b wrote: > @Don: the solution is very nice.. But, how can u prove that it is O(n^2).. > for me it seems to be O(n^3) .. > > Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2). > all 1s from (n/2,0) to (n,0). > > > > > > > > On Thu, Jan 17, 2013 at 9:28 PM, Don wrote: > > The downside is that it uses a bunch of extra space. > > The upside is that it is pretty fast. It only does the time-consuming > > task of scanning the matrix for contiguous pixels once, it only > > searches for squares larger than what it has already found, and it > > doesn't look in places where such squares could not be. In practice it > > performs at O(n^2) or better for most inputs I tried. But if you are > > devious you can come up with an input which takes longer. > > Don > > > On Jan 17, 10:14 am, marti wrote: > > > awesome solution Don . Thanks. > > > > On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti wrote: > > > > > Imagine there is a square matrix with n x n cells. Each cell is either > > > > filled with a black pixel or a white pixel. Design an algorithm to > > find the > > > > maximum subsquare such that all four borders are filled with black > > pixels; > > > > optimize the algorithm as much as possible > > > -- --
[algogeeks] Re: maximum subsquare such that all four borders are filled black
The worst case I know of is when the matrix is solid black except for the lower right quadrant. In this case, it does break down into O(n^3) runtime. It took about 8 times as long to run n=4000 as it took for n=2000. Don On Jan 24, 10:29 am, Don wrote: > I'm not sure I understand your case. However, I stated that there are > cases where it is worse than O(N^2). The runtime is highly dependent > on the contents of the matrix. In many cases it takes fewer than N^2 > iterations. Occasionally it takes more. On average it seems to be > roughly O(N^2), but again that depends a lot on what is in the matrix. > I got that result by trying different ways of filling the matrix. I > tried things like randomly setting each pixel with various > probabilities, placing random horizontal and vertical segments, > placing random squares, or placing random filled squares. I did all of > those both in black on white and white on black. In all of those > cases, going from n=1000 to n=2000 resulted in a runtime increase of > less than a factor of 4. > > Don > > On Jan 23, 10:33 pm, bharat b wrote: > > > > > > > > > @Don: the solution is very nice.. But, how can u prove that it is O(n^2).. > > for me it seems to be O(n^3) .. > > > Ex: nxn matrix .. all 1s from (n/2,0) to (n/2,n/2). > > all 1s from (n/2,0) to (n,0). > > > On Thu, Jan 17, 2013 at 9:28 PM, Don wrote: > > > The downside is that it uses a bunch of extra space. > > > The upside is that it is pretty fast. It only does the time-consuming > > > task of scanning the matrix for contiguous pixels once, it only > > > searches for squares larger than what it has already found, and it > > > doesn't look in places where such squares could not be. In practice it > > > performs at O(n^2) or better for most inputs I tried. But if you are > > > devious you can come up with an input which takes longer. > > > Don > > > > On Jan 17, 10:14 am, marti wrote: > > > > awesome solution Don . Thanks. > > > > > On Thursday, January 17, 2013 12:38:35 AM UTC+5:30, marti wrote: > > > > > > Imagine there is a square matrix with n x n cells. Each cell is either > > > > > filled with a black pixel or a white pixel. Design an algorithm to > > > find the > > > > > maximum subsquare such that all four borders are filled with black > > > pixels; > > > > > optimize the algorithm as much as possible > > > > -- --
[algogeeks] Re: Generating mazes
A few years ago one of my winning entries in the International
Obfuscated C Code Contest generated and let the user solve a 3D maze.
The program below is not obfuscated, and it only generates a 2D maze,
but it illustrates the principle.
The idea is to start with a solid area of wall and then tunnel out the
passageways. From a given point, it tries in a random order to tunnel
in each of the four directions. If it succeeds, it digs a tunnel to
that neighboring location and stores the direction it used to get to
that location, and then continues to tunnel from that new location.
When it gets to a point where it can't tunnel in any direction, it
uses the direction to back out to its previous location. It is not
recursive, like many maze generating programs. It stores it's stack
inside of the maze. The resulting maze could be used to generate a
bitmap image. In this case I just output a text representation.
Don
#include
#include
unsigned int rnd()
{
static unsigned int x = time(0);
x = 63663*(x&65535) + (x>>16);
return x&65535;
}
int main()
{
// Size should be odd
const int size = 199;
char m[size][size];
int i,j,d,x,y,tmp,order[4] = {0,1,2,3};
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
enum markers { passage=4, start=5, wall=6 };
// Fill area solid
for(i = 0; i < size; ++i)
for(j = 0; j < size; ++j)
m[i][j] = wall;
for(i = 0; i < size; ++i)
m[i][0] = m[0][i] = m[i][size-1] = m[size-1][i] = passage;
// Select starting location
i = j = (size/2) & 0xfffe;
m[i][j] = start;
// Dig tunnels
while(1)
{
// Permute directions
for(x = 1; x < 4; ++x)
{
y = rnd() % (x+1);
tmp = order[x];
order[x] = order[y];
order[y] = tmp;
}
// Try directions in selected order
for(d = 0; d < 4; ++d)
{
x = dir[order[d]][0]];
y = dir[order[d]][1]];
if (m[i+2*x][j+2*y] == wall)
{
m[i+x][j+y] = passage;
i += 2*x;
j += 2*y;
m[i][j] = order[d];
break;
}
}
// Nowhere to go. Back out.
if (d == passage)
{
x = m[i][j];
m[i][j] = passage;
if (x == start) break; // Done
i -= 2*dir[x][0];
j -= 2*dir[x][1];
}
}
// Start and end
m[2][1] = m[size-3][size-2] = passage;
// Print result
for(i = 0; i < size; ++i)
{
for(j = 0; j < size; ++j)
printf("%c", (m[i][j] == wall) ? '#' : ' ');
printf("\n");
}
return 0;
}
On Jan 29, 6:51 pm, Dave wrote:
> Does anyone have any ideas about how to generate mazes? I'd like an
> algorithm that can make many different mazes, maybe using a random number
> generator. Each maze should be guaranteed to have one and only one solution.
--
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.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Generating mazes
A few years ago one of my winning entries in the International
Obfuscated C Code Contest generated and let the user solve a 3D maze.
The program below is not obfuscated, and it only generates a 2D maze,
but it illustrates the principle.
The idea is to start with a solid area of wall and then tunnel out the
passageways. From a given point, it tries in a random order to tunnel
in each of the four directions. If it succeeds, it digs a tunnel to
that neighboring location and stores the direction it used to get to
that location, and then continues to tunnel from that new location.
When it gets to a point where it can't tunnel in any direction, it
uses the direction to back out to its previous location. It is not
recursive, like many maze generating programs. It stores it's stack
inside of the maze. The resulting maze could be used to generate a
bitmap image. In this case I just output a text representation.
Don
===
#include
#include
unsigned int rnd()
{
static unsigned int x = time(0);
x = 63663*(x&65535) + (x>>16);
return x&65535;
}
int main()
{
// Size should be odd
const int size = 199;
char m[size][size];
int i,j,d,x,y,tmp,order[4] = {0,1,2,3};
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
enum markers { passage=4, start=5, wall=6 };
// Fill area solid
for(i = 0; i < size; ++i)
for(j = 0; j < size; ++j)
m[i][j] = wall;
for(i = 0; i < size; ++i)
m[i][0] = m[0][i] = m[i][size-1] = m[size-1][i] = passage;
// Select starting location
i = j = (size/2) & 0xfffe;
m[i][j] = start;
// Dig tunnels
while(1)
{
// Permute directions
for(x = 1; x < 4; ++x)
{
y = rnd() % (x+1);
tmp = order[x];
order[x] = order[y];
order[y] = tmp;
}
// Try directions in selected order
for(d = 0; d < 4; ++d)
{
x = dir[order[d]][0];
y = dir[order[d]][1];
if (m[i+2*x][j+2*y] == wall)
{
m[i+x][j+y] = passage;
i += 2*x;
j += 2*y;
m[i][j] = order[d];
break;
}
}
// Nowhere to go. Back out.
if (d == passage)
{
x = m[i][j];
m[i][j] = passage;
if (x == start) break; // Done
i -= 2*dir[x][0];
j -= 2*dir[x][1];
}
}
// Start and end
m[2][1] = m[size-3][size-2] = passage;
// Print result
for(i = 0; i < size; ++i)
{
for(j = 0; j < size; ++j)
printf("%c", (m[i][j] == wall) ? '#' : ' ');
printf("\n");
}
return 0;
}
On Jan 29, 6:51 pm, Dave wrote:
> Does anyone have any ideas about how to generate mazes? I'd like an
> algorithm that can make many different mazes, maybe using a random number
> generator. Each maze should be guaranteed to have one and only one solution.
--
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.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Generating mazes
It is George Marsaglia's multiply with carry pseudo-random number generator. It has a period of 2^32, which is long enough for this purpose. It is about as good as a 32-bit rng can be. In real life I use the Mersenne Twister, but I wanted something simple to include here. Don On Jan 29, 11:46 pm, Piyush Grover wrote: > @Don can you give the logic of your rnd() function? -- 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. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: GATE-2011 Question
You have to identify the bottleneck in the pipeline. The time required for the bottleneck is the steady state time per operation of the pipelined processing. Then determine the time to do the 4 stages sequentially. The difference is the speed up. Don On Jan 30, 11:59 am, Ayush Kapoor wrote: > Consider an instruction pipeline with four stages (S1, S2, S3 and S4) each > with combinational circuit only. The pipeline registers are required > between each stage and at the end of the last stage. Delays for the stages > and for the pipeline registers are as given in the figure. > > What is the approximate speed up of the pipeline in steady state under > ideal conditions when compared to the corresponding non-pipeline > implementation? [2 marks] > (A) 4.0 > (B) 2.5 > (C) 1.1 > (D) 3.0 > > Answer to this question is 2.5 > Can anybody explain me how to solve this question? -- 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. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: size of array
There is not a sure way to do that in C or C++ without putting an additional requirement on the caller. Don On Jan 28, 5:14 am, Anil Sharma wrote: > How to calculate the size/lenght of an int array which is passed as an ONLY > argument to a function??? -- 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. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: GATE-2011 Question
The problem references a figure which I don't think you have provided, and I don't know what A,B,C,D are or how they relate to S1, S2, S3, S4 so I can't solve the problem. But the principle is to find the one stage which has the lowest throughput. That is the bottleneck. The pipeline can't process any faster than that stage. The problem asks for the speedup, so you need to know how long it would take to do the 4 stages sequentially, which would just be the sum of the time for the four stages. The difference between those two is the speedup. Don On Jan 31, 2:55 am, Ayush Kapoor wrote: > Can you please elaborate your answer ... ? > > > > > > > > > > On Wed, Jan 30, 2013 at 10:37 PM, Don wrote: > > You have to identify the bottleneck in the pipeline. The time required > > for the bottleneck is the steady state time per operation of the > > pipelined processing. Then determine the time to do the 4 stages > > sequentially. The difference is the speed up. > > > Don > > > On Jan 30, 11:59 am, Ayush Kapoor wrote: > > > Consider an instruction pipeline with four stages (S1, S2, S3 and S4) > > each > > > with combinational circuit only. The pipeline registers are required > > > between each stage and at the end of the last stage. Delays for the > > stages > > > and for the pipeline registers are as given in the figure. > > > > What is the approximate speed up of the pipeline in steady state under > > > ideal conditions when compared to the corresponding non-pipeline > > > implementation? [2 marks] > > > (A) 4.0 > > > (B) 2.5 > > > (C) 1.1 > > > (D) 3.0 > > > > Answer to this question is 2.5 > > > Can anybody explain me how to solve this question? > > > -- > > 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. > > For more options, visithttps://groups.google.com/groups/opt_out. > > -- > Ayush -- 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. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Crypt arithmetic!! Needed help in solving..
I'm not going to solve it for you. Use logic to figure out what values certain letters must have and keep plugging away until you know them all. On Feb 1, 3:10 am, nikhil rao wrote: > Pls help needed in solving the below problem.. > > 1 )MULTIPLICATION TYPE > > A B C * D E C > > F G H > I A C * > A C A E * * > > A F A E C H > > 2. > > P X B * W Y A > > O A Z O > O N X W * > O X N P * * > - > O X N Z N O -- 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. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: perfect square condition checking....
The following is a bit faster than the Newton's Method solution I
suggest above. It uses a binary square root algorithm as seen here:
http://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Binary_numeral_system_.28base_2.29
The value is a perfect square if x ends up being zero.
bool isSqr(unsigned int x)
{
unsigned int res = 0;
unsigned int bit = 1 << 30;
while(bit > x) bit >>= 2;
while(bit)
{
if (x >= res + bit)
{
x -= res + bit;
res = (res >> 1) + bit;
}
else
{
res >>= 1;
}
bit >>= 2;
}
return (x == 0);
}
On Dec 23 2012, 10:37 am, Anil Sharma
wrote:
> please suggest some efficient solution to check perfect square condition .
> no matter how much large number is... eg..i/p-8949 o/p-93
--
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.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Generating mazes
I believe that this will generate a maze with multiple cycles, which violates the requirement stated in the initial question that the maze have exactly one solution. On Feb 6, 11:53 am, Anup Ghatage wrote: > There is another algorithm.. The one which involves random division. > > Basically, given an M x N matrix > > > |...| > |...| > |...| > |...| > |...| > |...| > |...| > |...| > |...| > |...| > |...| > > Draw a random line intersecting the maze vertically, then draw another > random line intersecting it horizontally. > > > |.|.| > |.|.| > |.|.| > |.|.| > |__.|.| > |.|.| > |.|.| > |.|.| > |.|.| > |.|.| > |.|.| > > Now since you've got a 'plus' like formation of the two new lines, create > an opening on each of the new intersecting lines, one on each side of the > intersect > > > |.|.| > |.|.| > |...| > |..|| > |_____|___..__| > |.|.| > |.|.| > |.|.| > |...| > |.|.| > |.|.| > > Now you've got 4 new matrices, recursively go ahead drawing more > intersecting lines on them such that the new ones don't have one end point > in the open. > > Regards > > > > > > > > > > On Wed, Jan 30, 2013 at 8:19 PM, Don wrote: > > It is George Marsaglia's multiply with carry pseudo-random number > > generator. It has a period of 2^32, which is long enough for this > > purpose. It is about as good as a 32-bit rng can be. In real life I > > use the Mersenne Twister, but I wanted something simple to include > > here. > > > Don > > > On Jan 29, 11:46 pm, Piyush Grover wrote: > > > @Don can you give the logic of your rnd() function? > > > -- > > 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. > > For more options, visithttps://groups.google.com/groups/opt_out. > > -- > Anup Ghatagewww.ghatage.com -- 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. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Generating mazes
I think that your method would work if you only put an opening on 3 of the four arms of the "plus". Don On Feb 8, 9:55 pm, Anup Ghatage wrote: > Hm. Then a way to look at it is like this: > > Find a way. Find n-1 other ways which are not the solution. > > You can use a random path generating algorithm, starting from one side, > selecting a random cell from the possible 8 cell neighborhood, and then > repeating the process till you get to the end. This will give you the only > correct, random path. > > Now it is a matter of creating n-1 other random paths which are not the > solution in a similar fashion. > The beauty is that they will intersect each other as the number increases > and will increase complexity in the process. > > > > > > > > > > On Fri, Feb 8, 2013 at 3:51 AM, Don wrote: > > I believe that this will generate a maze with multiple cycles, which > > violates the requirement stated in the initial question that the maze > > have exactly one solution. > > > On Feb 6, 11:53 am, Anup Ghatage wrote: > > > There is another algorithm.. The one which involves random division. > > > > Basically, given an M x N matrix > > > > > > > |...| > > > |...| > > > |...| > > > |...| > > > |...| > > > |...| > > > |...| > > > |...| > > > |...| > > > |...| > > > |...| > > > > Draw a random line intersecting the maze vertically, then draw another > > > random line intersecting it horizontally. > > > > > > > |.|.| > > > |.|.| > > > |.|.| > > > |.|.| > > > |__.|.| > > > |.|.| > > > |.|.| > > > |.|.| > > > |.|.| > > > |.|.| > > > |.|.| > > > > Now since you've got a 'plus' like formation of the two new lines, create > > > an opening on each of the new intersecting lines, one on each side of the > > > intersect > > > > > > > |.|.| > > > |.|.| > > > |...| > > > |..|| > > > |_____|___..__| > > > |.|.| > > > |.|.........| > > > |.|.| > > > |...| > > > |.|.| > > > |.|.| > > > > Now you've got 4 new matrices, recursively go ahead drawing more > > > intersecting lines on them such that the new ones don't have one end > > point > > > in the open. > > > > Regards > > > > On Wed, Jan 30, 2013 at 8:19 PM, Don wrote: > > > > It is George Marsaglia's multiply with carry pseudo-random number > > > > generator. It has a period of 2^32, which is long enough for this > > > > purpose. It is about as good as a 32-bit rng can be. In real life I > > > > use the Mersenne Twister, but I wanted something simple to include > > > > here. > > > > > Don > > > > > On Jan 29, 11:46 pm, Piyush Grover wrote: > > > > > @Don can you give the logic of your rnd() function? > > > > > -- > > > > You received this message because you are subscribed to the Google > > Groups > > > > "Algorithm Geeks" group. > > > > To unsubscribe from this group
[algogeeks] Re: Amazon Interview Question
The xor approach only works if there are no values which occur only
once. But the problem statement indicates that some numbers occur
once, some occur twice, and one occurs three times. So you will end up
with prod equal to the xor of all of the values which occur once or
three times. Put that in your input array and you'll find that you
don't get the desired output.
I don't know of a solution better than sorting and scanning the array.
Don
On Feb 12, 3:14 pm, prakhar singh wrote:
> #include
>
> int main()
> {
> int a[] = {2,2,3,3,3,1,1,4,4}; // is this correct?
> int prod=a[0];int i;
> for(i=1;i<(int)sizeof(a)/sizeof(a[0]);i++)
> {
> prod ^= a[i];
> }
> printf("%d\n",prod); //outputs 3, algorithm works as Sachin described
> it;
>
> }
>
> On Tue, Feb 12, 2013 at 11:44 PM, Sachin Chitale
> wrote:
>
>
>
>
>
>
>
> > use ex-or operation for all array elements..
> > a^a=0
> > a^a^a=a
>
> > On Sun, Feb 10, 2013 at 8:22 AM, Mohanabalan D B
> > wrote:
>
> >> can use counting sort
>
> >> On Sun, Jul 15, 2012 at 6:37 PM, santosh thota
> >> wrote:
>
> >>> If we can retrieve ith prime efficiently, we can do the following...
> >>> 1.maintain a prod=1, start from 1st element, say a[0]=n find n th prime
> >>> 2.check if (prod% (ith_prime * ith_prime )==0) then return i;
> >>> else prod=prod*ith_prime;
> >>> 3.repeat it till end
>
> >>> On Thursday, 12 July 2012 10:55:02 UTC+5:30, algo bard wrote:
>
> >>>> Given an array of integers where some numbers repeat once, some numbers
> >>>> repeat twice and only one number repeats thrice, how do you find the
> >>>> number
> >>>> that gets repeated 3 times?
>
> >>>> Does this problem have an O(n) time and O(1) space solution?
> >>>> No hashmaps please!
>
> >>> --
> >>> 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/-/TSPSKlD0FDsJ.
>
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from 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 unsubscribe from this group and stop receiving emails from it, send an
> >> email to algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visithttps://groups.google.com/groups/opt_out.
>
> > --
> > Regards,
> > Sachin Chitale
> > Application Engineer SCJP, SCWCD
> > Contact# : +91 8086284349, 9892159511
> > Oracle Corporation
>
> > --
> > 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.
> > For more options, visithttps://groups.google.com/groups/opt_out.
--
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.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Number of paths
The problem can't be solved without specifying what the legal moves are. Solutions have been given for the case where the only moves are down and right. However, if other moves are allowed the result will be different, and if cycles are allowed the answer could be infinite. Stating problems precisely is very important. BFS is not a workable solution. For any matrix larger than about 10x10 it will take longer than you want to wait. Don On Feb 21, 2:56 am, shady wrote: > Given a matrix of size mXn, find the number of paths from the top left cell > to the bottom right cell. > > BFS is one way... any other approach ? -- 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. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: separate coins into heaps of similar weights using balance in minimum comparisons
I don't see how a statement like "3 coins together weigh x kg" provides any new information. Using a binary search algorithm you should be able to find any coins which weigh the same in 17 comparisons in the worse case. On Mar 2, 12:42 am, Shubham Sandeep wrote: > @dave you are correct but language of question implies---> out of 8 coins 3 > taken together weigh x,again 3 coins taken out of 8 have y as weight . This > shows that one or more coins out of 3 (weight x) may be same as those > considered for weight y as so on for z and w. > > > > > > > > > > On Sat, Mar 2, 2013 at 2:39 AM, Dave wrote: > > @Maddy: I'm a little confused because there are 8 coins in the bag but 3 + > > 3 + 2 + 2 = 10 coins are grouped by weight. > > > Dave > > > On Friday, March 1, 2013 1:15:03 PM UTC-6, maddy wrote: > > >> There are 8 coins in a bag . > >> 3 coin weights x kg > >> 3 coins weights y kg > >> 2 coins weights z kg > >> 2 coins weights w kg > >> You have to separate them into separate heaps according to > >> their weights in minimum comparisons using weighing balance. > > >> -- > >> Regards, > >> SHUBHAM SANDEEP > >> IT 3rd yr. > >> NIT ALD. > > > -- > > 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. > > For more options, visithttps://groups.google.com/groups/opt_out. > > -- > Regards, > SHUBHAM SANDEEP > IT 3rd yr. > NIT ALD. -- 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. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: facebook programming question
Move all equal objects to the median location of those objects.
So if you have
{5,5,1,5,1,1,1,5,1,5}
Then we would move the fives to index 3 and the 1's to index 5.
Why? Consider any candidate position to place a collection of objects.
If there are x more objects to the left of that position than to the
right, we could reduce the total moves by x simply by moving the
position one to the left. We could continue reducing the moves until
there are an equal number of objects to the left as to the right. That
position is the median of that subset of objects.
So to get the result they are asking for, you have to find the median
location for each distinct value in the array and find the sum of the
differences between each value and the median.
I would consider using a map to store the locations indexed by value.
Then iterate over the map and process each set of locations one by
one.
Don
On Mar 23, 4:59 am, rakesh kumar wrote:
> > There are N objects kept in a row. The ith object is at position x_i. You
> > want to partition them into K groups. You want to move all objects
> > belonging to the same group to the same position. Objects in two different
> > groups may be placed at the same position. What is the minimum total amount
> > by which you need to move the objects to accomplish this?
>
> > Input:
> > The first line contains the number of test cases T. T test cases follow.
> > The first line contains N and K. The next line contains N space seperated
> > integers, denoting the original positions x_i of the objects.
>
> > Output:
> > Output T lines, containing the total minimum amount by which the objects
> > should be moved.
>
> > Constraints:
> > 1 <= T <= 1000
> > 1 <= K <= N <= 200
> > 0 <= x_i <= 1000
>
> > Sample Input:
> > 3
> > 3 3
> > 1 1 3
> > 3 2
> > 1 2 4
> > 4 2
> > 1 2 5 7
>
> > Sample Output:
> > 0
> > 1
> > 3
>
> > Explanation:
>
> > For the first case, there is no need to move any object.
> > For the second case, group objects 1 and 2 together by moving the first
> > object to position 2.
> > For the third case, group objects 1 and 2 together by moving the first
> > object to position 2 and group objects 3 and 4 together by moving object 3
> > to position 7. Thus the answer is 1 + 2 = 3.
>
> > I thought of sorting the array and then calculating difference but no
> > success.Please help
--
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.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Get Target
Use a backtracking search to build a prefix expression. If there are
two more operands than operators in the expression, the next item
could be either an operand or an operator. Otherwise, it must be an
operand.
In very loose pseudocode:
search(int target, list operands, stack opStack, string expression)
{
if ((operands.size() == 0) && (opStack.size() == 1) &&
(opStack.top() == target))
output (expression);
// Try adding each operand next in the expression
for(op = operands.begin(); op != operands.end(); ++op)
{
list nextOps = operands;
nextOps.remove(op);
opStack.push(op);
search(target, nextOps, nextStack, expression+op);
opStack.pop();
}
// Try each operator
if (opStack.size() >= 2)
{
int b = opStack.pop();
int a = opStack.pop();
opStack.push(a+b);
search(target, operands, opStack, expression + "+");
opStack.pop();
opStack.push(a-b);
search(target, operands, opStack, expression + "-");
opStack.pop();
opStack.push(a*b);
search(target, operands, opStack, expression + "*");
opStack.pop();
opStack.push(a/b);
search(target, operands, opStack, expression + "/");
opStack.pop();
opStack.push(a);
opStack.push(b);
}
}
On Mar 21, 8:57 pm, prankur gupta wrote:
> Hi All,
>
> Could you help me this question.
> This was asked at Yelp Interview.
>
> Given 6 integers and 1 target value, write a function to get the target
> value using 6 integers with any on these operations +,*,-,/
>
> Thanks
>
> --
> PRANKUR GUPTA
>
> Masters Student (CSE)
> State University of New York
> Stony Brook University
> prgu...@cs.stonybrook.edu
--
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.
For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: how to solve this?
Simplify the expression by evaluating expressions inside parenthesis first. Follow the order of evaluation, doing multiplications first and then addition and subtraction. It should be possible to reduce any expression to the form ax+b=0. Then x=-b/a. Don On Apr 4, 11:18 am, arun kumar wrote: > Given an expression in the form of a string, solve for x. The highest power > of x in the expression will be equal to 1. Operators allowed are +, * and > -. These are all binary operators. So, 2x would be written as 2*x. Every > operator will be followed by a single term or a constant. > > For example, consider the following equation: > > 2*x+5-(4*x-7+(4-2))=10*x-9 Given such an equation, we need to find a > solution to x -- 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. For more options, visit https://groups.google.com/groups/opt_out.
[algogeeks] Re: Probability Puzzle
The answer is 17 in 18, because flipping 5 heads in a row is evidence that the probability is high that we have the coin with two heads. Don On Aug 7, 12:34 pm, Algo Lover wrote: > A bag contains 5 coins. Four of them are fair and one has heads on > both sides. You randomly pulled one coin from the bag and tossed it 5 > times, heads turned up all five times. What is the probability that > you toss next time, heads turns up. (All this time you don't know you > were tossing a fair coin or not). -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Probability Puzzle
Consider the 5 * 64 possible outcomes for the selection of coin and six flips, each one happening with equal probability. Of those 320 possible outcomes, 4*62 are excluded by knowing that the first 5 flips are heads. That leaves 64 outcomes with the rigged coin and 2 outcomes with each of the fair coins, for a total of 72 outcomes. 68 of those are heads, so the answer to the puzzle is 68 of 72, or 17 of 18. Don On Aug 8, 2:36 am, Shachindra A C wrote: > @brijesh > > *first five times* is mentioned intentionally to mislead i think. I vote for > 3/5. Moreover, 17/80 doesn't make sense also. Plz correct me if I am wrong. > > > > On Mon, Aug 8, 2011 at 12:06 PM, sumit gaur wrote: > > (3/5) > > > On Aug 7, 10:34 pm, Algo Lover wrote: > > > A bag contains 5 coins. Four of them are fair and one has heads on > > > both sides. You randomly pulled one coin from the bag and tossed it 5 > > > times, heads turned up all five times. What is the probability that > > > you toss next time, heads turns up. (All this time you don't know you > > > were tossing a fair coin or not). > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from 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, > Shachindra A C -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: what is complexity of func(p)
I don't think that this function is doing what you want it to do. If
you ask for a^b, it returns a^1 in most cases.
Try this instead.
int power(int a, int b)
{
int result = 1;
if (b == 1) result = a;
else if (b>1)
{
result = power(a,b/2);
result *= result;
if (b%2) result *= a;
}
return result;
}
On Aug 8, 10:37 pm, rohit wrote:
> int get_power(int a, int b)
> {
> if(!b)
> return 1;
> if(b%2)
> return a * get_power(a, b/2);
> return get_power(a, b/2);
> }
>
> int func(int p)
> { int sum = 0;
> for(int i = 1; i <= p; ++i)
> {
> sum += get_power(i, 5);}
>
> return sum;
>
> }
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: need a pgm pls help me
#include
#include
int main()
{
char inFileName[80];
char outFileName[80];
int numSegments;
int bytesPerSegment;
printf("Enter file name:");
fgets(inFileName,80,stdin);
printf("Enter number of segments:");
scanf("%d", &numSegments);
FILE *f = fopen(inFileName, "rb");
if (!f) return 0;
// Get size of file to determine bytes per file segment
fseek(f, 0, SEEK_END);
int bytesPerSegment = 1 + (ftell(f) / numSegments);
fseek(f,0,SEEK_SET);
char *buffer = (char *)malloc(bytesPerSegment);
for(int segment = 0; segment < numSegments; ++segment)
{
sprintf(outFileName,"%s%d", inFileName,segment);
FILE *out = fopen(outFileName,"wb");
int len=fread(buffer, bytesPerSegment, 1, f);
fwrite(buffer, len, 1, out);
fclose(out);
}
return 1;
}
On Aug 9, 7:28 am, Divya Elangovan wrote:
> pls help me..its very urgent
>
> need a program to divide a file into equal parts(segments)
>
> --
>
> *
> **
> *
> * ** **DIVI*
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Closest ancestor of two nodes
tree closestSharedAncestor(tree root, tree node1, tree node2, int
&result)
{
tree returnValue = 0;
if (root)
{
if (root == node1) result += 1;
if (root == node2) result += 2;
int sum = 0;
tree returnLeft = closestSharedAncestor(root->left, node1, node2,
sum);
if (returnLeft) returnValuet = returnLeft;
else
{
tree returnRight = closestSharedAncestor(root->right, node1,
node2, sum);
if (returnRight) returnValue = returnRight;
else if (sum == 3) returnValue = root;
}
result += sum;
}
return returnValue;
}
On Aug 9, 9:56 am, Raman wrote:
> Can anyone give me the recursive algo to find closest ancestor of two nodes
> in a tree(not a BST).
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: suggest simple code for
int depth(node *root)
{
return root ? max(depth(root->left), depth(root->right)) : 0;
}
On Aug 8, 8:03 am, jagrati verma wrote:
> finding the depth or height of a tree.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: suggest simple code for
int depth(node *root)
{
return root ? 1+max(depth(root->left), depth(root->right)) : 0;
}
On Aug 8, 8:03 am, jagrati verma wrote:
> finding the depth or height of a tree.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: suggest simple code for
I do love functions that start with "return".
Don
On Aug 10, 10:09 am, Dave wrote:
> @Don: Beautiful!
>
> Dave
>
> On Aug 10, 10:03 am, Don wrote:
>
> > int depth(node *root)
> > {
> > return root ? 1+max(depth(root->left), depth(root->right)) : 0;
>
> > }
>
> > On Aug 8, 8:03 am, jagrati verma wrote:
>
> > > finding the depth or height of a tree.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Problems on Linked List
Q1: The function below reverses a linked list in place. Call it on one
of the lists, compare the resulting list to the other list. Then call
it again to put the list back in its original order.
list Reverse(list head)
{
list T, prv, nxt;
prv = head;
for(T = head->next; T; T = nxt)
{
nxt = T->next;
T->next = prv;
prv = T;
T = nxt;
}
head->next = 0;
return prv;
}
Q2:
delete(node *d)
{
if (d->next)
{
node nxt = d->next;
d->value = nxt->value;
d->next = nxt->next;
free nxt;
}
else
{
for(node p = head; p; p = p->next)
if (p->next == d)
{
p->next = 0;
free d;
}
}
}
On Aug 10, 1:14 pm, Piyush Kapoor wrote:
> Q1)Two linked Lists are given,i.e,their head pointers are given,and the
> problem is to check if the second one is reverse of the first one.Give the
> most efficient algo for it.
> Q2)A linked list is given,and one of its nodes is given.The problem is to
> delete the given node from the linked list.(The head node is not given).
> (In both of the above cases,the linked lists are singly linked lists.)
> --
> *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.
[algogeeks] Re: Design a concurrent hash table
Sounds like you need some sort of semaphore system to lock cells in the hash table. Essentially it would only give one user access to a particular cell at any given time. Make sure that the cells have a restricted interface so that they can only be accessed through the semaphore-controlled interface. The write interface would attempt to get the semaphore, and if successful, write the data and then release the semaphore. If it failed, it would return a failure notice to the caller. The read interface would check the semaphore and if it was open, get the data. Don On Aug 11, 5:15 am, Navneet Gupta wrote: > Q. Design a concurrent hash table with as much as concurrency as possible. > System has multiple readers and writers. System will crash if a reader or > writer is reading or writing from a location which is being updated by some > writer. We need to prevent crash. > > It is pretty much an open-ended question, so basically looking for > strategies. > > -- > Regards, > Navneet -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Jumping Puzzle
int A[100];
int dist[100];
int N;
void findDist(int p, int d)
{
if (d < dist[p])
{
dist[p] = d;
for(int i = 0; i < p; ++i)
if ((i+A[i]) >= p)
findDist(i,d+1);
}
}
int main(int argc, char* argv[])
{
int i;
int location = 0;
printf("Number of elements:");
scanf("%d", &N);
for(i = 0; i < N; ++i)
{
printf("Element %d:", i);
scanf("%d",&A[i]);
}
for(i = 0; i < N; ++i)
dist[i] = N;
findDist(N-1, 0);
for(i = 1; i < N; ++i)
if (dist[i] == (dist[location]-1))
{
printf("Move %d to location %d\n", i-location, i);
location = i;
}
return 0;
}
On Aug 11, 3:07 am, Algo Lover wrote:
> Given an array, start from the first element and reach the last by
> jumping. The jump length can be at most the value at the current
> position in the array. Optimum result is when you reach the goal in
> minimum number of jumps.
>
> For ex:
> Given array A = {2,3,1,1,4}
> possible ways to reach the end (index list)
> i) 0,2,3,4 (jump 2 to index 2, then jump 1 to index 3 then 1 to index
> 4)
> ii) 0,1,4 (jump 1 to index 1, then jump 3 to index 4)
>
> Since second solution has only 2 jumps it is the optimum result.
>
> My solution is for any index i loop from i to i + A[i]
> find an index j where
> (j + A[j]) is maximum for all j.
> make i=j;
>
> This solution in O(n) i suppose coz we are picking each element twice
> in the worst case.
>
> I have read a O(n^2) DP solution for this problem.Is there any
> case where my approach will fail ?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: reverse
What exactly do you mean by "reverse a number?" Please define what that means and give an example. Don On Aug 11, 12:13 pm, Rajeshwar Patra wrote: > how can we reverse a number using bitwise operators? > > -- > *Rajeshwar Patra,* > *MCA final year,* > *Nit Durgapur* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Math Quiz
2 On Aug 11, 1:26 pm, Mani Bharathi wrote: > ABCD is a parallelogram and E is the middle point of side AD EC meets BD at > O. If the area if the parallelogram is 24 units then the area of EOD is ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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
Yes. Linear probing, if done in the usual way, will end up at 2 if the hash function returned values 1,2,7,8, 9, or 10. That is 6 of the 10 possible values, so if each one is equally likely, the probability is 0.6. Don On Aug 11, 3:04 pm, aditi garg wrote: > cud u xplain how? > > On Thu, Aug 11, 2011 at 11:31 PM, Tarun Arya wrote: > > Rajeev sir, > > 0.6 is correct :) > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > -- > Aditi Garg > Undergraduate Student > Electronics & Communication Divison > NETAJI SUBHAS INSTITUTE OF TECHNOLOGY > Sector 3, Dwarka > New Delhi -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Non recursive preorder and postorder
It can be done without using a stack, by using the pointers in the node to keep track of the path back up the tree. The algorithm will temporarily modify the tree, but when completed the tree will be restored to its original state. Don On Aug 15, 8:07 am, rohit wrote: > Can anyone give algorithm for non recursive preorder and postorder?? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: program puzzle
#include
#include
int main(int argc, char* argv[])
{
char line[500];
char tmp[500];
char *words[100];
int wordCount = 0;
char *p, *wordStart=0;
printf("Enter string:");
fgets(line,500,stdin);
for(p = line; *p; ++p)
{
if (!wordStart && isalpha(*p)) wordStart = p;
else if (wordStart && !isalpha(*p))
{
words[wordCount++] = wordStart;
*p = 0;
wordStart = 0;
}
}
p = tmp;
for(int i = wordCount-1; i >= 0; --i) p += sprintf(p, "%s ",
words[i]);
strcpy(line,tmp);
printf(">%s<\n", line);
return 0;
}
On Aug 15, 6:18 am, programming love
wrote:
> write a program to reverse the words in a give string.
> also state the time complexity of the algo.
>
> if the string is "i am a programmer"
> the output should be "programmer a am i"
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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] Prime numbers
I wrote a program to print prime numbers, but it is not very fast. Can
someone help me figure out why?
#include
/* This program implements a blindingly fast algorithm
to find prime numbers, using an elegant recursive method. */
int _(int n, int m, int d, int t=0)
{
int r;
if (t) return d?1+_(n,m,d-1,d):n?_(n-1,m,m,n):0;
for(r=m!=n; d*(thttp://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Prime numbers
I wrote it. Can you figure out how it works?
Don
On Aug 17, 1:25 am, Nitin Nizhawan wrote:
> Hi Dod,
>
> Could you pls expalin what this algorithm is doing and from where you got
> it.
>
> Thanks
> Nitin
>
> On Wed, Aug 17, 2011 at 2:56 AM, Don wrote:
> > I wrote a program to print prime numbers, but it is not very fast. Can
> > someone help me figure out why?
>
> > #include
>
> > /* This program implements a blindingly fast algorithm
> > to find prime numbers, using an elegant recursive method. */
> > int _(int n, int m, int d, int t=0)
> > {
> > int r;
> > if (t) return d?1+_(n,m,d-1,d):n?_(n-1,m,m,n):0;
> > for(r=m!=n; d*(t > r &= _(n,_(t,m,0,1),d-1)|!_(t,1,t);
> > return r*n;
> > }
>
> > /*--
> > Print primes up to the requested value
> > */
> > int main(int argc, char* argv[])
> > {
> > for(int n = 2; n <= 1000; n++)
> > printf("%d is%s prime\n",n, _(n,1,n,0)?"":" not");
>
> > 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.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Prime numbers
_(n,1,n,0) is true if n is prime. I set out to create an O(n^n) algorithm. It essentially computes the product of every possible set of n integers in the range (1..n-1). If any of those products equal n, the number is composite. You will notice that the program does not use the * operator to perform a multiplication. It does use * as a logical AND, but to do the products it uses a recursive call with t=1, which is a flag to tell _ to do multiplication instead of determining if n is prime. It does the multiplication by recursively adding up m*n ones. As a result, it takes billions of recursive calls to determine that 6 is not prime. Don On Aug 17, 10:33 am, Sanjay Rajpal wrote: > @Don : can you plz explain it ? > > Sanjay Kumar > B.Tech Final Year > Department of Computer Engineering > National Institute of Technology Kurukshetra > Kurukshetra - 136119 > Haryana, India -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: an amazing amazon question!
Actually you are all wrong. His uniform speed was zero, and he was sitting by milestone 44 the whole time. On Aug 17, 11:58 am, priya ramesh wrote: > A car is traveling at a uniform speed.The driver sees a milestone showing a > 2-digit number. After traveling for an hour the driver sees another > milestone with the same digits in reverse order.After another hour the > driver sees another milestone containing the same two digits. What is the > average speed of the driver? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: brain teaser
We know that n+m+s+carry < 10. So n<7. We also know that either n+n+n or o+o+o > 9 because there must be a carry to make those two columns add to a different value. We can start eliminating values for n. If n is 1, o would have to be 7 to make the second row work out. But then u and e would both be 3. If n is 3, o must be 1, so u would also be 3. If n is 4, o must be 1 and u must be 3, which makes n+m+s > 9. If n=5, then e would be 5, so n can't be 5. If n is larger than 5, there is no combination which makes n+m+s<10. That leaves n=2. It follows that e=6, o=4, and u=3. m and s are interchangeable: 1 and 5. And j is 9. 2442+1442+5442=9326 Don On Aug 17, 1:23 pm, priya ramesh wrote: > noon > + moon > + soon > = june > > find the values of the alphabets to satisfy this equation -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: apti! solve this!
Are we assuming a flat earth? On Aug 17, 9:13 am, priya ramesh wrote: > A moves 3 kms east from his starting point . He then travels 5 kms north. > From that point he moves 8 kms to the east.How far is A from his starting > point? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Need to Hire an algorithm expert for a one time assignment
Why not post your questions, one per thread, and let people discuss it? Don On Aug 18, 7:41 am, maxpayne wrote: > Hi, > > I need help from some one who is really good at algorithms to finish > an assignment. I am a freelancer (not a student, so don't expect > homework problems) based in Singapore and unfortunately I do not have > a back ground in algorithms. I will really appreciate it if some one > in this group can spare an hour or so to give me some expert advice. > The problems will be more along the lines of those asked in popular > coding competitions (think TopCoder, ACM, Project Euler etc). Kindly > write back to me at aquarian.thun...@gmail.com (for details) if you > are interested and can spare an hour or so. > > thanks, > Max -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: knight's tour - variant
1.0. A knight's only legal move is to remain on the board. On Aug 17, 10:27 am, Seshumadhav Chaturvedula wrote: > what is the probability that a knight will stay on a K X K chess board after > 'n' steps ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: calculate a/b without using ‘*’, ‘/’’ and ‘%’
exp(ln(a)-ln(b)) On Aug 18, 8:56 am, radha krishnan wrote: > how to do using BIT manipulation ? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: question on fork()
// DO NOT RUN THIS! By inspection, how many times will it print "Hello
world"?
// If you find out by running it, that is cheating. Don't do it!
int main()
{
int i=0, j=0;
for(i = 0; i*j < 20; ++i)
{
if (fork() > 0) ++j;
else i = j = 0;
printf("Hello world\n");
}
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.
[algogeeks] Re: C code scanf problem
The problem is that scanf("%c" will take whatever character is next,
even if it is not the one you think you typed. When you typed your
first entry, the number "3" and then pressed "Return", the "\n"
character is left in the buffer, so your scanf gets that character
instead of the one you want. The space in front of the %c causes scanf
to skip whitespace and give you the next non-whitespace character.
In general, using scanf is not a reliable way to read input. There may
be some cases where it is adequate, but there are much more robust
ways. For example, use fgets to read an entire line of input and then
parse it using sscanf or just by looking at the characters one at a
time. In your case, you would read in the first line and use sscanf to
extract the numeric value, and then read in the second line and scan
through it until you find a valid character.
However you do it, make sure to have some error checking to verify
that you end up with something valid, in this case I think you would
want to verify that it was a valid variable name.
Don
On Aug 24, 9:19 am, Mehnaaz wrote:
> @ vikas ..the space actually worked !!..is there any
> explanation ??..thanks a ton!
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: C doubt
If you are working in C++, stl has a vector container class which will do this. Otherwise, declare an integer pointer in the struct and use malloc to allocate memory for it. Then you can use it like an array. Don On Aug 23, 11:51 pm, Arun Vishwanathan wrote: > say that you have a structure with some fields of known size and unknown > size.For example, a char, an integer and an integer array.I do not know the > size of the integer array until the user mentions the number of bytes he > needs this integer array to cover in the command line as an argument.Is it > possible to have a structure with an integer dynamic array? > > Arun > > -- > "People often say that motivation doesn't last. Well, neither does bathing > - that's why we recommend it daily." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: probability ques
First find the endpoints of the region where the condition is met: a + 100/a = 50 a^2 - 50a + 100 = 0 By the quadratic formula, a is 2.08712 or 47.9128. The range is 45.8256. A falls in the range of 1..100 or 99. So the probability is 47.9128/99 = 0.48397 Don On Aug 23, 11:56 am, ramya reddy wrote: > Let 'a' be a number between 1 and 100. what is the probability of choosing > 'a' such that a+ (100/a) <50 > > -- > Regards > Ramya > * > * > *Try to learn something about everything and everything about something* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: C doubt
Yes, the memory provided by malloc will not be in the structure. Only
the pointer to that memory will be in the structure. The size of a
struct is defined at compile time, so it can't be dynamically sized at
run time.
struct junk
{
int size;
int *data;
};
Somewhere in the code:
struct junk myJunk;
myJunk.size = n;
myJunk.data = (int *)malloc(n * sizeof(int));
for(i = 0; i < n; ++i)
myJunk.data[i] = i;
That should work for values of n which your memory can support.
sizeof(struct junk) is eight bytes even if it contains a pointer to a
million integers.
Don
On Aug 24, 11:04 am, sagar pareek wrote:
> See if we use dynamic memory allocation then still the size of pointer will
> be 4 bytes only
> Mean that int* pointer still have the size equals to pointer ... malloc only
> returns new alloted memory which is now only *pointed *by that pointer
>
> check this out :-http://www.ideone.com/20ayq
>
>
>
> On Wed, Aug 24, 2011 at 8:10 PM, Don wrote:
> > If you are working in C++, stl has a vector container class which will
> > do this. Otherwise, declare an integer pointer in the struct and use
> > malloc to allocate memory for it. Then you can use it like an array.
> > Don
>
> > On Aug 23, 11:51 pm, Arun Vishwanathan wrote:
> > > say that you have a structure with some fields of known size and unknown
> > > size.For example, a char, an integer and an integer array.I do not know
> > the
> > > size of the integer array until the user mentions the number of bytes he
> > > needs this integer array to cover in the command line as an argument.Is
> > it
> > > possible to have a structure with an integer dynamic array?
>
> > > Arun
>
> > > --
> > > "People often say that motivation doesn't last. Well, neither does
> > bathing
> > > - that's why we recommend it daily."
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> **Regards
> SAGAR PAREEK
> COMPUTER SCIENCE AND ENGINEERING
> NIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: C-hexadecimal doubt
It is most common to use 4 bytes to store an integer value, even if the full range will not be used. There is no problem putting a 16-bit value into a 32-bit field. The only case where this is not true is when memory is extremely limited and you need to pack as much into every word as possible. Do be aware that most structures are word- aligned, so to actually save memory you must have several adjacent elements in the structure which can be combined into one word. Don On Aug 24, 1:07 pm, Arun Vishwanathan wrote: > Hi all, > > I need to store a hexadecimal value in C( which would be used as a request > type in a network) of around 4digits( or 16 bits-2 bytes ) in a packet > structure.If my system keeps 4 bytes for an integers, is it necessary that I > have to declare the hex value as of type short int or so, so that it takes > up only 2 bytes in my packet ? What if it was required to have a hex value > of 3 bytes or so? How could i store it then? > Also if hex value was to be of a multiple of 4 bytes would i need to use > something like an integer array to store them or a float maybe? > > thanks! > > -- > "People often say that motivation doesn't last. Well, neither does bathing > - that's why we recommend it daily." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: large nos
Use NTL. Don On Aug 24, 12:43 pm, MAC wrote: > any thoughts ? if we have link lists to represent very large integer numbers > how to implement multiply and devide operator > -- > thanks > --mac -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
I'm going to assume that "elements in pairs" means exactly two of each
element except for the one which is missing it's pair.
The recursive solution is simple, but it only uses tail recursion, so
it is worthwhile to do it iteratively.
int findSingle(int *a, int size)
{
int result;
while(1)
{
printf("a[0] = %d size=%d\n", a[0], size);
if (size == 1)
{
result = a[0];
break;
}
else if (size == 3)
{
result = (a[0] == a[1]) ? a[2] : a[0];
break;
}
else
{
int midpoint = size/2;
if (a[midpoint] == a[midpoint-1]) --midpoint;
if (a[midpoint] != a[midpoint+1])
{
result = a[midpoint];
break;
}
else if (midpoint % 2)
{
size = midpoint;
}
else
{
a += midpoint;
size -= midpoint;
}
}
}
return result;
}
On Aug 24, 4:49 am, atul purohit wrote:
> Hi,
>
> A* sorted *integer array contains elements in pairs. All the pairs are
> complete except one element whose pair is missing. Find that element.
>
> Ex. { 1,1,2,2,2,2,3,3,4,5,5}
> result = 5
>
> There is a standard solution which returns an XOR of all the elements. But
> this needs O(n) time complexity. The person who asked me this question said
> that this can be done in < O(n). Maybe we can eliminate some elements.
> Anyone knows how to do this?
>
> Cheers,
> Atul
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Find the non-duplicate element in sorted array in < O(n) time
I assume that "elements in pairs" means that each value occurs exactly
twice except for the one single.
This algorithm is O(log n) and is nonrecursive. Writing it recursively
would make it a couple of lines shorter, but because it is purely tail
recursion, that is not necessary.
// Given an array "a" of size elements in which all elements occur in
pairs except for one single item,
// find the single item and return its value.
int findSingle(int *a, int size)
{
while(1)
{
// For an array of size 1, the only element is the single.
if (size == 1) return a[0];
// The logic below won't work for size three, but it is simple to
find the single.
else if (size == 3) return (a[0] == a[1]) ? a[2] : a[0];
else
{
// Pick the midpoint of the array
int midpoint = size/2;
// If we are looking at the second element of a pair, move back
to the first element
if (a[midpoint] == a[midpoint-1]) --midpoint;
// If midpoint is not a pair, that is the single.
else if (a[midpoint] != a[midpoint+1]) return a[midpoint];
// If midpoint is odd, look at left half of the array
if (midpoint % 2) size = midpoint;
else // If midpoint is even, look at the right half of the array
{
a += midpoint;
size -= midpoint;
}
}
}
}
On Aug 24, 4:49 am, atul purohit wrote:
> Hi,
>
> A* sorted *integer array contains elements in pairs. All the pairs are
> complete except one element whose pair is missing. Find that element.
>
> Ex. { 1,1,2,2,2,2,3,3,4,5,5}
> result = 5
>
> There is a standard solution which returns an XOR of all the elements. But
> this needs O(n) time complexity. The person who asked me this question said
> that this can be done in < O(n). Maybe we can eliminate some elements.
> Anyone knows how to do this?
>
> Cheers,
> Atul
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Intersection of characters
int main(int argc, char *argv[])
{
FILE *f1 = fopen(argv[1],"r");
FILE *f2 = fopen(argv[2],"r");
unsigned int hash1[8] = {0};
unsigned int hash2[8] = {0};
char ch;
while((ch=getc(f1)) != EOF)
hash1[ch&7] |= 1 << (ch>>3);
while((ch=getc(f2)) != EOF)
hash2[ch&7] |= 1 << (ch>>3);
for(ch = 0; ch < 256; ++ch)
if (((hash1[ch&7]&hash2[ch&7]) >> (ch>>3)) & 1)
printf("%c", ch);
return 0;
}
On Aug 25, 9:12 am, Shrey Choudhary
wrote:
> There are two files .. print the common characters in two files
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Intersection of characters
Sure. It uses a hash table to keep track of which characters occur in
each file. The hash table is 256 bits initialized to zero. When it
encounters a character in file 1 it sets the corresponding bit in the
hash table. It does that by taking the 3 low order bits as the index
to the hash table. Those bits will fall in the range 0..7. The high
order bits, obtained by shifting the character right 3 bits, will give
a value in the range 0..32. We shift a bit into that location and use
bitwise or to set the bit in the hash table. We do that for both
files. The final "for" loop checks each character to determine if its
bit is set in both hash tables. If so, it occurs in both places and we
output that character.
The code would be somewhat simpler if I didn't try to use every bit in
the hash table. It would take 512 bytes of memory instead of 512 bits.
int main(int argc, char *argv[])
{
FILE *f1 = fopen(argv[1],"r");
FILE *f2 = fopen(argv[2],"r");
char hash1[256] = {0};
char hash2[256] = {0};
char ch;
while((ch=getc(f1)) != EOF)
hash1[ch] = 1;
while((ch=getc(f2)) != EOF)
hash2[ch] = 1;
for(ch = 0; ch < 256; ++ch)
if (hash1[ch] && hash2[ch])
printf("%c", ch);
return 0;
}
Don
On Aug 25, 11:42 am, Shrey Choudhary
wrote:
> @Don..
>
> Can you briefly explain the program?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: stack using bst
The only way I see to be able to search in O(log n) and push/pop in O(1) would be to have each node contain 4 pointers: left, right, and parent pointers for the binary search tree and next pointer for the stack linked list. The stack would be a linked list using the "next" pointer, and the search tree would allow quick searching. Insertion and searching would be O(log n) as with any binary search tree. Pop would be O(1). If you don't need to be able to search, just use the "left" pointer to make a linked list. Push and pop are both O(1), but you don't have a binary search tree any more. Don On Aug 25, 12:00 pm, prasanth n wrote: > how to implement a stack(push and pop) using binary search tree?? > > -- > *prasanth* -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: stack using bst
You will have to keep two pointers, one to the root of the tree and
one to the head of the FIFO linked list.
To push, insert the item into both the bst and the linked list.
To pop, set a pointer to the first item in the linked list. Delete it
from the bst. It will always be a leaf, so deleting should be easy.
Follow the parent pointer up one level and set the appropriate left or
right pointer to null. Then set the head of the linked list to the
next item in the list. Return the pointer to the former first item.
push(node n)
{
tree.insert(n); // O(log n)
n->next = stack;
stack = n;
}
node pop()
{
node result = stack;
if (result->parent->left == result) result->parent->left = 0;
else result->parent->right = 0;
stack = result->next;
result->next = 0;
return result;
}
I was mistaken when I said push was O(1). Later on I said O(log n)
which is correct.
Don
On Aug 25, 1:25 pm, shady wrote:
> @don how will you keep track of the latest element inserted in a bst ?
> O(1) for pop ? similarly how to get O(1) for push ?
>
> Stack can be implemented with bst but the time complexity will increase.
>
> Anyone with different views ?
>
> On Thu, Aug 25, 2011 at 11:37 PM, Don wrote:
> > The only way I see to be able to search in O(log n) and push/pop in
> > O(1) would be to have each node contain 4 pointers: left, right, and
> > parent pointers for the binary search tree and next pointer for the
> > stack linked list. The stack would be a linked list using the "next"
> > pointer, and the search tree would allow quick searching. Insertion
> > and searching would be O(log n) as with any binary search tree. Pop
> > would be O(1).
>
> > If you don't need to be able to search, just use the "left" pointer to
> > make a linked list. Push and pop are both O(1), but you don't have a
> > binary search tree any more.
>
> > Don
>
> > On Aug 25, 12:00 pm, prasanth n wrote:
> > > how to implement a stack(push and pop) using binary search tree??
>
> > > --
> > > *prasanth*
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Intersection of characters
First it will use a bitwise AND to combine the bits of hash1 and
hash2. That gives the bits which are set in both hash values. Then it
shifts the bits to put the bit we are interested in into the 1's
place. Finally, a bitwise AND 1 looks at only the one bit we want. If
it is set, that character appears in both files.
Don
On Aug 25, 1:10 pm, Abhishek Yadav wrote:
> @Don: Can you please explain the 3rd for loop.the working of if
> statement???
>
> On Thu, Aug 25, 2011 at 11:02 PM, Don wrote:
> > Sure. It uses a hash table to keep track of which characters occur in
> > each file. The hash table is 256 bits initialized to zero. When it
> > encounters a character in file 1 it sets the corresponding bit in the
> > hash table. It does that by taking the 3 low order bits as the index
> > to the hash table. Those bits will fall in the range 0..7. The high
> > order bits, obtained by shifting the character right 3 bits, will give
> > a value in the range 0..32. We shift a bit into that location and use
> > bitwise or to set the bit in the hash table. We do that for both
> > files. The final "for" loop checks each character to determine if its
> > bit is set in both hash tables. If so, it occurs in both places and we
> > output that character.
>
> > The code would be somewhat simpler if I didn't try to use every bit in
> > the hash table. It would take 512 bytes of memory instead of 512 bits.
>
> > int main(int argc, char *argv[])
> > {
> > FILE *f1 = fopen(argv[1],"r");
> > FILE *f2 = fopen(argv[2],"r");
> > char hash1[256] = {0};
> > char hash2[256] = {0};
> > char ch;
>
> > while((ch=getc(f1)) != EOF)
> > hash1[ch] = 1;
>
> > while((ch=getc(f2)) != EOF)
> > hash2[ch] = 1;
>
> > for(ch = 0; ch < 256; ++ch)
> > if (hash1[ch] && hash2[ch])
> > printf("%c", ch);
>
> > return 0;
> > }
>
> > Don
>
> > On Aug 25, 11:42 am, Shrey Choudhary
> > wrote:
> > > @Don..
>
> > > Can you briefly explain the program?
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Given a number, return the least prime greater than number
Usually that is done before run time and hard coded into the hash function. But for numbers in the range you are talking about, a sieve would work. However trial division should not take long either, if you just need to do it once when the hash table is created. Don On Aug 25, 10:18 pm, Navneet Gupta wrote: > Needless to say. looking for an efficient solution rather than trying > successive numbers from given number for primality. Any method? > > A general purpose use of above is to calculate N for hash functions. (index > = key%N where N is prime). > > -- > Regards, > Navneet -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find the non-duplicate element in sorted array in < O(n) time
After working on it quite a bit I got an O(log n) algorithm working.
For small cases (size < 10) it sequentially finds the solution.
For larger cases it uses a binary search:
Starting at the midpoint, find the left and the right ends of the
region with values equal to the value at the midpoint. This is done by
another binary search. That gives three regions:
1. Values less than the midpoint value in the left part of the array
2. Values equal to the midpoint value
3. Values greater than the midpoint value in the right part of the
array
One of those regions will be odd in size. If it is region 2, the
midpoint value is the repeated value. Otherwise, narrow the search to
the odd-sized region.
In 1000 trials on an array of size 1001 including a variety of input
data/different sized clumps of equal values, it took on average 7.5
iterations through the main loop and 14 iterations through the inner
binary search loop per call.
Code follows (apologies for how cutting and pasting messes up the
formatting):
// Find left edge of group of equal values including a[midpoint]
int findLeftEdge(int *a, int midpoint)
{
// We know that midpoint > 3. For a small case, just search
sequentially.
if (a[midpoint-4] != a[midpoint])
{
while(a[midpoint-1] == a[midpoint])
--midpoint;
return midpoint;
}
int min = 1; // findSingle eliminates cases where a[0] ==
a[midpoint]
int max = midpoint-4; // Covered by first check above
while(1)
{
int median = (min + max) / 2;
if (a[median] == a[midpoint])
{
if (a[median-1] != a[midpoint]) return median;
max = median-1;
}
else
{
if (a[median+1] == a[midpoint]) return median+1;
min = median+1;
}
}
}
// FInd right edge of group of equal values including a[midpoint]
int findRightEdge(int *a, int midpoint, int size)
{
if (a[midpoint+4] != a[midpoint])
{
while(a[midpoint+1] == a[midpoint])
++midpoint;
return midpoint;
}
int min = midpoint + 4;
int max = size-2;
while(1)
{
int median = (min + max) / 2;
if (a[median] == a[midpoint])
{
if (a[median+1] != a[midpoint]) return median;
min = median + 1;
}
else
{
if (a[median-1] == a[midpoint]) return median-1;
max = median-1;
}
}
}
// Given an array "a" of size elements in which all elements occur in
pairs except for one single item,
// find the single item and return its value.
int findSingle(int *a, int size)
{
while(1)
{
// For an array of size 1, the only element is the single.
if (size == 1) return a[0];
// The logic below won't work for size three, but it is simple to
find the single.
else if (size == 3) return (a[0] == a[1]) ? a[2] : a[0];
else if (size < 10)
{
int result = a[0];
for(int i = 1; i < size; ++i)
result ^= a[i];
return result;
}
else
{
// Pick the midpoint of the array
int midpoint = size/2;
// If all values to the left of midpoint are equal, singleton must
be to right.
if (a[midpoint] == a[0])
{
a += midpoint;
size -= midpoint;
if ((size%2) == 0)
{
++a;
--size;
}
}
// If all values to the right of midpoint are equal, singleton must
be to left.
else if (a[midpoint] == a[size-1])
{
size = midpoint;
if ((size%2) == 0) --size;
}
else
{
int left = findLeftEdge(a,midpoint);
int right = findRightEdge(a,midpoint,size);
if ((right-left) % 2 == 0) return a[midpoint];
if (left % 2) size = left;
else
{
++right;
a += right;
size -= right;
}
}
}
}
}
On Aug 24, 4:49 am, atul purohit wrote:
> Hi,
>
> A* sorted *integer array contains elements in pairs. All the pairs are
> complete except one element whose pair is missing. Find that element.
>
> Ex. { 1,1,2,2,2,2,3,3,4,5,5}
> result = 5
>
> There is a standard solution which returns an XOR of all the elements. But
> this needs O(n) time complexity. The person who asked me this question said
> that this can be don
[algogeeks] Re: unsorted array problem
I believe this is what techcoder is saying:
int a[N];
// Find the bitwise xor of all the array values.
// These are the bits which are different between the two results.
int xor = 0;
for(i = 0; i < N; ++i)
xor ^= a[N];
// Find the low order bit of xor
int bit = 1;
while(!(xor & bit))
bit <<= 1;
// xor the values with "bit" set to get one result
// xor the values with "bit" unset to get the other result
int result1 = 0, result2 = 0;
for(i = 0; i < n; ++i)
{
if (a[i] & bit) result1 ^= a[i];
else result2 ^= a[i];
}
Now result1 & result2 are the values which appear an odd number of
times. It is O(n).
Don
On Aug 26, 12:13 pm, Dave wrote:
> @Tech: I'm not sure I understand your algorithm. Let's try it on
> {1,1,2,2,3,4,5,5,6,6,7,7}. The two number occurring an odd number of
> times are 3 and 4. We xor the numbers getting 7 = 111 in binary. Now
> how do we divide the numbers into two groups?
>
> Dave
>
> On Aug 26, 11:09 am, tech coder wrote:
>
> > it can be done in O(N) by using XOR ing the elements
> > 1: Xor all the elemnts since those elemnts that even freq will nullify each
> > other we get number taht will tell in which the two required number differ.
> > 2: divide the array in two sets on the basis of bit in which numbers
> > differ
> > 3:1 element will be in one set another will be in another set
> > 4: XOR both the sets again we get both the elemts
> > On Thu, Aug 25, 2011 at 12:50 PM, Umesh Jayas
> > wrote:
>
> > > int main()
> > > {
> > > int arr[]={1,2,5,1,5,1,1,3,2,2,};
> > > int elements = sizeof(arr)/sizeof(arr[0]);
> > > int count=1;
> > > int num;
> > > sort(arr,arr+elements);
>
> > > num=arr[0];
> > > for(int i=1;i > > {
> > > if(arr[i]==num)
> > > count++;
> > > else
> > > {
> > > if(count%2==0)
> > > { num=arr[i];
> > > count=1;}
> > > else
> > > {cout<<"\n"< > > count=1;
> > > num=arr[i];
> > > }
> > > }
> > > }
> > > getch();
> > > }
>
> > > complexity: 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.-Hide quoted text -
>
> > - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find all the subsets whose sum <= k
This is the knapsack problem. Find a polynomial-time solution and you will be a hero. Don On Aug 26, 12:43 pm, Piyush Grover wrote: > Here is a problem: > > Given an array of size n. Find all the MAXIMAL subsets whose sum is <= K. > The solution is not a concern, the optimization is required. > > -piyush -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Find all the subsets whose sum <= k
@rahul Your code will only find pairs which sum to k. The problem is to find a subset of as many elements in the array as required to sum as close as possible to k. It is a well-known problem and after years of study, no polynomial solution is known. There are reasonably fast solutions for small inputs, but the best anyone has done is a pseudo-polynomial-time algorithm using dynamic programming. Thus it is weakly NP-complete. As n gets large, the time required increases exponentially. Search the web for "Knapsack problem" to learn more. Don On Aug 26, 1:04 pm, rahul sharma wrote: > yes it will > return in c return 1 value at tym... > ijust given the code snipetjust modify it..store trhm in some > other array like thebut it will > > On Aug 26, 11:02 pm, Piyush Grover wrote: > > > @rahul...I'm unsure if your algo returns all the subsets. > > > On Fri, Aug 26, 2011 at 11:24 PM, rahul sharma > > wrote: > > > > yeah can be done in poly tym also...but we dnt knw whether we have > > > unsorted arryit is possible in sorted array. > > > > On Aug 26, 10:52 pm, Don wrote: > > > > This is the knapsack problem. > > > > Find a polynomial-time solution and you will be a hero. > > > > Don > > > > > On Aug 26, 12:43 pm, Piyush Grover wrote: > > > > > > Here is a problem: > > > > > > Given an array of size n. Find all the MAXIMAL subsets whose sum is <= > > > K. > > > > > The solution is not a concern, the optimization is required. > > > > > > -piyush > > > > -- > > > You received this message because you are subscribed to the Google Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algogeeks@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com. > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Find all the subsets whose sum <= k
The 0-1 knapsack problem is still the knapsack problem. Don On Aug 26, 1:55 pm, Piyush Grover wrote: > it's similar to knapsack but not the same. In knapsack, types of items are > limited and we play on the quantity of each item. > Here each element will come once in the subset. > > On Fri, Aug 26, 2011 at 11:49 PM, Don wrote: > > @rahul > > Your code will only find pairs which sum to k. The problem is to find > > a subset of as many elements in the array as required to sum as close > > as possible to k. > > It is a well-known problem and after years of study, no polynomial > > solution is known. There are reasonably fast solutions for small > > inputs, but the best anyone has done is a pseudo-polynomial-time > > algorithm using dynamic programming. Thus it is weakly NP-complete. As > > n gets large, the time required increases exponentially. > > Search the web for "Knapsack problem" to learn more. > > Don > > > On Aug 26, 1:04 pm, rahul sharma wrote: > > > yes it will > > > return in c return 1 value at tym... > > > ijust given the code snipetjust modify it..store trhm in some > > > other array like thebut it will > > > > On Aug 26, 11:02 pm, Piyush Grover wrote: > > > > > @rahul...I'm unsure if your algo returns all the subsets. > > > > > On Fri, Aug 26, 2011 at 11:24 PM, rahul sharma < > > rahul23111...@gmail.com>wrote: > > > > > > yeah can be done in poly tym also...but we dnt knw whether we have > > > > > unsorted arryit is possible in sorted array. > > > > > > On Aug 26, 10:52 pm, Don wrote: > > > > > > This is the knapsack problem. > > > > > > Find a polynomial-time solution and you will be a hero. > > > > > > Don > > > > > > > On Aug 26, 12:43 pm, Piyush Grover > > wrote: > > > > > > > > Here is a problem: > > > > > > > > Given an array of size n. Find all the MAXIMAL subsets whose sum > > is <= > > > > > K. > > > > > > > The solution is not a concern, the optimization is required. > > > > > > > > -piyush > > > > > > -- > > > > > You received this message because you are subscribed to the Google > > Groups > > > > > "Algorithm Geeks" group. > > > > > To post to this group, send email to algogeeks@googlegroups.com. > > > > > To unsubscribe from this group, send email to > > > > > algogeeks+unsubscr...@googlegroups.com. > > > > > For more options, visit this group at > > > > >http://groups.google.com/group/algogeeks?hl=en. > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Given a number, return the least prime greater than number
That might require a very large table. There are 203 million primes
less than 2^32. Because a hash function is usually established once
and then used many times, computing a whole table of primes is not
necessary. Finding the one next prime can be done faster using trial
division, because the overhead in setting up a sieve is actually more
work than just finding the one next prime with trial division, if the
numbers are not huge.
The function below will find the next prime for numbers less than 100
million in about half the time it takes to use a sieve. Again, trial
division is not the best way to find a stream of many prime numbers,
but it is just fine for finding one.
Don
int nextPrime(int n)
{
++n;
if (n % 2 == 0) ++n;
if (n % 3 == 0) n += 2;
int step = "XEC"[n%3] - 'A';
while(1)
{
for (int i = 5; i*i <= n; i += 6)
{
if (n%i == 0) break;
if (n%(i+2) == 0) break;
}
if (i*i > n) return n;
n += step;
step ^= 6;
}
}
On Aug 27, 3:59 am, saurabh modi wrote:
> use sieve.then make a list of primes.
>
> A binary search can work well to find the next greater prime number.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Custom Random Generator
int custRand(int n)
{
int a,b;
do
{
a = rand(n);
b = rand(n);
} while(a < b);
return n - a + b;
}
On Aug 29, 10:48 am, Piyush Grover wrote:
> Given a function rand(n) which returns a random value between 1...n assuming
> equal probability.
> Write a function CustRand(n) using rand(n) which returns a value between
> 1...n such that
> the probability of occurrence of each number is proportional to its value.
>
> I have a solution but wondering if I can get better than this or some other
> approaches:
>
> CustRand(n){
>
> sum = n*(n+1)/2;
>
> a = rand(sum);
> for(i = 1; i <= n; i++){
> h = i*(i+1)/2;
> l = i*(i-1)/2;
> if(a <= h && a > l)
> return i;
> }
>
> }
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Custom Random Generator
If you draw the nxn grid and assign a value to each diagonal:
(For n = 5)
--b
| 12345
| 2345
| 345
| 45
| 5
a
You want the result to be the orthogonal distance from the diagonal.
That is what the formula computes.
Don
On Aug 29, 11:28 am, Piyush Grover wrote:
> I understand what you are doing in the loop but return statement is not
> clear to me. Can you explain.
>
> On Mon, Aug 29, 2011 at 9:48 PM, Don wrote:
> > int custRand(int n)
> > {
> > int a,b;
> > do
> > {
> > a = rand(n);
> > b = rand(n);
> > } while(a < b);
> > return n - a + b;
> > }
>
> > On Aug 29, 10:48 am, Piyush Grover wrote:
> > > Given a function rand(n) which returns a random value between 1...n
> > assuming
> > > equal probability.
> > > Write a function CustRand(n) using rand(n) which returns a value between
> > > 1...n such that
> > > the probability of occurrence of each number is proportional to its
> > value.
>
> > > I have a solution but wondering if I can get better than this or some
> > other
> > > approaches:
>
> > > CustRand(n){
>
> > > sum = n*(n+1)/2;
>
> > > a = rand(sum);
> > > for(i = 1; i <= n; i++){
> > > h = i*(i+1)/2;
> > > l = i*(i-1)/2;
> > > if(a <= h && a > l)
> > > return i;
> > > }
>
> > > }
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Given a number, return the least prime greater than number
"Step" alternates between 4 and 2 in such a way that n hits all odd
values not divisible by 3.
Don
On Aug 29, 10:35 am, dilip makwana wrote:
> I got it ... thanks
> {That line finds what value of step needs to be taken ... }
>
> Algo is good ... :D
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Custom Random Generator
No, a+b-1 would return values outside of the desired range.
Don
On Aug 29, 12:26 pm, nishaanth wrote:
> @Don...Nice solution.. But the return statement should be a+b-1
>
>
>
> On Mon, Aug 29, 2011 at 10:33 PM, Don wrote:
> > If you draw the nxn grid and assign a value to each diagonal:
>
> > (For n = 5)
>
> > --b
> > | 12345
> > | 2345
> > | 345
> > | 45
> > | 5
> > a
>
> > You want the result to be the orthogonal distance from the diagonal.
> > That is what the formula computes.
> > Don
>
> > On Aug 29, 11:28 am, Piyush Grover wrote:
> > > I understand what you are doing in the loop but return statement is not
> > > clear to me. Can you explain.
>
> > > On Mon, Aug 29, 2011 at 9:48 PM, Don wrote:
> > > > int custRand(int n)
> > > > {
> > > > int a,b;
> > > > do
> > > > {
> > > > a = rand(n);
> > > > b = rand(n);
> > > > } while(a < b);
> > > > return n - a + b;
> > > > }
>
> > > > On Aug 29, 10:48 am, Piyush Grover wrote:
> > > > > Given a function rand(n) which returns a random value between 1...n
> > > > assuming
> > > > > equal probability.
> > > > > Write a function CustRand(n) using rand(n) which returns a value
> > between
> > > > > 1...n such that
> > > > > the probability of occurrence of each number is proportional to its
> > > > value.
>
> > > > > I have a solution but wondering if I can get better than this or some
> > > > other
> > > > > approaches:
>
> > > > > CustRand(n){
>
> > > > > sum = n*(n+1)/2;
>
> > > > > a = rand(sum);
> > > > > for(i = 1; i <= n; i++){
> > > > > h = i*(i+1)/2;
> > > > > l = i*(i-1)/2;
> > > > > if(a <= h && a > l)
> > > > > return i;
> > > > > }
>
> > > > > }
>
> > > > --
> > > > You received this message because you are subscribed to the Google
> > Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > To unsubscribe from 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.
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> 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.
[algogeeks] Re: How to save a binary search tree space efficiently
I'm not sure if this is what you are looking for, but I once came up with a way to save a binary tree in such a way that when it is rebuilt, it will be balanced. You don't get back the exact same tree with all the nodes in the same position, but you do get the same nodes in a balanced configuration. Start by doing an inorder traversal and storing each node sequentially in an array. Then call a recursive function called saveTree(first, last), where first and last are the first and last indices of the array. saveTree does the following if: write middle item of array to the file call saveTree on left half of array call saveTree on right half of array When you rebuild the tree adding the nodes in the order in which they occur in the file, the resulting tree will be balanced. Don On Aug 28, 1:29 am, rohit wrote: > How to save a binary search tree space efficiently and built it > again , just tell any idea. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Custom Random Generator
Here is how to do it with a single call to rand and no looping.
int custRand(int n)
{
int a = rand(n*n+n);
int b = a / n;
a %= n;
return (b > a) ? n+a-b+1 : n-a+b;
}
On Aug 29, 10:48 am, Piyush Grover wrote:
> Given a function rand(n) which returns a random value between 1...n assuming
> equal probability.
> Write a function CustRand(n) using rand(n) which returns a value between
> 1...n such that
> the probability of occurrence of each number is proportional to its value.
>
> I have a solution but wondering if I can get better than this or some other
> approaches:
>
> CustRand(n){
>
> sum = n*(n+1)/2;
>
> a = rand(sum);
> for(i = 1; i <= n; i++){
> h = i*(i+1)/2;
> l = i*(i-1)/2;
> if(a <= h && a > l)
> return i;
> }
>
> }
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Find square root a number
This code takes advantage of IEEE format of floating point numbers to
get a close approximation. Then two iterations of Newton's method get
about 12 digits of accuracy.
Don
float sqrt(float z) {
union
{
int tmp;
float f;
} u;
u.f = z;
u.tmp -= 1<<23;
u.tmp >>= 1;
u.tmp += 1<<29;
u.f = u.f-(u.f*u.f-z)/(2.0*u.f);
return u.f-(u.f*u.f-z)/(2.0*u.f);
}
On Aug 30, 1:07 am, Raghavan wrote:
> how to design this logic effectively?
>
> double squareRoot(int num){
>
> }
>
> --
> Thanks and Regards,
> Raghavan KL
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Custom Random Generator
This is one way to accomplish the job with one call to rand and no
looping. It does limit the value of "n" to be less than 65536. If you
want to allow larger values of n, you can use two calls to rand, one
for a and the other for b.
Don
int custRand(int n)
{
int a = rand(n*n+n)-1;
int b = a / n;
a %= n;
return (b > a) ? n+a-b+1 : n-a+b;
}
On Aug 29, 10:48 am, Piyush Grover wrote:
> Given a function rand(n) which returns a random value between 1...n assuming
> equal probability.
> Write a function CustRand(n) using rand(n) which returns a value between
> 1...n such that
> the probability of occurrence of each number is proportional to its value.
>
> I have a solution but wondering if I can get better than this or some other
> approaches:
>
> CustRand(n){
>
> sum = n*(n+1)/2;
>
> a = rand(sum);
> for(i = 1; i <= n; i++){
> h = i*(i+1)/2;
> l = i*(i-1)/2;
> if(a <= h && a > l)
> return i;
> }
>
> }
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: How to save a binary search tree space efficiently
Because the original poster specified that space efficiency is important, I would go with pre-order. There are typically as many nulls in a tree as there are nodes, so you could double the size of the file by including nulls. Don On Aug 30, 8:15 am, Dumanshu wrote: > Level Order traversal if you are ok with the Nulls being stored. > Otherwise its pre order traversal. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: Let's see if U can find the bug...
pow works with double (floating point) values, not integers, and when
you assign the result to an integer, it truncates. You will be better
off, both in speed and correctness, to just use r*r*r instead of pow(r,
3).
Don
On Aug 30, 1:06 am, Mohit Gupta wrote:
> *1.*
> /* Print armstrong numbers from 1 to 500 */
> /*1st version of prgrm: I am using pow function*/
> #include
> #include
> #include
> int main()
> {
> int num=1,temp,sum,r;
> while(num<=500){
> sum=0;
> temp=num;
> while(temp){
> r=temp%10;
> sum+=pow(r,3);
> temp/=10;
> }
> if(sum==num)
> printf("%d\n",num);
> num++;}
>
> getch();
> return 0;
>
> }
>
> It prints :
> 1
> 370
> 371
> 407
>
> But it does not print 153 which is also armstrong number. WHY???
>
> BUT if I change: pow(r,3) to r*r*r in codethen it prints:
> 1
> 153
> 370
> 371
> 407
>
> WHY 153 was not printed if i use pow() function???
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: solving a simple equation
There are three solutions, with d never exceeding 3. Don On Aug 30, 3:08 pm, him wrote: > finding number of integral solution of the equation > > ab+cd=a+d+b+c (1<=a<=b<=c<=d) (any efficient method ) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: String Problem
// Returns true if string s3 is s1 interleaved with s2.
// The function is iterative when possible, but uses a recursive
// call when both s1 and s2 match the next character in s3.
// Note that this function is not intended to be called directly. It
is called by Interleaved().
bool interleaved2(char *s1, char *s2, char *s3)
{
while(1)
{
// End case is when all three strings are empty
if (!s1[0] && !s2[0] && !s3[0]) return true;
if (s1[0] == s3[0])
{
if (s2[0] == s3[0])
{
// Tries both using s1 and s2 next. The recursive call uses
s1,
// and the postincrement of s2 uses s2 iteratively.
if (interleaved2(s1+1, s2++,s3+1)) return true;
}
// s1 is the only match
else ++s1;
}
else
{
// s2 is the only match
if (s2[0] == s3[0]) ++s2;
// Neither s1 nor s2 match the next character in s3 so the
strings are not interleaved
else return false;
}
// Move on to the next character in s3
++s3;
}
}
bool Interleaved(char *s1, char *s2, char *s3)
{
// Frequency counts
int count1[256] = {0};
int count2[256] = {0};
int i,j;
// Count the number of occurances of each character in s1 and s2
for(i = 0; s1[i]; ++i)
++count1[s1[i]];
for(j = 0; s2[j]; ++j)
++count1[s2[j]];
j += i;
// Next count the number of occurances of each character in s3
for(i = 0; s3[i]; ++i)
++count2[s3[i]];
// If the total number of characters in s3 is not s1+s2, interleaved
is false
if (i != j) return false;
// If s3 is s1 interleaved with s2, these counts must be equal
for(i = 1; i < 128; ++i)
if (count1[i] != count2[i])
return false;
// Call the function to do the real work.
return interleaved2(s1,s2,s3);
}
On Aug 31, 8:43 am, Navneet wrote:
> Suppose the two strings are ab and cd.
>
> The possible strings formed by interleaving these two are
> abcd, acbd, acdb , cabd etc..
>
> On Aug 31, 5:23 pm, sukran dhawan wrote:
>
> > what do u mean by interleaving ?
>
> > On Wed, Aug 31, 2011 at 5:01 PM, Navneet Gupta wrote:
>
> > > The important thing to notice here is that relative order of
> > > characters is important and hence you should not look for just count
> > > char based approaches.
>
> > > On Wed, Aug 31, 2011 at 11:20 AM, Navneet Gupta
> > > wrote:
> > > > Given two strings S1 and S2, Find whether another string S3 can formed
> > > > by interleaving S1 and S2. Only constant space.
>
> > > > --
> > > > Regards,
> > > > Navneet
>
> > > --
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: probability question
In my experience, the probability that a train stays on schedule to within 5 minutes is about 0.01, so I'm going to say that the probability is about 0.51. Don On Aug 31, 8:37 am, swetha rahul wrote: > In a railway station, there are two trains going. One in the harbour line > and one in the main line, each having a frequency of 10 minutes. The main > line service starts at 5 o'clock and the harbour line starts at 5.02A.M. A > man goes to the station every day to catch the first train that comes.What > is the probability of the man catching the first > train? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from 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: loop in link list
@Ravi:
Count the nodes in the loop.
Step one point that many nodes into the list.
Start another pointer at the head.
Step both pointers until the two "next" pointers are equal.
Now you have the two nodes which have the same "next" pointer.
Don
// Returns NULL if there is no loop
// Returns pointer to last node before the loop if there is a loop
Node *FindLoop(Node *head)
{
Node *p1=head, *p2=head;
while(p2)
{
p2 = p2->next;
if (p2) p2 = p2->next;
p1 = p1->next;
if (p1 == p2) break;
}
if (!p2) return 0;
// Count nodes in loop
int count = 1;
for(p2=p1->next; p2 != p1; p2 = p2->next)
++count;
// Start p1 at head and p2 at position count
p1 = p2 = head;
for(int i = 0; i < count; ++i)
p2 = p2->next;
// Find entrance point to loop
while(p1->next != p2->next)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
On Aug 31, 8:18 am, ravi maggon wrote:
> In one of my interview at winshuttle I was asked the same ques but their was
> an addon to this. Find the point where the loop occurs.
> For eg:
> 1->2->3->4->5->6->7->8->9->5
>
> so output should be 5
>
> can anyone give the algo for this.
>
> On Wed, Aug 31, 2011 at 6:44 PM, Piyush Grover
> wrote:
>
>
>
> > This is fine but adding a twist to it.
> > Find number of nodes which are not in the loop.
>
> > On Wed, Aug 31, 2011 at 6:27 PM, rahul sharma
> > wrote:
>
> >> int loop(void *head1,void *head2)
> >> {
> >> //head1 and head2 initialized to start;
> >> while(head1!=NULL && head2!=NULL)
> >> {
> >> head1=head1->next;
> >> head2=head2->next->next;
> >> if(head1==head2)
> >> return 1;tehre is loop;
> >> }
> >> return 0;//no loop
> >> }
>
> >> hi guys is it corect for finding the loop...if any test case that wont
> >> works here plz tell...
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from 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.
>
> --
>
> Regards
> Ravi Maggon
> Final Year, B.E. CSE
> Thapar University
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Static variable
Because i is static it is not on the stack. There is one value of i
accessed from all the calls to main. Each time main is called, it
decrements i, then if the decremented value is positive, it calls
main. So eventually we get to the point where we are 10 levels deep
and i=0. Then we have to start unwinding the stack. But even when i is
zero, every time the while condition is evaluated, it will decrement
i. So i continues to be decremented at each level as the recursion
unwinds. That is why it prints negative values.
Don
On Aug 31, 8:20 am, ravi maggon wrote:
> what will be the output of this:
> main()
> {
> static int i=10;
> while(--i>0)
> {
> main();
> printf("%d",i);
> }
>
> }
>
> --
>
> Regards
> Ravi Maggon
> Final Year, B.E. CSE
> Thapar University
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
