[algogeeks] Re: Minimal number of swaps

[Dave]

Use the quicksort algorithm: Set the swap counter to 0. Search from the 
beginning of the array for the first 0, and from the end of the array for 
the first 1. If the pointers cross, you are done; otherwise increment the 
swap counter and continue the searches.

On Tuesday, March 29, 2016 at 9:00:21 AM UTC-5, Régis Bacra wrote:
>
> This puzzle comes from a contribution on codingame.com (link to the puzzle 
> ). Any idea to 
> solve it efficiently?
>
> Given a list of 1 and 0, you must regroup all the 1 at the begin of the 
> list in a minimum number of steps. A step is the interchange of two 
> elements located at different positions.
> The expected result is the minimum number of steps required to obtain a 
> sorted list.
>
> Examples:
> 1 0 1 0 1 -> 1
> 0 1 0 1 1 1 0 -> 2
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Question on algo

[Dave]

Very simple. If MAXOR of the entire input set is not equal to zero, there 
are no subsets with equal MAXORs. If MAXOR of the entire set is zero, then 
any two complementary subsets have equal MAXORs. Since there are 2^N (^ is 
the exponential operator) subsets of a set of N elements, Little Panda 
needs to calculate mod((2^N)!,17) (! is the factorial symbol). 

Dave

On Monday, October 5, 2015 at 10:48:11 PM UTC-5, gopi wrote:

> Little Black Panda is mad about XOR operation. Presently he has gone mad 
> and he won't stop performing XOR operation on various numbers.
> Given an array of N numbers, for each subset of the array Little Panda 
> performs MAXOR operation for the subset. MAXOR operation means that he 
> finds XOR of all elements in that subset (if the subset is [1,2,3] then 
> MAXOR is 1^2^3=0) . Little Panda is now exhausted and wants to do something 
> else. Little Panda wants to pick any two subsets the MAXOR of whose are 
> same. Little Panda needs to find the number of selections that he can make. 
> He is very very weak in programming so he wants the answer from you. Please 
> help little panda in finding out his query.
> Since the output can be very large output it modulo 17.
>
> Input Format
> The first line contains N i.e. the length of the array.
> N lines follow, each containing a non-negative integer.
>
> Output Format
> Output Little Panda's Query in a single line.
>
> Constraints
> 1 <= N <= 10
> 0 <= A[i] <= 100
> (where A[i] denotes the value of array element)
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Regarding approach to solve

[Dave]

Do a breadth-first search. From your starting position, find all of the 
positions you can reach in one move. From each of those, find all positions 
you can reach in one move. If you reach an already-reached position, just 
ignore that move; you either got to that position on an earlier move or via 
another path on this move. Continue this way until either you reach the 
solution state or you are not able to find any previously unreached 
positions. In the former case, you have determined the minimum number of 
moves to solve the puzzle. In the latter case, there is no solution.

Dave

On Sunday, September 28, 2014 10:07:56 AM UTC-5, Ravi Ranjan wrote:

 Yesterday I appeared for ACM USA Regionals, there I got the problem

 https://icpc-qual-14.kattis.com/problems/flipfive

 Can anyone help how to solve this kind of problem.
 Any links for similar problems ?



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Calculating C(n.r)

[Dave]

What you want to do is automate the process of cancelling common factors 
that you would do if you were calculating nCr by hand. Fill an array a[] 
with the numerator terms, n, n-1, n-2, ..., n-r+1, and a second array b[] 
with the denominator terms, 1, 2, 3, ..., r. Inside a double loop with j 
and i going from 0 to r-1, compute the gcd of a[i] and b[j]. Divide both 
a[i] and b[j] by the gcd. When the loops finish, you will have cancelled 
the common factors from all of the terms, and in fact, all of the 
denominator terms will be 1. In a final loop, compute the product of the 
numerator terms. There are some obvious optimizations.

Dave

On Tuesday, April 8, 2014 1:06:47 PM UTC-5, kumar raja wrote:

 Hi all,

 I know the way to calculate value of C(n,r) using pascals identity. But i 
 have a different requirement.

  C(n,r) =  n (n-1) (n-2) ... (n-r+1) / r! 

 Suppose the numerator is such that it cant fit into existing data type.  

 So i remember there is a way to strike off the common factors in numerator 
 and denominator  then calculate the result of it. But the logic is not 
 striking to me. Googled but could not find much. So please share the clever 
 way to calculate the above value w/o actually computing the factorials and 
 then making division.

 My actual requirement is to calculate the value of

 (n1+n2++nk)! / (n1!.n2!.n3!.nk!) .


 Regards,
 Kumar Raja.




-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Integer partition problem - DP

[Dave]

See http://en.wikipedia.org/wiki/Partition_(number_theory).

On Saturday, March 1, 2014 10:25:57 AM UTC-6, kumar raja wrote:

 Given an integer how many number of ways u can partition the number?
  
 e.g. 3  can be written as 3,1+2,1+1+1 
 and 4 can be written as  4, 1+1+1+1,2+2,1+3,1+1+2   

 So  for 3 -- 3
   for 4 --5.

 The order of the elements in the partition does not matter. 
 So how to calculate the number of ways to partition the given number?

 Can someone give idea on how to write the recurrence relation 
 for the problem? 


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Permuations with stack constraints

[Dave]

@Kumar: As a point of interest, the number of valid sequences of n pushes 
and n pops is C(3), the third Catalan Number. See, e.g., 
http://en.wikipedia.org/wiki/Catalan_number for details.

Dave

On Thursday, February 20, 2014 12:27:35 PM UTC-6, kumar raja wrote:

 Hi all,

 Here is a permuatation related question.

 Suppose the set is {a,b,c};

 At a given point of time either u can push an
 elemnt on to the stack or pop of the element.
 While pushing the elements u have to follow the 
 order a,b,c as given in the set.

 When u pop the element u will print it to the 
 output array.

 one possible sequence of operations is 

 push(a),push(b),pop(),push(c),pop(),pop()

 The permuation obtained by above combination is 

  {b,c,a}.
  
 But out of 6! permuations possible one invalid 
 permutation  is {c,a,b} (guess how?)

 So how to print all valid permuations with the 
 above constaraints?  


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Solving equation

[Dave]

@Saurabh: No. It represents an equation with no solutions. (x - 7) + 7 = 
(x + 1) - 5 reduces algebraically to 0 = -4. Since there are no values 
of x for which this is a true statement, there are no solutions.

Dave

On Monday, January 27, 2014 5:32:19 AM UTC-6, Saurabh Singh_cse_20094016 
wrote:

 ^ No its not invalid. It just represents an equation with infinitely many 
 correct solutions depending on the domain of x.

 Saurabh Singh
 B.Tech (Computer Science)
 MNNIT 
 blog:geekinessthecoolway.blogspot.com


 On Mon, Jan 27, 2014 at 4:21 PM, Amol Sharma amolsh...@gmail.comjavascript:
  wrote:

 i din't get ur question.

 isn't the equation *(x - 7) + 7 = (x + 1) - 5*  invalid ?

 --
 Thanks and Regards,
 Amol Sharma

  

 On Wed, Jan 15, 2014 at 3:34 AM, Arpit Sood sood...@gmail.comjavascript:
  wrote:

 Equivalent to solving an infix expression using stack with a pair (first 
 variable, second constant) as the element


 On Sat, Jan 11, 2014 at 6:50 AM, atul anand 
 atul.8...@gmail.comjavascript:
  wrote:

 Hello,

 How to solve an equation with one unknown variable ?
 operator allowed are : + , -

 for eg .  input could be :-
 x + ( 5 + 4 ) = 6
 (x - 7) + 7 = (x + 1) - 5

 If operator also allows  *  (multiply) , then what change in 
 algorithm is required.

 -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com javascript:.


  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com javascript:.


  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.




-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Median Finding in Sorted Arrays

[Dave]

Use a binary search. Assume that you have arrays a[m] and b[n] sorted in 
ascending order. If a[i] is the kth smallest element, then b[k-i-2] must be 
smaller than a[i], and b[k-i-1] must be larger (assuming arrays are 
zero-based). After using a binary search to find the value of i to meet 
this condition with k = (m+n)/2, you have to determine if a[i] or b[k-i-1] 
is the final answer. The complexity is O(log m).

Dave

On Sunday, January 5, 2014 5:34:12 AM UTC-6, Sanjay Rajpal wrote:

 Hi guys,

 Please help me in finding median of two sorted arrays of length m and n in 
 minimum possible time.


 Thanks,
 Sanjay


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Re: Saving and restoring Binary trees in files

[Dave]

@Don: Excellent solution. It requires little extra data to be stored, and 
it is easy to implement.
 
Dave

On Wednesday, November 13, 2013 9:31:47 AM UTC-6, Don wrote:

 The data file contains the pre-order traversal. For each node indicate the 
 contents of the node and two bits to indicate if it has a left and/or right 
 subtree. I did this with a tree containing strings. Each node was one line 
 in the file, with the first character being 'A' if the node is a leaf, 'B' 
 if it has only a left subtree, 'C' if it has only a right subtree, and 'D' 
 if it has both left and right subtrees. Then you read the line, store the 
 string minus the first character, and recursively build the left and then 
 right subtree, as appropriate.

 Don

 On Monday, November 11, 2013 1:20:05 PM UTC-5, atul007 wrote:

 @don : i did not get it , what will be data in file?


 On Mon, Nov 11, 2013 at 10:14 PM, Don dond...@gmail.com wrote:

 Save in preorder, tagging each node with two bits indicating if that 
 node has a left and right subtree.

 Then rebuild like this:

 Tree rebuild()
 {
Tree result = readNode();
Tree-left = hasLeftSubtree ? rebuild() : 0;
Tree-right = hasRightSubtree ? rebuild() : 0;
return result;

 }

 On Friday, November 8, 2013 1:00:35 PM UTC-5, atul007 wrote:

 @don :  it is not BST ,  it is binary tree ...so your approach will 
 not work in this case. 

 @kumar : save pre-order and in-order traversal with some delimiter in 
 b/w traversals. 

 pre-order : a b c d e 
 in-order   : c b e a d 

 write in file :- 

 a b c d e # c b e a d 

 now use pre-order and in-order traversal to re-create binary tree. 

 2) consider null node as # ..now write in file preorder traversal. 

 for eg :  a b c # # # d # # 

 3) save level order traversal of binary tree, where each level uses 
 # to distinguish between levels and * to mark null nodes 
 eg : a # b c # e * 
 a - level 1 
 b c - level 2 
 e NULL - level 3 

 shortcoming in 2 and 3 is use of character that can be part of tree 
 itself.So if node can contain # then you have to use some other 
 character to distinguish. 

 for solution 1 , you can write traversal in 2 lines instead of using 
 # 

 On 11/8/13, Vishnu vish...@gmail.com wrote: 
  1) save the nodes(value, left and right pointer) in pre-order 
 traversal 
  2) also save pointers of all node in same order 
  
  to restore 
  1) create new N nodes 
  2) do pointer mapping from old - new 
  3) restore nodes and replace old pointers to new 
  
  
  On Fri, Nov 8, 2013 at 8:50 PM, Don dond...@gmail.com wrote: 
  
  Save it in pre-order. 
  Rebuild by inserting nodes in the order they occur in the file. 
  
  
  On Friday, November 8, 2013 8:33:19 AM UTC-5, kumar raja wrote: 
  
  What is the effective way to save and restore the binary trees to 
 files 
  effectively? 
  
  
  
  
  
  
  
  
  
  
  
  
  
  Regards, 
  Kumar Raja. 
  
   -- 
  You received this message because you are subscribed to the Google 
 Groups 
  Algorithm Geeks group. 
  To unsubscribe from this group and stop receiving emails from it, 
 send an 
  email to algogeeks+...@googlegroups.com. 
  
  
  
  
  -- 
  Thanks, 
  Vishnu 
  
  -- 
  You received this message because you are subscribed to the Google 
 Groups 
  Algorithm Geeks group. 
  To unsubscribe from this group and stop receiving emails from it, 
 send an 
  email to algogeeks+...@googlegroups.com. 
  

  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com.




-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Generating random number without using rand()

[Dave]

See, e.g., 
http://en.wikipedia.org/wiki/Random_number_generation#Computational_methods. 
The algorithm creates a 32-bit random integer. It can be reduced to the 
range 0 to N with the modulus operator.
 
Dave

On Thursday, October 10, 2013 4:51:42 AM UTC-5, atul007 wrote:

 Hello,
Given integer N , How to generate random number from 0 to N without 
 using rand() 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.

[algogeeks] Re: Masked random generator

[Dave]

@Don: Note that a[j] - j is the number of non-excluded responses  a[j]. 
Here is the algorithm I would use:
 
k = rnd(N - S);
if( k  a[0] ) 
j = -1;
else
{
Use a binary search to find the largest j with 0 = j  S such that 
a[j] - j = k;
}
return k + j + 1;
 
The algorithm uses O(1) extra space and O(log S) time.
 
Dave

On Tuesday, October 8, 2013 9:48:58 AM UTC-5, Don wrote:

 Provide a function which returns a value randomly and uniformly selected 
 from the range 0..N-1 excluding values in the array a[S] containing sorted 
 values in the same range. A rejection algorithm would work well enough if S 
 is much smaller than N, but what if N is large and S is slightly smaller?

 Assume that you are given a pseudo-random generator int rnd(int n) which 
 returns a pseudo-random number uniformly distributed in the range 0..n-1.


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Interview Question

[Dave]

@Enchantress: I'm assuming that you are talking about cheating by copying 
from nearby students. 
 
If this is not the first exam, based on prior grades, put the A students in 
the back of the room, with the B students in front of the A students, the C 
students in front of the B students, the D students in front of the C 
students, and the F students in the front of the room. 
 
Put as many of the C students as you can in alternate seats, e.g., columns 
1, 3, 5,  If you can alternate all of the C students, put as many of 
the B students as you can in alternate seats. If you can alternate all of 
the B students, put as many of the D students as you can in alternate 
seats. If you can alternate all of the D students, put as many F students 
as you can in alternate seats. Finally, if you can alternate all of the F 
students, put as many A students as you can in alternate seats.
 
Rationale: An A or B student won't copy from anyone else, because he 
doesn't want someone else's mistake to mess up his grade. The C students 
have the most to gain by copying, but they will be spread out as much as 
possible. The D and F students will have only D and F students to copy 
from, so they won't gain much from copying.
 
Probably not the solution you were looking for, but I think an effective 
one.
 
Dave

On Saturday, July 27, 2013 1:02:11 PM UTC-5, enchantress wrote:

 Given m*n matrix and k students how can they be placed such that cheatig 
 is minimised.




-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Re: determine if 2 BSTs will be identical or not based on input order of its keys

[Dave]

@Don: You certainly can get by with only one workspace of size O(n). One 
side of the partitioning is done in-place, with the other side accumulated 
in the workspace and then copied back into the input array. That's a lot 
better than the O(n^2) worst case workspace required by your original 
algorithm.
 
Dave

On Tuesday, July 16, 2013 10:40:29 AM UTC-5, Don wrote:

 It definitely complicates things. I think that I would replaced the vector 
 parameters with pointers to the beginning and end of each array. The 
 partition is tricky because you need to make sure that both subtrees end up 
 in the same order they started in, which is difficult because most 
 partition algorithms are not stable. That's really the question I was 
 asking. Can you do that partition in place?

 Don


 On Sunday, July 14, 2013 2:48:46 PM UTC-4, sourabh wrote:

 You don't need to take vector for this you can have input in array also. 
 You just need to check the elements in each partition .
 On 12-Jul-2013 8:27 PM, Don dond...@gmail.com wrote:

 Can anyone modify this solution so that it does not duplicate the memory 
 at each level of recursion?

 (Here is my solution with the fix mentioned above)

 typedef std::vectorint btree;

 bool sameBstFormed(btree t1, btree t2)
 {
bool result;
if (t1.size() != t2.size()) result = false;
else if (t1.size() == 0) result = true;
else if (t1[0] != t2[0]) result = false;
else if (t1.size() == 1) result = true;
else
{
   btree left1, right1, left2, right2;
   for(int i = 1; i  t1.size(); ++i)
   {
  if (t1[i]  t1[0]) left1.push_back(t1[i]);
  else right1.push_back(t1[i]);
  if (t2[i]  t2[0]) left2.push_back(t2[i]);
  else right2.push_back(t2[i]);
   }
   result = sameBstFormed(left1, left2)  sameBstFormed(right1, 
 right2);
}
return result;
 }

 On Tuesday, July 9, 2013 5:41:57 PM UTC-4, Don wrote:

 Yes, you are right. Good catch.

 On Tuesday, July 9, 2013 2:13:47 PM UTC-4, Sambhavna Singh wrote:

 Amazing solution Don, thank you :)  You missed a small check in the 
 code: if(t1[0] != t2[0]) return 0;


 On Tue, Jul 9, 2013 at 11:27 PM, Don dond...@gmail.com wrote:

 The trees would be the same if
 1. The root is the same
 2. The left and right subtrees are both the same

 bool sameBstFormed(intVector t1, intVector t2)
 {
if (t1.size() != t2.size()) return false;   // Trees with 
 different number of nodes can't be the same
if (t1.size() == 0) return true;// Two empty trees 
 are equal
if (t1.size() == 1) return t1[0] == t2[0];   // Single node trees

// Partition left and right subtrees
intVector left1, right1, left2, right2;
for(int i = 1; i  n1; ++i)
{
   if (t1[i]  t1[0]) left1.add(t1[i]);
   else right1.add(t1[i]);
   if (t2[i]  t2[0]) left2.add(t2[i]);
   else right2.add(t2[i]);
}

return sameBstFormed(left1, left2)  sameBstFormed(right1, 
 right2);

 }

 On Thursday, June 6, 2013 1:57:49 AM UTC-4, Sambhavna Singh wrote:

 I came across this question on careercup: how do we go about finding 
 whether the BSTs formed by the given input order would be identical or 
 not 
 without actually forming the tree? 

 Link: 
 http://www.careercup.**com**/question?id=19016700http://www.careercup.com/question?id=19016700
  
  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, 
 send an email to algogeeks+...@googlegroups.com**.
  
  


  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com.
  
  



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Re: Highest reminder

[Dave]

The highest remainder when dividing n by a number less than n is 
floor((n-1)/2).
For n = 11, floor((11-1)/2) = floor(10/2) = floor(5) = 5.
For n = 17, floor((17-1)/2) = 8
For n = 23, floor((23-1)/2) = 11
 
For n = 12, floor((12-1)/2) = floor(11/2) = floor(5.5) = 5.
Etc.
 
Dave
 

On Wednesday, May 29, 2013 1:36:13 PM UTC-5, Ankit wrote:

 Hi,

 Number 23: =  11 * 1 + 12   Number/2 = 11.5

 Number 17: = 9 * 1 + 8   Number/2 = 8.5

 So, its neither floor(n/2) +- 1, nor ceil(n/2) +- 1


 On Wed, May 29, 2013 at 2:19 PM, Ankit Sambyal 
 ankitsam...@gmail.comjavascript:
  wrote:

 Hi Nikhil,

 Highest remainder can't be floor(n/2) - 1.
 If n = 11, highest remainder would be 5 when it is divided by 6, but your 
 formula gives 4.



 On Mon, May 27, 2013 at 8:16 PM, Nikhil Kumar 
 niksin...@gmail.comjavascript:
  wrote:

 Since we need to divide so the quotient should be at least 1, and we 
 need greatest remainder, so we need the least no. which will give the 
 quotient 1 upon dividing and that would be the no. you described.
 Also you would have noted the greatest remainder would be  floor(n/2)-1 .


 On Thursday, 16 May 2013 13:56:40 UTC+5:30, Soumya Prasad Ukil wrote:


 For a given number when divided by a number between 1 and n. I figured 
 out that highest reminder can be got if I divide the number by (⌊(n/2)⌋
 +1) .Can anyone give me pointers ?

  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send 
 an email to algogeeks+...@googlegroups.com javascript:.
  
  


  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.
  
  




 -- 

 *Ankit Agarwal*


 

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Minimum number of coins to SUM to S

[Dave]

@Don: The greedy algorithm will work for any S if the set of coins 
satisfies the following conditions:
 
1. There is a one-unit coin.
2. Each coin has value at least twice the value of the next less valuable 
coin.
 
E.g., U.S. coin system has values 1, 5, 10, 25, 50, and 100 cents. The 
conditions above are satisfied, so the greedy algorithm works.
 
E.g., The greedy algorithm does not work with a coin system with 1, 4, and 
5 unit coins. 8 units can be made with two 4-unit coins, but the greedy 
algorithm uses 5, 1, 1, and 1.
 
Dave

On Tuesday, May 28, 2013 9:55:01 AM UTC-5, Don wrote:

 This is a DP approach which is good if you need to perform the 
 operation for a large number of values of S. 
 For many combinations of coins, a greedy approach will work, but there 
 are combinations of coins where the greedy approach does not work. The 
 method below will work for any set of available coins. 
 Don 

 #include stdio.h 

 int main() 
 { 
 const int numCoins = 6; 
 const int maxS = 1; 
 int coins[numCoins] = {1,5,10,25,50,100};   // You can change this 
 if you want different sets of coins 
 int min[maxS]; 
 int i, j; 

 for(i = 1; i  maxS; ++i) min[i] = 10; 
 min[0] = 0; 

for(i = 0; i  maxS; ++i) 
   for(j = 0; j  numCoins; ++j) 
  if ((i+coins[j]  maxS)  (coins[i+coins[j]]  coins[i])) 
  coins[i+coins[j]] = coins[i] + 1; 

// Now coins[S] is the minimum number of coins required to sum to S 
 } 

 On May 18, 5:22 pm, rahul sharma rahul23111...@gmail.com wrote: 
  Minimum of coins to sum s 


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

Re: [algogeeks] Re: Array of intergers with repeating elements

[Dave]

@Pankaj: Can you give more details of your algorithm, including the big-O 
order of time and space. It certainly is not difficult to do it in O(n log 
n) time and O(n) space, as this can be accomplished by a merge-sort. For 
fixed data size, O(n) time and O(n) space can be achieved by a radix sort. 
Once the data is sorted, it is easy to find the unique element.
 

On Friday, May 10, 2013 3:26:13 AM UTC-5, pankaj joshi wrote:

 Hi,
  
 we can calculate the frequency of all element, Assign sort them in 
 increasing order of frequency.
 then the first element of sorted list will be the return element. 
 0bn
  
 we can implement it by Min Heap(which is based upon the frequency and 
 reorganise itself 
 as the frequency of element change (dynamically)).


  
 On Thu, May 9, 2013 at 12:41 AM, MAC macat...@gmail.com javascript:wrote:

  sry link was not pasted

 http://stackoverflow.com/questions/7338070/finding-an-element-in-an-array-where-every-element-is-repeated-odd-number-of-tim
  
 thanks 
 --mac
  

 On Thu, May 9, 2013 at 12:40 AM, MAC macat...@gmail.com javascript:wrote:

 if one can explin me this i think this problem will get solved 


 thanks 
 --mac
  

 On Wed, May 8, 2013 at 12:02 AM, MAC macat...@gmail.com 
 javascript:wrote:

  
 I was asked this in recent amazon onsite interview and asked o write 
 code 

 Given an Array of integers . N elements occur k times and one element 
 occurs b times, in other words there are n+1 distinct Elements. Given 
 that 0  b  k find the element occurring b times.
  
 We know k is NOT even .


 thanks 
 --mac



  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To unsubscribe from this group and stop receiving emails from it, send an 
 email to algogeeks+...@googlegroups.com javascript:.
  
  




 -- 
  Regards,

 Pankaj Kumar Joshi 

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email 
to algogeeks+unsubscr...@googlegroups.com.

[algogeeks] Re: Print a Random word from a file. Input is path to a file, constraints- No extra memory like hashing etc. All the words in the file should have equal probability.

[Dave]

Oops. The statement  int I = 1 in the above should be  int k = 1. Sorry.
 
Dave

On Sunday, May 5, 2013 9:10:37 PM UTC-5, Dave wrote:

 @Nishant: I'm assuming that you don't know the number of words in the 
 file, and that you don't want to store them all. Here is an algorithm that 
 requires you to store only two words and an integer.
 Assume double function random() returns a uniformly distributed random 
 number = 0.0 and  1.0.
  
 int i = 1
 read first word from file into string save;
 while not EOF
 {
 read next word from file into string temp;
 k++;
 if( k * random()  1.0 )
 copy temp to save; // happens with probability 1/k
 }
 print save;
 Here is why this works. The k-th word is initially selected with 
 probability 1/k. It is replaced with the k+1st word with probability 
 1/(k+1). Thus, the k-th word is not replaced with the k+1st word with 
 probability 1 - 1/(k+1) = k/(k+1). Similarly, it is not replaced with the 
 k+2nd word with probability (k+1)/(k+2). Etc. This means that the k-th word 
 was selected and survives to the EOF with probability 
  
 1/k * k/(k+1) * (k+1)/(k+2) * ... * (n-1)/n, where n is the number of 
 words in the file.
  
 Every numerator equals the preceding denominator, so the product collapses 
 to 1/n. This is true for any k with 1 = k = n, proving that the algorithm 
 produces the desired result.

 Dave

 On Sunday, May 5, 2013 7:44:01 AM UTC-5, Nishant Pandey wrote:

 Hi Guys,

 In this problem i am wondering how it will be done without extra memory 
 space, though we can easily do it with hashing and random funcs().
 Is there any solution for this , 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.

[algogeeks] Re: Print a Random word from a file. Input is path to a file, constraints- No extra memory like hashing etc. All the words in the file should have equal probability.

[Dave]

@Nishant: I'm assuming that you don't know the number of words in the file, 
and that you don't want to store them all. Here is an algorithm that 
requires you to store only two words and an integer.
Assume double function random() returns a uniformly distributed random 
number = 0.0 and  1.0.
 
int i = 1
read first word from file into string save;
while not EOF
{
read next word from file into string temp;
k++;
if( k * random()  1.0 )
copy temp to save; // happens with probability 1/k
}
print save;
Here is why this works. The k-th word is initially selected with 
probability 1/k. It is replaced with the k+1st word with probability 
1/(k+1). Thus, the k-th word is not replaced with the k+1st word with 
probability 1 - 1/(k+1) = k/(k+1). Similarly, it is not replaced with the 
k+2nd word with probability (k+1)/(k+2). Etc. This means that the k-th word 
was selected and survives to the EOF with probability 
 
1/k * k/(k+1) * (k+1)/(k+2) * ... * (n-1)/n, where n is the number of words 
in the file.
 
Every numerator equals the preceding denominator, so the product collapses 
to 1/n. This is true for any k with 1 = k = n, proving that the algorithm 
produces the desired result.

Dave

On Sunday, May 5, 2013 7:44:01 AM UTC-5, Nishant Pandey wrote:

 Hi Guys,

 In this problem i am wondering how it will be done without extra memory 
 space, though we can easily do it with hashing and random funcs().
 Is there any solution for this , 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.

[algogeeks] Re: least common ancestore bst

[Dave]

@Rahul: You must know if a node is its own ancestor or not. This is a 
matter of definition. 
 
If a node is its own ancestor, and if n1 is an ancestor of n2, then n1 is 
the least common ancestor of n1 and n2. 
 
If a node is not its own ancestor, and if n1 is an ancestor of n2, then the 
parent of n1 is the least common ancestor. 
 
It seems that common usage is that a node is its own ancestor; see, e.g., 
http://en.wikipedia.org/wiki/Lowest_common_ancestor.
 
Dave

On Sunday, April 21, 2013 11:56:01 AM UTC-5, rahul sharma wrote:

 int leastCommanAncestor(struct node* root, int n1, int n2)
 {
  if(root==NULL)
  return -1;
  if(root-datan1  root-datan2)
  return leastCommanAncestor(root-left,n1,n2);
  else if(root-datan1  root-datan2)
  return leastCommanAncestor(root-right,n1,n2);
  return root-data;
   
 }

 Does this code miss any case?N suppose if we have to find LCA of n1 and n2 
 and suppose n1 is parent of n2 ..then this will return n1..is this fyn or 
 if n1 is parent of n2 then we should return -1??

 Plz. comment


-- 
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: algorithm to sort based on frequency.

[Dave]

@Varun: Here is an algorithm using sorting only:
 
1. Append an index onto each number, so your example becomes {{4,0}, {3,1}, 
{2,2}, etc.}
 
2. Sort the numbers and their associated indices into ascending order by 
number. Your example becomes {{2,2}, {2,6}, {3,1}, {4,0}, {4,4}, etc.}. If 
the sort is not stable, the indices on equal numbers may not be in order, 
as I've shown here, but that doesn't matter. It will be taken care of in 
the next step.
 
3. Scan the array, and collapse every sequence of adjacent entries with 
equal numbers into one entry with the lowest index, and append the 
frequency to the entry. Your example becomes {{2,2,2}, {3,1,1}, {4,0,2}, 
etc.}
 
4. Sort the array with frequency as the primary key and index as the 
secondary key. You get {{4,0,2}, {2,2,2}, {6,5,2}, {3,1,1}, {5,1,3}}.
 
5. Reexpand the array by repeating each number according to its frequency, 
giving {4,4,2,2,6,6,3,5}.
 
Dave

On Wednesday, February 1, 2012 2:58:43 AM UTC-6, Varun wrote:

 I was asked this question sometime during an interview.

 WE have an array of known length. The elements in array can be repetitive.
 now sort the array based on frequency of occurrence of each element in 
 array.
 Eg: a= {4.3.2.5.4.6.2.6}
 after sorting a={4,4,2,2,6,6,3,5}

 4,2,6 all occurs twice, in this case retain the order in which they 
 appeared in original array.
 I was able to give a solution using hashing the elements of the array to a 
 new array, and if hash matches, incrementing the count, and then sort the 
 hash values. Later, re scan the array to retain the order in case there's a 
 match in frequency of any two element.

 Looking for better alternatives.
 Please pour in.


-- 
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?

[Dave]

@Kumar0746: Technically, you can't solve an _expression_; you can solve an 
_equation_, which is a statement of the form expression = expression, which 
is what you have. 
 
Don's suggestion is a good one. Another way is to call the expression on 
the left side of the equation f(x) and the expression on the right side of 
the equation g(x), and calculate f(0), g(0), f(1), and g(1). Then 
 
x = (f(0) -g(0)) / (f(0) - g(0) - f(1) + g(1))
 
In the original poster's example, f(0) = 10, f(1) = 8, g(0) = -9, and g(1) 
= 1, so x = 19/12. Presuming that you want the exact answer, leave it in 
fractional form, and if the denominator is negative, then negate both 
numerator and denominator. Then divide both numerator and denominator by 
their gcd. Finally, if the denominator is 1, report the numerator as the 
answer; otherwise report the fraction numerator/denominator as the answer.
 
Dave

On Thursday, April 4, 2013 11:43:20 AM UTC-5, Don wrote:

 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 kumar0...@gmail.com 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: Print tree node which sum

[Dave]

@Marti: I'm not quite sure if you mean that there are two problems, one 
with a BST and the other with an ordinary tree, or if you mean that one of 
the summands comes from a BST and the other comes from an ordinary tree. 
 
If both values come from a BST, do two simultaneous inorder traversals, one 
forwards (from left to right), and the other backwards (from right to 
left). If the sum of the two current elements is less than the value, 
advance the forward traversal, while if the sum is greater than the value, 
advance the backward traversal. Quit when equality is reached or when the 
two traversals reach the same element. O(n) time and O(log n) space if the 
BST is reasonably balanced, although the space can be as large as O(n) if 
the BST is severly unbalanced (as in case it has degenerated into a linked 
list). 
 
In order to do two simultaneous traversals, use two stacks to keep track of 
the state, as recursion won't allow you to do them.
 
Dave

On Tuesday, March 5, 2013 1:54:30 AM UTC-6, marti wrote:

 Given a value , print two nodes that sum to the value in a BST and normal 
 tree.. time:O(n), space O(logn).


-- 
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

[Dave]

@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, visit https://groups.google.com/groups/opt_out.

[algogeeks] Re: FInd unique element.

[Dave]

@Marti: If you know m and k, and if m is even and k is odd, then xoring the 
elements of the array will give the integer that occurs k times. But this 
is not a general algorithm for arbitrary m and k.
 
Dave

On Sunday, February 24, 2013 1:24:23 AM UTC-6, marti wrote:

 A hint is to use XOR for linear time..but how?

 On Friday, February 22, 2013 12:58:07 AM UTC+5:30, marti wrote:

 How do I Find the Unique Element that Appears exactly k Times in an Array?
  the problem is given an integer array, only one integer appears* k* times, 
 all the other integers appears *m* times in the array (*k**m*). Find 
 out that integer.



-- 
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.

Re: [algogeeks] Re: perfect square condition checking....

[Dave]

@Gaurav: Does it work for n = 25 or for n = 8? I think you've confused 
perfect square with power of two.
 
Dave

On Wednesday, February 6, 2013 11:32:55 PM UTC-6, Gaurav Rana wrote:

 if(n(n-1)==0)
 //perfect square


 On Thu, Feb 7, 2013 at 3:01 AM, Don dond...@gmail.com javascript:wrote:

 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 anilsharmau...@gmail.com
 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+...@googlegroups.com javascript:.
 For more options, visit https://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] Generating mazes

[Dave]

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.

Re: [algogeeks] matrix Multiplication

[Dave]

@Koup: No, I meant O(n^3 log k). Sorry.
 
Dave

On Sunday, January 20, 2013 3:09:00 AM UTC-6, Koup wrote:

 I need to multiply an array A by it self. Is there an algorithm that does 
 array multiplication with complexity O(n^2)?Doesn't it take at least O(n^3)?

 On Sun, Jan 20, 2013 at 12:44 AM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Guneesh: I think you mean to say that the complexity of both the 
 iterative and recursive algorithms is O(n^3 log k), using the notation of 
 the original poster (A is n-by-n, and it is to be raised to the power k).
  
 If what you really need is a way to calculate A^k * x, for some vector x, 
 it may be cheaper to use matrix-vector multiplication k times; this will be 
 O(n^2 * k).
  
 Dave

 On Saturday, January 19, 2013 7:30:50 AM UTC-6, Guneesh wrote:

 both recursive and iterative codes are O(nlogn) algos..
 but memory will be more in recursion..
 so we will prefer iteration 

  -- 
  
  




-- 

[algogeeks] Re: Check simple polygon

[Dave]

@Shady: See http://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 ? 

-- 

Re: [algogeeks] matrix Multiplication

[Dave]

@Guneesh: I think you mean to say that the complexity of both the iterative 
and recursive algorithms is O(n^3 log k), using the notation of the 
original poster (A is n-by-n, and it is to be raised to the power k).
 
If what you really need is a way to calculate A^k * x, for some vector x, 
it may be cheaper to use matrix-vector multiplication k times; this will be 
O(n^2 * k).
 
Dave

On Saturday, January 19, 2013 7:30:50 AM UTC-6, Guneesh wrote:

 both recursive and iterative codes are O(nlogn) algos..
 but memory will be more in recursion..
 so we will prefer iteration 

-- 

Re: [algogeeks] matrix Multiplication

[Dave]

@Guneesh: I don't think your code is correct. You want val to take on the 
values n, n^2, n^4, n^8, ..., whereas in your code, val takes on the values 
1,n, n^2, n^3,   The algorithm should be more like this:
 
int power()
{
int ans=1,val=n;
while(k)
{
if(k1)ans=ans*val;
k=k1;
if(k)val=val*val;
}
return ans;
}
 
Dave

On Saturday, January 19, 2013 5:06:25 AM UTC-6, Guneesh wrote:

 consider code to find n^k where n is an integer

 int power()
 {
 int ans=1,val=1;
 while(k)
 {
 val=val*n;
 if(k1)ans=ans*val;
 k=k1;
 }
 return ans;
 }

 now if n is is a matrix all you have to do is replace * by matrix 
 multiplication algorithm


-- 

Re: [algogeeks] Dutch National Flag Algorithm

[Dave]

@Pralaybi: While this is a nice solution to the Dutch National Flag 
problem, the problem the original poster presented, and called the Dutch 
National Flag problem, is different. What the given problem really amounts 
to is transposing a 3-by-(n/3) array stored in a linear array into an 
(n/3)-by-3 array, in-place. For algorithms, google in situ 
matrix transposition and in place matrix transposition. I'm not sure 
that an O(n)-time algorithm exists.
 
Dave
 

On Tuesday, January 15, 2013 2:08:15 PM UTC-6, pralaybi...@gmail.com wrote:

 Hi,

 You could try something like this.

 [image: Inline image 1]

 One pass thru the array (jack here, sorry for the bad naming) and you are 
 done!

 Cheers :) 



 On Mon, Jan 14, 2013 at 1:37 AM, Ankit Tripathi 
 ankittri...@gmail.comjavascript:
  wrote:

 Hello everyone,
 Recently I encountered following program :
 Given an integer array of n elements ( where n is a multiple of 3 ),
 example : *a1, a2, a3, a4, b1, b2, b3, b4, c1, c2, c3, c4*.
 You have to rearrange the array in such a manner that the elements of 
 array becomes :
 *a1, b1, c1, a2, b2, c2, a3, b3, c3, a4, b4, c4*.

 Time complexity = O(n)
 Space complexity = O(1).

 I was able to write a code where it took *O(n) time, but in O(n) space*.
 Can anybody suggest me a way to do the code in *O(1) space and O(n) time?
 *
  
 -- 
  
  




-- 

Re: [algogeeks] Re: perfect square condition checking....

[Dave]

@Bharat: It can be proven that Newton's method for square root, x(n+1) = 
(x(n) + a / x(n))/2, always converges to sqrt(a) if a  0 and x(0)  0. It 
is not difficult, so let e(n) = x(n) - sqrt(a), the error in the n-th 
iteration, and find the recurrence for e(n+1) in terms of e(n) and a. You 
should get e(n+1) = e(n)^2 / (2*(e(n) + sqrt(a))). You can then observe 
that if x(0)  0, then e(1) = 0, and if e(n)  0 then 0  e(n+1)  e(n) / 
2, proving convergence. You can further observe that if e(n) is small, 
then convergence is quadratic: e(n+1) = O(e(n)^2).
 
Dave

On Monday, January 14, 2013 2:09:22 AM UTC-6, bharat 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 dond...@gmail.com javascript: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 bagop...@gmail.com 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 malu@gmail.com 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 dondod...@gmail.com 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

[Dave]

@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: Linked List question

[Dave]

@Don: You did, of course, see the OP's revision in 
https://groups.google.com/d/msg/algogeeks/Be3WBebCDCk/_Mb0HUQ93WoJ, did you 
not?
 
Dave

On Thursday, January 3, 2013 3:08:40 PM UTC-6, Don wrote:

 The spec says that the list is infinite, so I don't think that is 
 possible in finite time. 
 Don 

 On Jan 2, 7:53 pm, Dave dave_and_da...@juno.com wrote: 
  @Don: HaHa. That's cute, but don't you really think the problem is to 
  return any node in the list with equal probability? 
  
  Dave 
  
  
  
  
  
  
  
  On Wednesday, January 2, 2013 4:48:15 PM UTC-6, Don wrote: 
   Why not just return the first node? That is as random as any other 
   node. 
   Don 
  
   On Dec 27 2012, 5:01 am, naveen shukla 
   naveenshuklasweetdrea...@gmail.com wrote: 
Given a linked list of infinite length. Write a function to return a 
   random 
node. 
  
Constraints: 
  
1 You can traverse a singly linked list only once. 
2 You can not use any extra space. 
  
Thanks in advance. 


-- 

[algogeeks] Re: Linked List question

[Dave]

@Don: HaHa. That's cute, but don't you really think the problem is to 
return any node in the list with equal probability?
 
Dave

On Wednesday, January 2, 2013 4:48:15 PM UTC-6, Don wrote:

 Why not just return the first node? That is as random as any other 
 node. 
 Don 

 On Dec 27 2012, 5:01 am, naveen shukla 
 naveenshuklasweetdrea...@gmail.com wrote: 
  Given a linked list of infinite length. Write a function to return a 
 random 
  node. 
  
  Constraints: 
  
  1 You can traverse a singly linked list only once. 
  2 You can not use any extra space. 
  
  Thanks in advance. 


-- 

Re: [algogeeks] Linked List question

[Dave]

@Doom: Yes. It is necessary to go through the entire list. The code could 
look like this:
 
int* p = head;
int k = 1;
while( head )
{
head = head - next;
k++;
if( k * (double)rand()  RAND_MAX )
p = head;
}
 
Dave

On Sunday, December 30, 2012 12:40:28 PM UTC-6, Doom wrote:

 Hi Dave

 Please help me with some additional clarification regarding the 
 implementation of this algo. How do we make use of random number generator?

 And is it necessary to traverse the list until the end? 


 On Friday, 28 December 2012 19:35:07 UTC+5:30, Dave wrote:

 @Sanjeev: Set a pointer p to the first node. Traverse the list. When at 
 the kth node, set p to the kth node with probability 1/k. When you reach 
 the end of the list, return p, which will point to a random node with 
 uniform probability.
  
 Dave

 On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:

 i mean the length of the linked list is not known to us.
 @udit how can we do this in single traversal ? i think we need to 
 traverse the linked list twice in your case.
 Please reply if i am wrong ?

 On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal udit...@gmail.comwrote:

 If the length of the linked is infinite then the above algo would do
 the needful.
 In case you have a finite length linked list, then you can normalize
 the random value using following:
 Suppose length of linked list is: l
 random number is: r; and r  l
 then new random number would be: r1 = r%l;
 now again use the above algo using new random number r1;

 On Thu, Dec 27, 2012 at 4:12 PM, Vineeth vineet...@gmail.com wrote:
  You said : Given a linked list of infinite length
 
  On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
  naveenshukla...@gmail.com wrote:
  But suppose a random number generate a value 5 and your linked list 
 has only
  four elements. In that case what would be the answer ???
 
 
  On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri 
 hpre...@gmail.com
  wrote:
 
  Well my algo will be Something like this
 
  1 Get a Random number. Perhaps You can have the function like 
 Randon(List
  *head, int Randomnumber)
 
  2 Use the function argument Randomnumber to loop the list.
  i.e. for(int count=0;count=Randomnumber;count++ ){
 head = head - next;
  }
 
  3 print (head-value);
 
  4 return ;
 
  Now as we are using byvalue when we return the value of head 
 remains the
  same old head value. So everytime we call we are traversing the 
 same old
  list.
 
   The Random variable can be taken inside the function itself if the 
 user
  is not taking the random value.
   i.e. int Randomnumber = random();  and now the user can calll 
 Simple
  Random(head);
 
 
 
  On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
  naveenshukla...@gmail.com wrote:
 
  random node
 
 
  --
 
 
 
 
 
 
  --
  With Best Wishes
 
  From:
 
  Naveen Shukla
  IIIT Allahabad
  B.Tech IT 4th year
  Mob No: 07860896972
  E-mail naveenshukla...@gmail.com
 
  --
 
 
 
  --
 
 



 --
 Udit Agarwal
 B.Tech. ( Information Technology ) , 7th Semester,
 Indian Institute of Information Technology
 Allahabad - 211012, India
 Email : udit...@gmail.com
 Mobile: +91-9411656264

 --





 -- 
 With Best Wishes

 From:

 Naveen Shukla
 IIIT Allahabad
 B.Tech IT 4th year
 Mob No: 07860896972
 E-mail naveenshukla...@gmail.com 



-- 

Re: [algogeeks] Linked List question

[Dave]

@Sanjeev: Set a pointer p to the first node. Traverse the list. When at the 
kth node, set p to the kth node with probability 1/k. When you reach the 
end of the list, return p, which will point to a random node with uniform 
probability.
 
Dave

On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:

 i mean the length of the linked list is not known to us.
 @udit how can we do this in single traversal ? i think we need to traverse 
 the linked list twice in your case.
 Please reply if i am wrong ?

 On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal udit...@gmail.comjavascript:
  wrote:

 If the length of the linked is infinite then the above algo would do
 the needful.
 In case you have a finite length linked list, then you can normalize
 the random value using following:
 Suppose length of linked list is: l
 random number is: r; and r  l
 then new random number would be: r1 = r%l;
 now again use the above algo using new random number r1;

 On Thu, Dec 27, 2012 at 4:12 PM, Vineeth vineet...@gmail.comjavascript: 
 wrote:
  You said : Given a linked list of infinite length
 
  On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
  naveenshukla...@gmail.com javascript: wrote:
  But suppose a random number generate a value 5 and your linked list 
 has only
  four elements. In that case what would be the answer ???
 
 
  On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri 
 hpre...@gmail.com javascript:
  wrote:
 
  Well my algo will be Something like this
 
  1 Get a Random number. Perhaps You can have the function like 
 Randon(List
  *head, int Randomnumber)
 
  2 Use the function argument Randomnumber to loop the list.
  i.e. for(int count=0;count=Randomnumber;count++ ){
 head = head - next;
  }
 
  3 print (head-value);
 
  4 return ;
 
  Now as we are using byvalue when we return the value of head remains 
 the
  same old head value. So everytime we call we are traversing the same 
 old
  list.
 
   The Random variable can be taken inside the function itself if the 
 user
  is not taking the random value.
   i.e. int Randomnumber = random();  and now the user can calll Simple
  Random(head);
 
 
 
  On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
  naveenshukla...@gmail.com javascript: wrote:
 
  random node
 
 
  --
 
 
 
 
 
 
  --
  With Best Wishes
 
  From:
 
  Naveen Shukla
  IIIT Allahabad
  B.Tech IT 4th year
  Mob No: 07860896972
  E-mail naveenshukla...@gmail.com javascript:
 
  --
 
 
 
  --
 
 



 --
 Udit Agarwal
 B.Tech. ( Information Technology ) , 7th Semester,
 Indian Institute of Information Technology
 Allahabad - 211012, India
 Email : udit...@gmail.com javascript:
 Mobile: +91-9411656264

 --





 -- 
 With Best Wishes

 From:

 Naveen Shukla
 IIIT Allahabad
 B.Tech IT 4th year
 Mob No: 07860896972
 E-mail naveenshukla...@gmail.com javascript: 


-- 

Re: [algogeeks] Linked List question

[Dave]

@Udit: Here is the proof: At step k, node k is selected with probability 
1/k. On the (k+1)st step, node k is replaced with probability 1/(k+1). Thus 
it is retained with probability 1 - 1/(k+1) = k/(k+1). On subsequent steps, 
node k is retained with probabilities (k+1)/(k+2), (k+2)/(k+3), ..., 
(n-1)/n. Thus, node k is selected on the kth step and then retained until 
the end of the list with probability 1/k * k/(k+1) * (k+1)/(k+2) * ... * 
(n-1) / n. Each denominator cancels with the succeeding numerator, so the 
product collapses to 1/n.
 
Dave

On Friday, December 28, 2012 10:46:17 AM UTC-6, Udit Agarwal wrote:

 @Dave: U said that the node p returned will be assigned to some kth 
 node with probability 1/k. then the probability for p to be assigned 
 to 1,2,3... nodes would be like 1/1, 1/2, 1/3, and so on.. the how is 
 the node p is assigned with uniform probability. 

 On Fri, Dec 28, 2012 at 7:35 PM, Dave dave_an...@juno.com javascript: 
 wrote: 
  @Sanjeev: Set a pointer p to the first node. Traverse the list. When at 
 the 
  kth node, set p to the kth node with probability 1/k. When you reach the 
 end 
  of the list, return p, which will point to a random node with uniform 
  probability. 
  
  Dave 
  
  On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote: 
  
  i mean the length of the linked list is not known to us. 
  @udit how can we do this in single traversal ? i think we need to 
 traverse 
  the linked list twice in your case. 
  Please reply if i am wrong ? 
  
  On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal udit...@gmail.com 
 wrote: 
  
  If the length of the linked is infinite then the above algo would do 
  the needful. 
  In case you have a finite length linked list, then you can normalize 
  the random value using following: 
  Suppose length of linked list is: l 
  random number is: r; and r  l 
  then new random number would be: r1 = r%l; 
  now again use the above algo using new random number r1; 
  
  On Thu, Dec 27, 2012 at 4:12 PM, Vineeth vineet...@gmail.com wrote: 
   You said : Given a linked list of infinite length 
   
   On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla 
   naveenshukla...@gmail.com wrote: 
   But suppose a random number generate a value 5 and your linked list 
   has only 
   four elements. In that case what would be the answer ??? 
   
   
   On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri 
   hpre...@gmail.com 
  
   wrote: 
   
   Well my algo will be Something like this 
   
   1 Get a Random number. Perhaps You can have the function like 
   Randon(List 
   *head, int Randomnumber) 
   
   2 Use the function argument Randomnumber to loop the list. 
   i.e. for(int count=0;count=Randomnumber;count++ ){ 
  head = head - next; 
   } 
   
   3 print (head-value); 
   
   4 return ; 
   
   Now as we are using byvalue when we return the value of head 
 remains 
   the 
   same old head value. So everytime we call we are traversing the 
 same 
   old 
   list. 
   
The Random variable can be taken inside the function itself if 
 the 
   user 
   is not taking the random value. 
i.e. int Randomnumber = random();  and now the user can calll 
 Simple 
   Random(head); 
   
   
   
   On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla 
   naveenshukla...@gmail.com wrote: 
   
   random node 
   
   
   -- 
   
   
   
   
   
   
   -- 
   With Best Wishes 
   
   From: 
   
   Naveen Shukla 
   IIIT Allahabad 
   B.Tech IT 4th year 
   Mob No: 07860896972 
   E-mail naveenshukla...@gmail.com 
   
   -- 
   
   
   
   -- 
   
   
  
  
  
  -- 
  Udit Agarwal 
  B.Tech. ( Information Technology ) , 7th Semester, 
  Indian Institute of Information Technology 
  Allahabad - 211012, India 
  Email : udit...@gmail.com 
  Mobile: +91-9411656264 
  
  -- 
  
  
  
  
  
  -- 
  With Best Wishes 
  
  From: 
  
  Naveen Shukla 
  IIIT Allahabad 
  B.Tech IT 4th year 
  Mob No: 07860896972 
  E-mail naveenshukla...@gmail.com 
  
  -- 
  
  



 -- 
 Udit Agarwal 
 B.Tech. ( Information Technology ) , 7th Semester, 
 Indian Institute of Information Technology 
 Allahabad - 211012, India 
 Email : udit...@gmail.com javascript: 
 Mobile: +91-9411656264 


-- 

[algogeeks] Re: Coin denomination

[Dave]

@Shady: I'm not sure what you mean by output N coins. With U.S. coins, 
you can need up to 4 pennies, 1 nickel, 2 dimes, 1 quarter, and 1 
half-dollar (or 4 pennies, 1 nickel, 2 dimes, and 3 quarters, if you don't 
use half-dollars, which are uncommon) to make any amount from 1 to 99 
cents. So should you output distinct coins (1,5,10,25,50), or repeat the 
coins the required number of times (1,1,1,1,5,10,10,25,50)?
 
Dave

On Friday, December 21, 2012 4:01:52 PM UTC-6, shady wrote:

 Given R and N, output N coins in the range from 1 to R such that average 
 number of coins needed to represent all the number in the range is 
 minimized. 

 Any idea ? hints ?


-- 

Re: [algogeeks] Re: Coin denomination

[Dave]

@Shady. That still didn't answer my question. Maybe I didn't frame it very 
well, so let me try again. Are you naming coins that you have one of or an 
infinite supply of? I.e., if you want to use two of a coin to make a 
certain sum, does it count in the N as one coin or two? More specifically, 
if I want to make 7 as (5,1,1), do I list the coins as (1,5), which is N=2, 
or (1,1,5), which is N=3?
 
Dave

On Saturday, December 22, 2012 4:34:24 AM UTC-6, shady wrote:

 We have *all kinds of denominations (1, 2, 3, R)*... therefore to 
 cover this range, we generally select coins like this 1, 2, 4, 8, 16... but 
 in this case... we can select* any N coins from R*, such that it *minimizes 
 the average coins used for all values in the range R*... like .

 6 can be represented by 2, 4
 15 - (1, 2, 4, 8)
 10 - (2, 8)



 On Sat, Dec 22, 2012 at 1:59 PM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Shady: I'm not sure what you mean by output N coins. With U.S. coins, 
 you can need up to 4 pennies, 1 nickel, 2 dimes, 1 quarter, and 1 
 half-dollar (or 4 pennies, 1 nickel, 2 dimes, and 3 quarters, if you don't 
 use half-dollars, which are uncommon) to make any amount from 1 to 99 
 cents. So should you output distinct coins (1,5,10,25,50), or repeat the 
 coins the required number of times (1,1,1,1,5,10,10,25,50)?
  
 Dave

 On Friday, December 21, 2012 4:01:52 PM UTC-6, shady wrote:

 Given R and N, output N coins in the range from 1 to R such that average 
 number of coins needed to represent all the number in the range is 
 minimized. 

 Any idea ? hints ?

  -- 
  
  




-- 

[algogeeks] Re: Inmobi Placement Paper

[Dave]

@Vamshi: The first answer should be min heap, not max heap. The reason 
is that you want to know what the smallest of the ten largest numbers 
you've found so far. So the algorithm is to place the first 10 numbers into 
the min heap. For each additional number x, if x is greater than the root 
of the heap (min element of the current top ten), then replace the root 
with x and re-establish the heap condition. When you are finished with the 
input, the numbers in the heap will be the largest ten numbers in the file.
 
Dave

On Saturday, December 1, 2012 11:54:22 AM UTC-6, vamshi vijay wrote:

 Hi friends

 http://www.iitplacementpapers.com/2012/09/inmobi-previous-placment-papers.html
 -- 
 With Regards,
 N.Vamshi Vijay,
 Mtech,CSE, IIT Kharagpur,
 Software Developer, Amazon India Development Center.


  

-- 

[algogeeks] Re: Output

[Dave]

@Rajesh: In binary, mask = 111...10 (with 4-byte ints, this is 27 
1-bits followed by 5 0-bits). The logical product of num with mask zeros 
out the low order 5 bits while retaining the high order 27 bits. Thus, res 
is num truncated to the largest multiple of 32 that does not exceed num. 56 
= (1*32 + 24) goes to 1*32 = 32, 64 (=2*32 + 0) stays at 2*32 = 64, and 127 
(=3*32 + 31) goes to 3*32 = 96.
 
Dave

On Saturday, November 24, 2012 2:45:24 AM UTC-6, rajesh pandey wrote:

 void dosomething(int num)
 {
 int mask=~(15-1);
 int res=nummask;
 printf(%d,res);
 }
 int main()
 {
 dosomething(56);
 dosomething(64);
 dosomething(127);
 return 0;
 }

 please explain  the logic behind the output.

 Thanks,
 Rajesh  


-- 

Re: [algogeeks] Re: time complexity of gcd euclid algo(recursive)

[Dave]

@Pralaybi: You've got it right. Since h is proportional to the log of the 
smaller number, we also can say that the complexity is O(log^2 (smaller 
number)).
 
Dave

On Friday, November 23, 2012 2:09:01 PM UTC-6, pralaybi...@gmail.com wrote:

 @Dave: Could you please correct me if am wrong here.
 1) So we are looking out for the worst case, and that happens when m and n 
 are consecutive Fibo numbers, being mutually prime to reach other.
 2) Its taking 5 iterations to reduce the number of digits in the smaller 
 of m and n, by one. Assuming there are h digits in the smaller number 
 from now on.
 3) Also, the computation cost is proportional to the number of digits, 
 hence cost is proportional to h. (Could you please elaborate a lil more on 
 this)
 4) So net complexity is h*h = O(quadratic)

 On Fri, Nov 16, 2012 at 8:50 PM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Sonesh: Not so. The worst case for Euclid's algorithm is when the 
 numbers are consecutive Fibonacci numbers. So (89,55) -- (55,34) -- 
 (34,21) -- (21,13) -- (13,8) -- (8,5), so it took 5 steps to reduce the 
 number of digits of the first number from 2 to 1. Asymptotically, the 
 number of digits reduces by log_10(phi) =  log_10((1+sqrt(5))/2) ~= 0.209, 
 where phi is the Golden Ratio, so it takes, on average, ~4.78 iterations to 
 reduce the numbers by 1 digit, in the worst case. But still, we can say 
 that Euclid's algorithm is O(log n).
  
 Dave

 On Friday, November 16, 2012 6:40:58 PM UTC-6, sonesh wrote:

 you see, in each step of recursion, the number of digits in *n* is 
 decrease by one(at least in worst case), so the complexity you can decide.

 On Tuesday, November 13, 2012 3:34:06 PM UTC+5:30, Shruti wrote:

 hi

 Can anyone help me find out the time complexity of recursive gcd 
 algorithm (using euclid's algo)
 i.e. for the following program :

 int gcd(int n,int m) //given nm
 {
if(n%m==0)
return m;
else
 return gcd(m,n%m);

 }

 i think the soln is lg(a*b) but have no idea how..

  -- 
 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/-/bCB-L41X6ukJ.

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 For more options, visit this group at 
 http://groups.google.com/group/algogeeks?hl=en.




-- 

Re: [algogeeks] Array problem

[Dave]

@Ansum: Notice that the problem does not ask to give a method of making as 
many numbers as possible equal, but only what the maximum number is. Here 
is an algorithm for achieving an array with the equality numbers I 
specified:
 
1. If the sum of the numbers is a multiple of n, then avg = sum/n is the 
target number. If every number is not equal to avg, find a number a[i] in 
the array that is smaller than avg and a number a[j] that is larger than 
avg. Then set a[i] = a[i]+1 and a[j] = a[j]-1. Repeat until every number 
equals avg. Result is that n numbers are equal.
 
2. If the sum of the numbers is not a multiple of n, pick any number, say 
a[1], as the target value. If there is any number a[k] from k = 2 to n-1 
such that a[k] != a[1], increase or decrease a[k] by 1 to make it closer to 
a[1] and respectively decrease or increase a[n] by 1. Repeat until every 
number a[k] = a[1] for k = 2 to n-1. Then a[1] to a[n-1] are equal but a[n] 
cannot be equal because then the sum of the numbers would be a multiple of 
n. Result is that n-1 numbers are equal.
 
Since you don't have to produce the maximally equal array, the algorithm I 
gave is the solution. Here it is in code (with C's 0-based array indexing):
 
int maxEqual( int n, int a[])
{
int i, sum = 0;
for( i = 0 ; i  n ; ++i )
sum += a[i];
return if sum % n == 0 ? n : n - 1;
}
 
Dave

On Thursday, November 22, 2012 1:25:43 AM UTC-6, Ansum Baid wrote:

 @Dave: Can you give a little insight on your approach?

 On Wed, Nov 21, 2012 at 6:52 PM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Ansum: Polycarpus should start by summing the numbers. If the sum is 
 divisible by n, then n numbers can be made equal. If the sum is not 
 divisible by n, then only n-1 numbers can be made equal.
  
 Dave

 On Wednesday, November 21, 2012 12:18:54 PM UTC-6, Ansum Baid wrote:

  This question has been taken from codeforces.com. Any idea how to 
 solve this ?

 Polycarpus has an array, consisting of *n* integers *a*1, *a*2, ..., *a*
 *n*. Polycarpus likes it when numbers in an array match. That's why he 
 wants the array to have as many equal numbers as possible. For that 
 Polycarpus performs the following operation multiple times:


- he chooses two elements of the array *a**i*, *a**j* (*i* ≠ *j*); 
- he simultaneously increases number *a**i* by 1 and decreases 
number *a**j* by 1, that is, executes *a**i* = *a**i* + 1 and *a**j*= 
*a**j* - 1. 

 The given operation changes exactly two distinct array elements. 
 Polycarpus can apply the described operation an infinite number of times.

 Now he wants to know what maximum number of equal array elements he can 
 get if he performs an arbitrary number of such operation. Help Polycarpus.
 Input

 The first line contains integer *n* (1 ≤ *n* ≤ 105) — the array size. 
 The second line contains space-separated integers *a*1, *a*2, ..., *a**n
 * (|*a**i*| ≤ 104) — the original array.
 Output

 Print a single integer — the maximum number of equal array elements he 
 can get if he performs an arbitrary number of the given operation.
 Sample test(s)
  input

 2
 2 1

 output

 1

 input

 3
 1 4 1

 output

 3


  -- 
  
  




-- 

Re: [algogeeks] Array problem

[Dave]

@Ansum: Polycarpus should start by summing the numbers. If the sum is 
divisible by n, then n numbers can be made equal. If the sum is not 
divisible by n, then only n-1 numbers can be made equal.
 
Dave

On Wednesday, November 21, 2012 12:18:54 PM UTC-6, Ansum Baid wrote:

  This question has been taken from codeforces.com. Any idea how to solve 
 this ?

 Polycarpus has an array, consisting of *n* integers *a*1, *a*2, ..., *a**n
 *. Polycarpus likes it when numbers in an array match. That's why he 
 wants the array to have as many equal numbers as possible. For that 
 Polycarpus performs the following operation multiple times:


- he chooses two elements of the array *a**i*, *a**j* (*i* ≠ *j*); 
- he simultaneously increases number *a**i* by 1 and decreases number *
a**j* by 1, that is, executes *a**i* = *a**i* + 1 and *a**j* = *a**j*- 1
. 

 The given operation changes exactly two distinct array elements. 
 Polycarpus can apply the described operation an infinite number of times.

 Now he wants to know what maximum number of equal array elements he can 
 get if he performs an arbitrary number of such operation. Help Polycarpus.
 Input

 The first line contains integer *n* (1 ≤ *n* ≤ 105) — the array size. The 
 second line contains space-separated integers *a*1, *a*2, ..., *a**n* (|*a
 **i*| ≤ 104) — the original array.
 Output

 Print a single integer — the maximum number of equal array elements he can 
 get if he performs an arbitrary number of the given operation.
 Sample test(s)
  input

 2
 2 1

 output

 1

 input

 3
 1 4 1

 output

 3




-- 

Re: [algogeeks] Re: time complexity of gcd euclid algo(recursive)

[Dave]

@Bharat: See, e.g., 
http://en.wikipedia.org/wiki/Euclidean_algorithm#Algorithmic_efficiency.
 
Dave

On Sunday, November 18, 2012 12:03:33 AM UTC-6, bharat wrote:

 @ Dave : can u pls explain the solution u gave .
 How can u say fibnocci sequence produces worst case ?

 On Fri, Nov 16, 2012 at 11:15 AM, Shruti Gupta 
 fundoo...@gmail.comjavascript:
  wrote:

 Don, thanks for the solution, Can u pls explain how a+b gets reduced by 
 atleast 25% 


 On Fri, Nov 16, 2012 at 3:42 AM, Don dond...@gmail.com javascript:wrote:

 Tail recursion is no different than a loop, so the complexity is the
 same as an iterative solution like this:

 int gcd(int a, int b)  // For ab
 {
 while(1)
 {
 int c = a % b;
 if (!c) return b;
 a = b;
 b = c;
 }
 }

 The complexity is log(a) + log(b) because each iteration reduces a+b
 by at least 25%.

 Don

 On Nov 13, 5:04 am, Shruti Gupta fundooshr...@gmail.com wrote:
  hi
 
  Can anyone help me find out the time complexity of recursive gcd 
 algorithm
  (using euclid's algo)
  i.e. for the following program :
 
  int gcd(int n,int m) //given nm
  {
 if(n%m==0)
 return m;
 else
  return gcd(m,n%m);
 
  }
 
  i think the soln is lg(a*b) but have no idea how..

 --
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 For more options, visit this group at 
 http://groups.google.com/group/algogeeks?hl=en.


  -- 
  
  




-- 

[algogeeks] Re: time complexity of gcd euclid algo(recursive)

[Dave]

@Sonesh: Not so. The worst case for Euclid's algorithm is when the numbers 
are consecutive Fibonacci numbers. So (89,55) -- (55,34) -- (34,21) -- 
(21,13) -- (13,8) -- (8,5), so it took 5 steps to reduce the number of 
digits of the first number from 2 to 1. Asymptotically, the number of 
digits reduces by log_10(phi) =  log_10((1+sqrt(5))/2) ~= 0.209, where phi 
is the Golden Ratio, so it takes, on average, ~4.78 iterations to reduce 
the numbers by 1 digit, in the worst case. But still, we can say that 
Euclid's algorithm is O(log n).
 
Dave

On Friday, November 16, 2012 6:40:58 PM UTC-6, sonesh wrote:

 you see, in each step of recursion, the number of digits in *n* is 
 decrease by one(at least in worst case), so the complexity you can decide.

 On Tuesday, November 13, 2012 3:34:06 PM UTC+5:30, Shruti wrote:

 hi

 Can anyone help me find out the time complexity of recursive gcd 
 algorithm (using euclid's algo)
 i.e. for the following program :

 int gcd(int n,int m) //given nm
 {
if(n%m==0)
return m;
else
 return gcd(m,n%m);

 }

 i think the soln is lg(a*b) but have no idea how..



-- 
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/-/bCB-L41X6ukJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Loan

[Dave]

@All: This probably is a scam.
 
Dave

On Tuesday, November 13, 2012 3:32:39 AM UTC-6, Virag wrote:

 Hello, I hope this e-mail reaches well. Just to let you know that I'm 
 presently in Spain for an Agricultural Conference but I'm in a serious fix; 
 I was mugged and lost all my money  cards. I'm so glad I wasn't hurt. 
  Please, will you be able to help me with some cash(USD3500) or any amount 
 you could afford to lend me. I'll definitely pay you back immediately I 
 return back home next weekend.

 I'll really appreciate your positive response and 'll forward you the 
 transfer details upon your response. Thank you for your attention and 
 looking forward to your corresponding letter. 
  
 Thanks  Regards
 Virag
 Head, Gender Studies
 Confidare Research, Bangalore
 The onset of victory is a victory in itself - Celebrate it.


-- 
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/-/WQAaUFsyx8QJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: swap objects without temp variable

[Dave]

@Don: This can be easily fixed, as there is no need to swap equal values, 
so:
 
void swap(int a, int b)
{
if( a != b )
{
a ^= b;
b ^= a;
a ^= b;
}
}

On Monday, November 5, 2012 10:41:42 AM UTC-6, Don wrote:

 Note that most of these methods fail if you try to swap an item with 
 itself. void swap(int a, intb)
 {
 a ^= b;
 b ^= a;
 a ^= b;
 }


 For example, swap(a[i], a[j]) will fail if i==j and swap is 
 implemented as 


 Don 

 On Nov 4, 3:32 pm, manish narayan.shiv...@gmail.com wrote: 
  Swapping two objects (not integers/chars),without using temp...? 
  my solution is using xor operation..is that right and ny other solutions 
 ? 


-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/2QXdGv1P-iMJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] swap objects without temp variable

[Dave]

@Shivam: Your one-line solution violates the sequence point rule. Hence, 
it is non-standard, and the result is compiler dependent.
 
Dave

On Monday, November 5, 2012 9:36:12 AM UTC-6, Shivam...aka Bboy 
rullz... wrote:

 in a single line 
 a^=b^=a^=b; 

 On 05/11/2012, atul anand atul.8...@gmail.com javascript: wrote: 
  a=a^b; 
  b=a^b; 
  a=a^b; 
  
  need to check if a and b are equal or not , bcozz a^a =0 
  
  On Mon, Nov 5, 2012 at 2:02 AM, manish narayan...@gmail.comjavascript: 
 wrote: 
  
  Swapping two objects (not integers/chars),without using temp...? 
  my solution is using xor operation..is that right and ny other 
 solutions 
  ? 
  
  -- 
  You received this message because you are subscribed to the Google 
 Groups 
  Algorithm Geeks group. 
  To view this discussion on the web visit 
  https://groups.google.com/d/msg/algogeeks/-/OxVSnZ1QjzMJ. 
  To post to this group, send email to 
  algo...@googlegroups.comjavascript:. 

  To unsubscribe from this group, send email to 
  algogeeks+...@googlegroups.com javascript:. 
  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 algo...@googlegroups.comjavascript:. 

  To unsubscribe from this group, send email to 
  algogeeks+...@googlegroups.com javascript:. 
  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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/17FE1cYGsVcJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: swap objects without temp variable

[Dave]

@Manish: Sure. 
 
a = a + b; 
b = a - b; 
a = a - b;
 
In 2-s complement arithmetic, it works even if a + b overflows.
 
Dave

On Sunday, November 4, 2012 2:32:43 PM UTC-6, manish wrote:

 Swapping two objects (not integers/chars),without using temp...?
 my solution is using xor operation..is that right and ny other solutions ?

-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/nc5h3uIL65AJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Range Checking Efficiently C++

[Dave]

@Atul: Try x = 0, a = 1, b = 2, for which (x  a  x  b) is false, but (x 
- a  b - x) is true.
 
Dave

On Saturday, October 27, 2012 5:43:17 AM UTC-5, ATul SIngh wrote:

 Thnks but i figured it out
 as 
 ( x = a  x  b )  
 or 
 ( x = a  x = b )

 could be written as
 x -a  b - xfor first case
 x -a = b - x for sec one

 Second set is more optimised as it contains  only one comparison  and 
 minus is  much efficient than comparison operator.



 -- 

 *ATul Singh** Software Engineer**, Interra Systems*
 Mobile : +91-9971794013
 www.interrrasystems.com
 [image: Facebook] http://www.facebook.com/atulsingh7890 [image: 
 Twitter]http://www.twitter.com/atulsng
  [image: LinkedIn] http://www.linkedin.com/in/atulsingh7890




-- 
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/-/pyvTrbonkq4J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Directi Campus Internship paper

[Dave]

@Ujjwal: Here's an algorithm for problem 2:
 
Given a number n, form the prime number factorization of n:
 
n = p1^k1 * p2^k2 * ... * pm^km, where the pi are distinct primes and ^ 
represents exponentiation.
 
If any ki = 1, terminate the factorization and report that n is not a 
Trojan number.
 
Then calculate gcd(k1,k2,...,km), e.g., by repeated applications of 
Euclid's Algorithm.
 
Finally, n is a Trojan number if and only if gcd(k1,k2,...,km) = 1.
 
Dave

On Wednesday, October 24, 2012 3:37:28 AM UTC-5, Ujjwal Arora wrote:

 We had to code 2 questions in 1.30 hr on codechef only. the questions are 
 as follow :

 1.) Implement Least Recently Used (LRU) algorithm - a well known algorithm 
 of operating systems. 

 2.) Find if a given number is Trojan Number. A Trojan number is a number 
 which is strong but not a perfect power (m^k). A Strong number is a number 
 which has a prime number 'p' itsfactor and also divisible by p^2 i.e 
 divisible by a prime and also by its square. 
 Hence, Trojan number is a strong number , which can't be represented as 
 m^k.


-- 
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/-/p3FnJGZAMD4J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Compute modulus division by a power-of-2-number

[Dave]

@Rahul: If d is a power of 2, say 2^k, where ^ represents exponentiation, 
then the binary representation of d is a 1-bit followed by k 0-bits. Then 
d-1 is the binary number comprising k 1-bits. Anding this with n keeps only 
the low-order k bits of n, which you can see to be n%d.
 
Dave

On Wednesday, October 24, 2012 10:36:26 AM UTC-5, rahul sharma wrote:

 unsigned int getModulo(unsigned int n, unsigned int d)
  {
return ( n  (d-1) );
  } 
  
  n:6
  d:4
  ans is 2
  
  d must be power of 2
  
  anyone plz expalin logic behind this..i am not able to get this
  
  

-- 
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/-/KjTiT0WGFqMJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] C prog o/p

[Dave]

@Bharat: 0x notation indicates hexadecimal, so 0x11 = 1*16 + 1 = 17.
 
Dave

On Sunday, October 14, 2012 12:48:24 AM UTC-5, bharat wrote:

 @Ashok : I didn't get this answer .. 
 i=0x3c -- what is this address .. variables has addresses but not the 
 values right? we are not storing 60 any where right?
 0x11 = 3 in decimal format not 11 base 10.

 typecasting to (int*) needs an address right? 
 I mean 
 int b=10;
 int * a=(int*)b;



 On Sat, Oct 13, 2012 at 9:10 PM, Ashok Varma verm...@gmail.comjavascript:
  wrote:

 This gives a clear explanation: 

 #includestdio.h
 main(){
  int *i,*j;
  i=(int*)60;
  j=(int*)71;


  printf 
 http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(%p %p 
 %d,i,j,j-i);}


 op: 0x3c 0x47 2

 0x47 - 0x3c = 0x11 and hence j-1 = 2 (11/4 = 2, size of int = 4 bytes)


  On Sat, Oct 13, 2012 at 3:36 PM, bharat b 
 bagana.bh...@gmail.comjavascript:
  wrote:

  #includestdio.h
 main()
 {
  int *i,*j;
  i=(int*)60;
  j=(int*)71;
  printf(%d,j-i);
 }

 -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/b1AQOc8Y9wQJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: can we check a number has last digit 5 or not using bitwise operator.

[Dave]

@Piyush: I think not. Try n = 17 = 4*4 + 1 or n = 19 = 4*4 + 3. But you can 
say that n = 4 * a + b, with 0 = b = 3, is a multiple of 5 if and only if 
a - b is a multiple of 5, thus reducing to a simpler problem. That's the 
basis of the solution I posted earlier in this string.
 
Dave

On Saturday, October 13, 2012 3:58:16 PM UTC-5, Piyush Grover... wrote:

 The number which has 5 as last digit can be written as 
 n = 4*a + b where b = 1 or 3
 so if 4*a + 1 == n or 4*a + 3 == n; then n has 5 as a last digit.
 So code looks like:

 void main()
 {
  int n, m;
  scanf(%d, n);
  m = 2;
 m = 2;
 if(add(m, 1) == n || add(m,3) == n)
 puts(yes);
 else
 puts(no);
 }

 int add(int x, int y) {

 int a, b;

 do {

 a = x  y; b = x ^ y; x = a  1; y = b;

 }while(b);

 return b;

 }


 On Fri, Oct 12, 2012 at 12:46 AM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Jaspreet: The % operator is implemented using division, which is 
 considered an arithmetic operation, not a bitwise operation. 
  
 On primitive chips, as may be used in specialized hardware, division may 
 not be implemented, in which case a non-division based algorithm may be 
 desired.
  
 The question may be based on that idea, or just on how to do it faster 
 than using division, which typically is a very slow instruction (compared 
 to other machine instructions).
  
 Dave
  
 On Thursday, October 11, 2012 4:14:17 AM UTC-5, Jaspreet Singh wrote:

 Nice solution Dave sir .. but if you know can you please tell us what is 
 the internal structure of % operator .. i mean it has also to be done by 
 bitwise any way .. so can't we implement that in HHLs. 

 Thanks 

  On Thu, Oct 11, 2012 at 1:25 AM, Dave dave_an...@juno.com wrote:

  @Mohit: The decimal representation of a number ends in 5 if its low 
 order bit is 1 and it is divisibile by 5. 
  
 An algorithm using bitwise operations to check for divisibility by 5 is 
 given at https://groups.google.com/d/**msg/algogeeks/I5HWmwKW_ks/**
 n38FWJSd0l8Jhttps://groups.google.com/d/msg/algogeeks/I5HWmwKW_ks/n38FWJSd0l8J.
   

  
 It probably is not as fast as (n  1)  (n % 5 == 0), though.
  
 Dave
  
 On Wednesday, October 10, 2012 4:06:28 AM UTC-5, mohit mishra wrote:


 -- 
 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/-/bRupe9F1MUIJhttps://groups.google.com/d/msg/algogeeks/-/bRupe9F1MUIJ.
  

  
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com. 

 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.


  -- 
 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/-/XF05MQd7Ne4J. 

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/t0oNgSMyy3AJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: can we check a number has last digit 5 or not using bitwise operator.

[Dave]

@Jaspreet: The % operator is implemented using division, which is 
considered an arithmetic operation, not a bitwise operation. 
 
On primitive chips, as may be used in specialized hardware, division may 
not be implemented, in which case a non-division based algorithm may be 
desired.
 
The question may be based on that idea, or just on how to do it faster than 
using division, which typically is a very slow instruction (compared to 
other machine instructions).
 
Dave

On Thursday, October 11, 2012 4:14:17 AM UTC-5, Jaspreet Singh wrote:

 Nice solution Dave sir .. but if you know can you please tell us what is 
 the internal structure of % operator .. i mean it has also to be done by 
 bitwise any way .. so can't we implement that in HHLs. 

 Thanks 

 On Thu, Oct 11, 2012 at 1:25 AM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Mohit: The decimal representation of a number ends in 5 if its low order 
 bit is 1 and it is divisibile by 5. 
  
 An algorithm using bitwise operations to check for divisibility by 5 is 
 given at 
 https://groups.google.com/d/msg/algogeeks/I5HWmwKW_ks/n38FWJSd0l8J.  
  
 It probably is not as fast as (n  1)  (n % 5 == 0), though.
  
 Dave
  
 On Wednesday, October 10, 2012 4:06:28 AM UTC-5, mohit mishra wrote:


 -- 
 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/-/bRupe9F1MUIJ. 

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/XF05MQd7Ne4J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: can we check a number has last digit 5 or not using bitwise operator.

[Dave]

@Mohit: The decimal representation of a number ends in 5 if its low order 
bit is 1 and it is divisibile by 5. 
 
An algorithm using bitwise operations to check for divisibility by 5 is 
given at https://groups.google.com/d/msg/algogeeks/I5HWmwKW_ks/n38FWJSd0l8J.  

 
It probably is not as fast as (n  1)  (n % 5 == 0), though.
 
Dave

On Wednesday, October 10, 2012 4:06:28 AM UTC-5, mohit mishra wrote:




-- 
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/-/bRupe9F1MUIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] finding element in array with minimum of comparing

[Dave]

@Phoenix: If elem does not exist in the array and we did not put it in the 
array, then the loop would exceed the array. But by setting arr[0] to elem, 
we ensure that the loop does stop.
 
Dave

On Monday, October 8, 2012 6:52:27 AM UTC-5, phoenix wrote:

 @Dave: Nice solution. Can you clarify why you need to store the first 
 element in a temp variable and put 'elem' in the first position? If elem 
 was already first in array then it makes no difference. If elem was not 
 first but somewhere in between, the loop will break there when coming from 
 behind and size will have the index right? Why do we need to store elem in 
 first position according to your code?

 On Sun, Oct 7, 2012 at 3:01 PM, Mangal Dev Gupta 
 dev@gmail.comjavascript:
  wrote:

 *@Dave  while( arr[--size] != elem );* 

 *Exception will come when it will encounter a[-1]*
 *i dont know if this loop will ever end... very poor solution i will say 
 * 

 On Sat, Oct 6, 2012 at 10:00 PM, Umer Farooq the@gmail.comjavascript:
  wrote:

 Well actually, I've just gone through Dave's code thoroughly and I 
 believe that his code is most appropriate. 

 Thanks viper11 for providing the explanation.

 As for my code, I'd like to replace 

 while (i!=j)

 with

 while (i  j)

 because != won't work for middle element if the number of elements are 
 odd ... and it also won't work if the number of elements are even.

 Anyway, thanks Dave for providing us with such a great solution. Please 
 keep posting! :-)

 And others, thanks for pointing out the issue in my code.
  
 On Sat, Oct 6, 2012 at 9:03 PM, Kalidhakani J 
 kanik...@gmail.comjavascript:
  wrote:

 @umer - what if the element to be searched is at the middle of the 
 array? your code doesn't handles this. check out. 


 On Sat, Oct 6, 2012 at 3:38 AM, icy` vip...@gmail.com javascript:wrote:

 nice solution, Dave! 

 @Umer -- if the sought ele is first, then Dave's code has it sitting 
 in the variable temp for a little while.   Loop will stop when size is 0, 
 since arr[0]==elem.  Now he throws temp back into arr[0], which will 
 return 
 index 0 from the last compare line.

 On Wednesday, October 3, 2012 2:08:56 AM UTC-4, Umer Farooq wrote: 

 @Dave Thanks for pointing that out.

 But I still can't get what if elem is on first element or it is not 
 present in the array? How is your code going to handle that situation?

 @Atul, Well yes, In the given question, the number of iterations were 
 2n. Which I have reduced to n+n/2. 





 On Tue, Oct 2, 2012 at 11:13 PM, atul anand atul.8...@gmail.comwrote:

 @umer : how no. of comparison are reduced to half by moving both
 sidesyou have 2 if condition inside, so you are making 2
 comparisons at each iteration + n/2 comparison for while loop so
 number of comparisons are n+n/2

 On 10/2/12, Umer Farooq the@gmail.com wrote:
  why don't we try it from both ends ... something like this:
 
  int i = 0; j = size-1;
 
  while (i != j)
  {
  if (arr[i] == elem)
return arr[i];
  if (arr[j] == elem)
 return arr[j];
  }
 
  this way, we have eliminated half of the comparisons in for loop? 
 What do
  you guys say?
 
  On Tue, Oct 2, 2012 at 12:18 PM, rafi rafiw...@gmail.com wrote:
 
  Vikas is right!
  while (n) is equal to (while n!=0)
  you have 2n compares!
 
  בתאריך יום שני, 1 באוקטובר 2012 12:12:21 UTC+2, מאת vikas:
 
  still there is no improvement, compiler will generate the code to
  compare
  with zero here. what you have accomplished is , hide it from 
 human eyes
 
  On Monday, 1 October 2012 15:25:09 UTC+5:30, Navin Kumar wrote:
 
  @atul:
  still it won't compare 0 th element. Slight modification in 
 your code:
 
  n=*sizeof(arr)*;
  do
  {
   if(elem==arr[*--n*])
print found;
 
  }while(n);
 
  On Mon, Oct 1, 2012 at 9:50 AM, atul anand atul.8...@gmail.com 
 wrote:
 
  yes, but there no need of checking outside the loop
 
  n=sizeof(arr)-1;
  do
  {
   if(elem==arr[n])
   print found;
  n--;
 
  }while(n);
 
 
 
  On Mon, Oct 1, 2012 at 9:33 AM, Navin Kumar
  algorit...@gmail.comwrote:
 
  @atul: keep one more checking outside loop for element at 0 
 th index.
  Because when n = 0  the your loop come out from the loop 
 without
  comparing
  it.
 
 
  On Mon, Oct 1, 2012 at 8:55 AM, atul anand
  atul.8...@gmail.comwrote:
 
  n=sizeof(arr);
  n--;
 
  while(n)
  {
   if(elem=arr[n])
print found;
 
  n--;
 
  }
 
  On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר 
 rafiw...@gmail.com
  wrote:
 
  Hi
  i was in an interview and was given a simple function
  int arrExsits(int* arr,int size,int elem){
  for (int i=0;isize;++i)
  if(elem==arr[i])
 return i;
  return -1;
  }
  this function does 2n compares
  n- the if statment
  n-check that i is smaller then size
  i was suppose to give an optimal (less compares) solution 
 so i gave
 
  int arrExsits(int* arr,int size,int elem){
  if (arr[size-1]==elem)
  return size-1;
  arr[size-1]=elem

[algogeeks] Re: Missing Number Problem

[Dave]

@Sanjay: This has been discussed before. See 
https://groups.google.com/d/msg/algogeeks/C5oHrps8Q2o/P7tJrhj55ZcJ
for a description of the algorithm. 
 
Dave

On Friday, October 5, 2012 12:19:40 AM UTC-5, Sanjay Rajpal wrote:

 We are given 300 million 9-digit numbers and 2 MB of RAM. We have to find 
 the missing number. How do we approach this problem ? 

 *Regards,*
 *Sanjay Kumar*


 * *

  **
 *
 *



-- 
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/-/p-nPQWjDOfkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Missing Number Problem

[Dave]

@Icy: The problem, of course is that there are 900 million 9 digit numbers, 
so you solved a restricted problem. There is a solution for the given 
problem. See 
https://groups.google.com/d/msg/algogeeks/C5oHrps8Q2o/P7tJrhj55ZcJ.
 
Dave

On Friday, October 5, 2012 4:26:32 PM UTC-5, icy` wrote:

  By missing I assume that the numbers are consecutive and we are at 
 least provided with a range.

 Suppose for the sake of example, the range is 100,000 to 400,000 with 
 203,148 being the missing number.  They come to us shuffled up, and let us 
 suppose we are taking them from the hard drive instead of an array, one by 
 one.  Now if the range is known, there is an interesting property of XOR 
 that you can use.  A variable initialized to 0 can be XOR'd with every 
 element in the range, and then XOR'd with all the provided numbers.  It 
 will then become the missing number.   Ruby example (again, assume numbers 
 coming from hard drive or other source, one at a time, and not array in 
 memory):

 [image: Inline image 1]


-- 
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/-/arIGbFfpAggJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: finding element in array with minimum of comparing

[Dave]

@Rafi: Try this:
 
int arrExsits( int* arr, int size, int elem)
{
int temp = arr[0];
arr[0] = elem;
while( arr[--size] != elem );
arr[0] = temp;
return a[size] == elem ? size : -1;
}
n+1 comparisons, and it leaves the array unaltered.
 
Dave

On Sunday, September 30, 2012 4:27:27 AM UTC-5, rafi wrote:

 Hi
 i was in an interview and was given a simple function
 int arrExsits(int* arr,int size,int elem){
 for (int i=0;isize;++i)
 if(elem==arr[i])
return i;
 return -1;
 }
 this function does 2n compares 
 n- the if statment
 n-check that i is smaller then size
 i was suppose to give an optimal (less compares) solution so i gave

 int arrExsits(int* arr,int size,int elem){
 if (arr[size-1]==elem)
 return size-1;
 arr[size-1]=elem]
 for (int i=0;;++i)
 if(elem==arr[i]){
 if (i!=size-1)
 return i;
 return -1;
 }
 this solution works and it has n+2 compares the first one another n and 
 the second inner if.
 they told me it's good (and I've passed) but they told just for my 
 knowledge that there is a better N compare solution.
 I've searched the web but couldn't find it.
 anybody knows?
 Thanks 


-- 
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/-/xf30WpSdP_oJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] finding element in array with minimum of comparing

[Dave]

@Umer: I say that you forgot to increment i and decrement j in the loop. 
But you don't need any loop-counting comparisons at all. 
 
Dave

On Tuesday, October 2, 2012 3:36:58 AM UTC-5, Umer Farooq wrote:

 why don't we try it from both ends ... something like this:

 int i = 0; j = size-1;

 while (i != j)
 {
 if (arr[i] == elem)
   return arr[i];
 if (arr[j] == elem)
return arr[j];
 }

 this way, we have eliminated half of the comparisons in for loop? What do 
 you guys say?

 On Tue, Oct 2, 2012 at 12:18 PM, rafi rafiw...@gmail.com javascript:wrote:

 Vikas is right!
 while (n) is equal to (while n!=0)
 you have 2n compares!

 בתאריך יום שני, 1 באוקטובר 2012 12:12:21 UTC+2, מאת vikas:

 still there is no improvement, compiler will generate the code to 
 compare with zero here. what you have accomplished is , hide it from human 
 eyes

 On Monday, 1 October 2012 15:25:09 UTC+5:30, Navin Kumar wrote:

 @atul: 
 still it won't compare 0 th element. Slight modification in your code:

 n=*sizeof(arr)*;
 do
 {
  if(elem==arr[*--n*])
  print found;

 }while(n);

 On Mon, Oct 1, 2012 at 9:50 AM, atul anand atul.8...@gmail.com wrote:

 yes, but there no need of checking outside the loop

 n=sizeof(arr)-1;
 do
 {
  if(elem==arr[n])
  print found;
 n--;

 }while(n);



 On Mon, Oct 1, 2012 at 9:33 AM, Navin Kumar algorit...@gmail.comwrote:

 @atul: keep one more checking outside loop for element at 0 th index. 
 Because when n = 0  the your loop come out from the loop without 
 comparing 
 it.


 On Mon, Oct 1, 2012 at 8:55 AM, atul anand atul.8...@gmail.comwrote:

 n=sizeof(arr);
 n--;

 while(n)
 {
  if(elem=arr[n])
   print found;

 n--;

 }

 On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר rafiw...@gmail.comwrote:

 Hi
 i was in an interview and was given a simple function
 int arrExsits(int* arr,int size,int elem){
 for (int i=0;isize;++i)
 if(elem==arr[i])
return i;
 return -1;
 }
 this function does 2n compares 
 n- the if statment
 n-check that i is smaller then size
 i was suppose to give an optimal (less compares) solution so i gave

 int arrExsits(int* arr,int size,int elem){
 if (arr[size-1]==elem)
 return size-1;
 arr[size-1]=elem]
 for (int i=0;;++i)
 if(elem==arr[i]){
 if (i!=size-1)
 return i;
 return -1;
 }
 this solution works and it has n+2 compares the first one another n 
 and the second inner if.
 they told me it's good (and I've passed) but they told just for my 
 knowledge that there is a better N compare solution.
 I've searched the web but couldn't find it.
 anybody knows?
 Thanks 

 -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com**.
 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=enhttp://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 algo...@googlegroups.com.
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com**.
 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=enhttp://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 algo...@googlegroups.com.
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com**.
 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=enhttp://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 algo...@googlegroups.com.
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com**.
 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en
 .


  -- 
 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/-/SwuLNscTCOoJ.

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 For more options, visit this group at 
 http://groups.google.com/group/algogeeks?hl=en.




 -- 
 Umer
  

-- 
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/-/eakrSzF7tY0J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe

[algogeeks] Re: Given a two dimensional graph with points on it, find a line which passes the most number of points.

[Dave]

@Shashi: It has been discussed before, and an O(n^2 log n) solution is 
outlined at 
https://groups.google.com/d/msg/algogeeks/fBhXY9aUNJ0/CTB_p7uO8YYJ and is 
given in more detail at 
https://groups.google.com/d/msg/algogeeks/fBhXY9aUNJ0/0S0zK6HdKdMJ.
 
Dave

On Monday, October 1, 2012 12:00:19 PM UTC-5, Shashi Kant wrote:

 Given a two dimensional graph with points on it, find a line which passes 
 the most number of points. 
 Can somebody suggest possible ways to do it.

 *(or point me to the post if this problem is already discussed)*



 *Thanks  Regards,*
 *Shashi Kant *
 ***Think positive and find fuel in failure*
 http://thinkndoawesome.blogspot.com/
 *System/Software Engineer*
 *Hewlett-Packard India Software Operations.
 *




-- 
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/-/TW09gurbAN0J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Adobe Written Test - 25 SEPT 2010

[Dave]

@Navin: It means that given a positive integer n whose decimal 
representation ends in 3, find a multiple, m*n, which is written solely 
with the digit 1. E.g., 3: 37 * 3 = 111; 13: 8547 * 13 = 111,111.
 
Dave

On Thursday, September 20, 2012 11:56:08 PM UTC-5, Navin Kumar wrote:

 @all: Please explain question number 8. I am not getting the question 
 exactly what it says ?  

 On Fri, Sep 21, 2012 at 9:30 AM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Bharat: Simulate long division, dividing a number ...1 by the 
 number. You can do this one digit at a time, printing the quotient digit by 
 digit until you bring down a zero. It could look something like this:
  
 int n=the number that ends with 3;
 int divisor=1;
 while( divisor  n )
 divisor = 10 * divisor + 1;
 while( divisor != 0 )
 {
 printf(%d,divisor / n);
 divisor = 10 * (divisor % n) + 1;
 }
 printf(\n);
  
 Dave

 On Thursday, September 20, 2012 9:45:55 PM UTC-5, bharat wrote:

 what is the solution(not brute force) for 8th question ?

 On Fri, Sep 14, 2012 at 5:19 PM, Bhupendra Dubey bhupen...@gmail.comwrote:

 Which edition of barron?


 On Wed, Sep 28, 2011 at 6:05 PM, VIHARRI vihar...@gmail.com wrote:

 1. Java uses stack for byte code in JVM - each instruction is of one
 byte, so how many such instructions are possible in an operating
 system.

 2. Three processes p1, p2, p3, p4 - each have sizes 1GB, 1.2GB, 2GB,
 1GB. And each processes is executed as a time sharing fashion. Will
 they be executed on an operating system.

 3. write a recursive program for reversing the linked list.

 4. write a program for checking the given number is a palindrome.
 ( dont use string / array for converting number ).

 5. write a recursive program for multiplying two numbers a and b, with
 additions. The program should take care of doing min # additions as
 that of which ever number is lower between a and b.

 6. There are two sets A and B with n integers, write a program to
 check the whether there exists two numbers a in A and b in B such that
 a+b = val ( val is given );

 7. write a program to return the row number which has max no of one's
 in an array of NxN matrix where all 1's occur before any 0's starts.

 8. For every number that has 3 in its units place has one multiple
 which has all one's i.e. 111 is such multiple and 13 has a multiple
 11. Write a program to find such multiple for any number that has
 3 at its units place.

 9. what are the maximum no of edges that can be connected in a graph
 of n vertices and 0 edges such that after adding edges given graph is
 still disconnected.

 10. One Question on critical section.

 For Analytical Test - Prepare the Questions in the barrons book of
 sample paper - 2 ( they have give two passages )

 --
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com.

 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en
 .




 -- 
 Thanks  regards
 Bhupendra



  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com.

 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.


  -- 
 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/-/pDBPxDR3R1oJ.

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/LpHDrQKDb90J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Adobe Written Test - 25 SEPT 2010

[Dave]

@Navin: No problem. Just print a 1 instead of a quotient digit. That makes 
the code even simpler, like this:
 
int n=the number that ends with 3;
int divisor=1;
printf(1);
while( divisor != 0 )
{
printf(1);
divisor = 10 * (divisor % n) + 1;
}
printf(\n);
 
Dave

On Friday, September 21, 2012 2:05:55 AM UTC-5, Navin Kumar wrote:

 @Dave sir: Thanx for reply. your  solution gives the exact multiple like 
 37 for 3, 8547 for 13. In the question i think we have to print the number 
 which is 13x8547 which will be very large (out of integer range).In 
 that case we have to store result in string. 
  

 On Fri, Sep 21, 2012 at 12:09 PM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Navin: It means that given a positive integer n whose decimal 
 representation ends in 3, find a multiple, m*n, which is written solely 
 with the digit 1. E.g., 3: 37 * 3 = 111; 13: 8547 * 13 = 111,111.
  
 Dave

 On Thursday, September 20, 2012 11:56:08 PM UTC-5, Navin Kumar wrote:

 @all: Please explain question number 8. I am not getting the question 
 exactly what it says ?  

 On Fri, Sep 21, 2012 at 9:30 AM, Dave dave_an...@juno.com wrote:

 @Bharat: Simulate long division, dividing a number ...1 by the 
 number. You can do this one digit at a time, printing the quotient digit 
 by 
 digit until you bring down a zero. It could look something like this:
  
 int n=the number that ends with 3;
 int divisor=1;
 while( divisor  n )
 divisor = 10 * divisor + 1;
 while( divisor != 0 )
 {
 printf(%d,divisor / n);
 divisor = 10 * (divisor % n) + 1;
 }
 printf(\n);
  
 Dave

 On Thursday, September 20, 2012 9:45:55 PM UTC-5, bharat wrote:

 what is the solution(not brute force) for 8th question ?

 On Fri, Sep 14, 2012 at 5:19 PM, Bhupendra Dubey 
 bhupen...@gmail.comwrote:

 Which edition of barron?


 On Wed, Sep 28, 2011 at 6:05 PM, VIHARRI vihar...@gmail.com wrote:

 1. Java uses stack for byte code in JVM - each instruction is of one
 byte, so how many such instructions are possible in an operating
 system.

 2. Three processes p1, p2, p3, p4 - each have sizes 1GB, 1.2GB, 2GB,
 1GB. And each processes is executed as a time sharing fashion. Will
 they be executed on an operating system.

 3. write a recursive program for reversing the linked list.

 4. write a program for checking the given number is a palindrome.
 ( dont use string / array for converting number ).

 5. write a recursive program for multiplying two numbers a and b, 
 with
 additions. The program should take care of doing min # additions as
 that of which ever number is lower between a and b.

 6. There are two sets A and B with n integers, write a program to
 check the whether there exists two numbers a in A and b in B such 
 that
 a+b = val ( val is given );

 7. write a program to return the row number which has max no of one's
 in an array of NxN matrix where all 1's occur before any 0's starts.

 8. For every number that has 3 in its units place has one multiple
 which has all one's i.e. 111 is such multiple and 13 has a multiple
 11. Write a program to find such multiple for any number that has
 3 at its units place.

 9. what are the maximum no of edges that can be connected in a graph
 of n vertices and 0 edges such that after adding edges given graph is
 still disconnected.

 10. One Question on critical section.

 For Analytical Test - Prepare the Questions in the barrons book of
 sample paper - 2 ( they have give two passages )

 --
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com**.

 For more options, visit this group at http://groups.google.com/**
 group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en
 .




 -- 
 Thanks  regards
 Bhupendra



  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com**.

 For more options, visit this group at http://groups.google.com/**
 group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en
 .


  -- 
 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/-/pDBPxDR3R1oJhttps://groups.google.com/d/msg/algogeeks/-/pDBPxDR3R1oJ
 .

 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com.
 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.


  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To view this discussion

Re: [algogeeks] Adobe Written Test - 25 SEPT 2010

[Dave]

I thought about it some more, and realize that my code wasn't correct. Try 
this:
 
int n = the number that ends with 3; // e.g., int n = 13;
int d = 1;
while( d % n != 0 )
{
printf(1);
d = 10 * (d % n) + 1;
}
printf(1\n);

On Friday, September 21, 2012 11:07:29 AM UTC-5, Dave wrote:

 @Navin: No problem. Just print a 1 instead of a quotient digit

 

 . That makes the code even simpler, like this:
  
 int n=the number that ends with 3;
 int divisor=1;
 printf(1);
 while( divisor != 0 )
 {
 printf(1);
 divisor = 10 * (divisor % n) + 1;
 }
 printf(\n);
  
 Dave

 On Friday, September 21, 2012 2:05:55 AM UTC-5, Navin Kumar wrote:

 @Dave sir: Thanx for reply. your  solution gives the exact multiple like 
 37 for 3, 8547 for 13. In the question i think we have to print the number 
 which is 13x8547 which will be very large (out of integer range).In 
 that case we have to store result in string. 
  

 On Fri, Sep 21, 2012 at 12:09 PM, Dave dave_an...@juno.com wrote:

 @Navin: It means that given a positive integer n whose decimal 
 representation ends in 3, find a multiple, m*n, which is written solely 
 with the digit 1. E.g., 3: 37 * 3 = 111; 13: 8547 * 13 = 111,111.
  
 Dave

 On Thursday, September 20, 2012 11:56:08 PM UTC-5, Navin Kumar wrote:

 @all: Please explain question number 8. I am not getting the question 
 exactly what it says ?  

 On Fri, Sep 21, 2012 at 9:30 AM, Dave dave_an...@juno.com wrote:

 @Bharat: Simulate long division, dividing a number ...1 by the 
 number. You can do this one digit at a time, printing the quotient digit 
 by 
 digit until you bring down a zero. It could look something like this:
  
 int n=the number that ends with 3;
 int divisor=1;
 while( divisor  n )
 divisor = 10 * divisor + 1;
 while( divisor != 0 )
 {
 printf(%d,divisor / n);
 divisor = 10 * (divisor % n) + 1;
 }
 printf(\n);
  
 Dave

 On Thursday, September 20, 2012 9:45:55 PM UTC-5, bharat wrote:

 what is the solution(not brute force) for 8th question ?

 On Fri, Sep 14, 2012 at 5:19 PM, Bhupendra Dubey bhupen...@gmail.com
  wrote:

 Which edition of barron?


 On Wed, Sep 28, 2011 at 6:05 PM, VIHARRI vihar...@gmail.com wrote:

 1. Java uses stack for byte code in JVM - each instruction is of one
 byte, so how many such instructions are possible in an operating
 system.

 2. Three processes p1, p2, p3, p4 - each have sizes 1GB, 1.2GB, 2GB,
 1GB. And each processes is executed as a time sharing fashion. Will
 they be executed on an operating system.

 3. write a recursive program for reversing the linked list.

 4. write a program for checking the given number is a palindrome.
 ( dont use string / array for converting number ).

 5. write a recursive program for multiplying two numbers a and b, 
 with
 additions. The program should take care of doing min # additions as
 that of which ever number is lower between a and b.

 6. There are two sets A and B with n integers, write a program to
 check the whether there exists two numbers a in A and b in B such 
 that
 a+b = val ( val is given );

 7. write a program to return the row number which has max no of 
 one's
 in an array of NxN matrix where all 1's occur before any 0's starts.

 8. For every number that has 3 in its units place has one multiple
 which has all one's i.e. 111 is such multiple and 13 has a multiple
 11. Write a program to find such multiple for any number that 
 has
 3 at its units place.

 9. what are the maximum no of edges that can be connected in a graph
 of n vertices and 0 edges such that after adding edges given graph 
 is
 still disconnected.

 10. One Question on critical section.

 For Analytical Test - Prepare the Questions in the barrons book of
 sample paper - 2 ( they have give two passages )

 --
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com**.

 For more options, visit this group at http://groups.google.com/**
 group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en
 .




 -- 
 Thanks  regards
 Bhupendra



  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com**.

 For more options, visit this group at http://groups.google.com/**
 group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en
 .


  -- 
 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/-/pDBPxDR3R1oJhttps://groups.google.com/d/msg/algogeeks/-/pDBPxDR3R1oJ
 .

 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email

Re: [algogeeks] Adobe Written Test - 25 SEPT 2010

[Dave]

@Rahul: What does this print for n = 193?
 
Dave

On Friday, September 21, 2012 12:14:18 AM UTC-5, Rahul Kumar Patle wrote:

 here is my code:

 main()
 {
 int n=13;
 int divisor=1;
 int temp;
 while( divisor  n )
 divisor = 10 * divisor + 1;
 printf(%d\n , divisor);
 temp = divisor;
 while(n)
 {
 if(temp%n == 0)
 break;
 temp = 10 * (temp % n) + 1;
 divisor = 10 * divisor + 1;
 while( temp  n )
 {
 divisor = 10 * divisor + 1;
 temp = 10 * temp + 1;
 }
 printf(%d and %d\n , divisor, temp);
 }
 printf(%d\n, divisor);
 }



 On Fri, Sep 21, 2012 at 10:30 AM, Rahul Kumar Patle 
 patlera...@gmail.comjavascript:
  wrote:

 @navin: you have to find a number containing all 1's which is divisible 
 by a given number xx...3, here given number contains 3 at it unit place...

 On Fri, Sep 21, 2012 at 10:25 AM, Navin Kumar 
 algorit...@gmail.comjavascript:
  wrote:

 @all: Please explain question number 8. I am not getting the question 
 exactly what it says ?  

 On Fri, Sep 21, 2012 at 9:30 AM, Dave dave_an...@juno.com javascript:
  wrote:

 @Bharat: Simulate long division, dividing a number ...1 by the 
 number. You can do this one digit at a time, printing the quotient digit 
 by 
 digit until you bring down a zero. It could look something like this:
  
 int n=the number that ends with 3;
 int divisor=1;
 while( divisor  n )
 divisor = 10 * divisor + 1;
 while( divisor != 0 )
 {
 printf(%d,divisor / n);
 divisor = 10 * (divisor % n) + 1;
 }
 printf(\n);
  
 Dave

 On Thursday, September 20, 2012 9:45:55 PM UTC-5, bharat wrote:

 what is the solution(not brute force) for 8th question ?

 On Fri, Sep 14, 2012 at 5:19 PM, Bhupendra Dubey 
 bhupen...@gmail.comwrote:

 Which edition of barron?


 On Wed, Sep 28, 2011 at 6:05 PM, VIHARRI vihar...@gmail.com wrote:

 1. Java uses stack for byte code in JVM - each instruction is of one
 byte, so how many such instructions are possible in an operating
 system.

 2. Three processes p1, p2, p3, p4 - each have sizes 1GB, 1.2GB, 2GB,
 1GB. And each processes is executed as a time sharing fashion. Will
 they be executed on an operating system.

 3. write a recursive program for reversing the linked list.

 4. write a program for checking the given number is a palindrome.
 ( dont use string / array for converting number ).

 5. write a recursive program for multiplying two numbers a and b, 
 with
 additions. The program should take care of doing min # additions as
 that of which ever number is lower between a and b.

 6. There are two sets A and B with n integers, write a program to
 check the whether there exists two numbers a in A and b in B such 
 that
 a+b = val ( val is given );

 7. write a program to return the row number which has max no of one's
 in an array of NxN matrix where all 1's occur before any 0's starts.

 8. For every number that has 3 in its units place has one multiple
 which has all one's i.e. 111 is such multiple and 13 has a multiple
 11. Write a program to find such multiple for any number that has
 3 at its units place.

 9. what are the maximum no of edges that can be connected in a graph
 of n vertices and 0 edges such that after adding edges given graph is
 still disconnected.

 10. One Question on critical section.

 For Analytical Test - Prepare the Questions in the barrons book of
 sample paper - 2 ( they have give two passages )

 --
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com.

 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en
 .




 -- 
 Thanks  regards
 Bhupendra



  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com.

 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en
 .


  -- 
 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/-/pDBPxDR3R1oJ.

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript

Re: [algogeeks] Adobe Written Test - 25 SEPT 2010

[Dave]

@Bharat: Simulate long division, dividing a number ...1 by the number. 
You can do this one digit at a time, printing the quotient digit by digit 
until you bring down a zero. It could look something like this:
 
int n=the number that ends with 3;
int divisor=1;
while( divisor  n )
divisor = 10 * divisor + 1;
while( divisor != 0 )
{
printf(%d,divisor / n);
divisor = 10 * (divisor % n) + 1;
}
printf(\n);
 
Dave

On Thursday, September 20, 2012 9:45:55 PM UTC-5, bharat wrote:

 what is the solution(not brute force) for 8th question ?

 On Fri, Sep 14, 2012 at 5:19 PM, Bhupendra Dubey 
 bhupen...@gmail.comjavascript:
  wrote:

 Which edition of barron?


 On Wed, Sep 28, 2011 at 6:05 PM, VIHARRI vihar...@gmail.comjavascript:
  wrote:

 1. Java uses stack for byte code in JVM - each instruction is of one
 byte, so how many such instructions are possible in an operating
 system.

 2. Three processes p1, p2, p3, p4 - each have sizes 1GB, 1.2GB, 2GB,
 1GB. And each processes is executed as a time sharing fashion. Will
 they be executed on an operating system.

 3. write a recursive program for reversing the linked list.

 4. write a program for checking the given number is a palindrome.
 ( dont use string / array for converting number ).

 5. write a recursive program for multiplying two numbers a and b, with
 additions. The program should take care of doing min # additions as
 that of which ever number is lower between a and b.

 6. There are two sets A and B with n integers, write a program to
 check the whether there exists two numbers a in A and b in B such that
 a+b = val ( val is given );

 7. write a program to return the row number which has max no of one's
 in an array of NxN matrix where all 1's occur before any 0's starts.

 8. For every number that has 3 in its units place has one multiple
 which has all one's i.e. 111 is such multiple and 13 has a multiple
 11. Write a program to find such multiple for any number that has
 3 at its units place.

 9. what are the maximum no of edges that can be connected in a graph
 of n vertices and 0 edges such that after adding edges given graph is
 still disconnected.

 10. One Question on critical section.

 For Analytical Test - Prepare the Questions in the barrons book of
 sample paper - 2 ( they have give two passages )

 --
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 For more options, visit this group at 
 http://groups.google.com/group/algogeeks?hl=en.




 -- 
 Thanks  regards
 Bhupendra



  -- 
 You received this message because you are subscribed to the Google Groups 
 Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/pDBPxDR3R1oJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] BitWise Operations - For finding next multiple

[Dave]

Actually, it doesn't do what the requester asked even when x is a power of 
2, because, e.g., the output for n = 6 and x = 2 is 6, but according to the 
examples provided, the output should be 8, the next higher multiple of 2. 
You could use (n + x)  ~(x-1) or (n + x)  (-x) for the x = power of two 
case.
For general x  0, the following algorithm is O(log n):
int nextLargerMultiple(int n, int x)
{
 int r = n, d = x;
 while( r = d ) d = 1;
 while( d != x )
 {
 d = 1;
 if( r = d ) r -= d;
 }
 return n - r + x;
}
Think long division, as you learned to do it with paper and pencil. The 
first while loop shifts x left enough that the result is  n. The second 
while loop  successively shifts x right one place and if 
possible subtracts it from n. At the end of the second while loop r is the 
remainder; n%x. Subtracting r from n gives the n rounded down to a multiple 
of x, and then adding x gives the next larger multiple of x.
 
Dave

On Thursday, September 13, 2012 9:03:49 AM UTC-5, bharat wrote:

 the above code works only for 2,4,8,16 ...

 On Thu, Sep 13, 2012 at 7:13 PM, VIHARRI P L V 
 vihar...@gmail.comjavascript:
  wrote:

 Let me give an example. 
 
   For 17 next multiple of number 5 is 20.
   For 20 next multiple of number 5 is 25.

 And give solution for this proeblem also:
  
   For 17 next nearest multiple of number 5 is 20.
   For 20 next nearest multiple of number 5 is 20.

 *VIHARRI P L V*




 On Thu, Sep 13, 2012 at 7:09 PM, bharat b 
 bagana.bh...@gmail.comjavascript:
  wrote:

 @vihari: what is n?

 On Thu, Sep 13, 2012 at 6:32 PM, VIHARRI vihar...@gmail.comjavascript:
  wrote:

 hey for finding next multiple of a number x using bitwise : ( n + x -1 
 )  ~(x-1) but not working for all numbers 
 Could some one please explain me. 

 -- 
 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/-/7C_Nw4RoxmEJ.
 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/e0LIWXHAQjMJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Median in a stream of integers (running integers)

[Dave]

@Rahul: You'll find a discussion of the heap method in the thread at 
https://groups.google.com/d/topic/algogeeks/483lcb0FTY0/discussion. 
 
Dave

On Saturday, September 8, 2012 11:53:44 AM UTC-5, rahul sharma wrote:

 http://www.geeksforgeeks.org/archives/14873 

 Please explain heap method..hw it works..with given i/pthnx


-- 
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/-/KBlvjPo2XMIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: give the algo or program to find second largest element in a list using tournament method

[Dave]

@Don: Nope. Constructing a heap can be done in O(n). See, e.g., 
http://www.diku.dk/forskning/performance-engineering/Jesper/heaplab/heapsurvey_html/node9.html
.
 
Dave

On Tuesday, September 4, 2012 10:24:25 AM UTC-5, Don wrote:

 Constructing a max-heap is O(n*log n) 

 However, the problem asked for a solution using tournament method. 
 If you ignore that requirement, an O(n) solution is trivial, and 
 doesn't require the additional storage of a heap: 

 int first = max(A[0], A[1]); 
 int second = min(A[0], A[1]); 
 for(i = 2; i  N; ++i) 
 { 
 if (A[i] = first) 
 { 
 second = first; 
 first = A[i]; 
 } 
 else if (A[i]  second) 
 second = A[i]; 
 } 

 // First and second now contain 1st and 2nd largest values in A 

 Don 

 On Sep 3, 5:04 am, bharat b bagana.bharatku...@gmail.com wrote: 
  Construct a max-heap -- O(n).. 
  call delete() 2 times .. -- O(logn).. 
  === O(n) time.. 
  
  


-- 
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/-/bKzs-wHLSoIJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Can somebody suggest me AO* algo that convert a number n into strigs of 1's

[Dave]

@Daemon: Probably no one understands what you've asked. What does it mean 
to convert a number n into strigs of 1's? Doesn't that depend on what a 
strig is and what operations are allowed? E.g., if one of the operations is 
replacing a digit by the strig 1, the algorithm is pretty simple.
 
Dave

On Monday, September 3, 2012 12:20:28 PM UTC-5, Daemon Dev wrote:

 seems no body interested in this..  v bad..

 On Sunday, September 2, 2012 11:05:24 PM UTC+5:30, Daemon Dev wrote:

 Can somebody suggest me AO* algorithm that convert a number n into strigs 
 of 1's

 n- (n-1)+1; n-ceil(n/2)+floor(n/2)
 h(n)=n and h(1)=0

 Please help.. 



-- 
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/-/v0gZ1oeAFcQJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is equal to given number in O(n) time and O(1) space.

[Dave]

@Atul007: No need to destroy the BST. Perform two simultaneous inorder 
traversals of the BST, one from left to right (the usual direction) and one 
from right to left. At any stage you have selected two nodes. If the sum is 
less than the given number, advance the left-to-right traversal; If the sum 
is greater, advance the right-to-left traversal. Quit with success when the 
sum equals the given number or with failure when the two traversals have 
reached the same node.
Dave

On Sunday, September 2, 2012 11:00:42 PM UTC-5, atul007 wrote:

 convert BST to sorted DLL..
 now it is a double linked list , so we can find 2 number in O(n)  time by 
 keeping 2 pointers(one at start and one at end) from sorted DLL.
 now convert DLL to BST.

 On Mon, Sep 3, 2012 at 1:32 AM, Navin Kumar algorit...@gmail.comjavascript:
  wrote:
 MICROSOFT:Given a BST and a number. Find two node in a BST whose sum is 
 equal to given number in O(n) time and O(1) space.



-- 
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/-/oizd-5CSfuoJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: 5 tyres 10000 Kilometers..

[Dave]

@Prem: You will travel 40,000 tire (American spelling) km. Therefore, each 
tire needs to be on the ground for 8,000 km. One way to accomplish this is 
to rotate the 5 tires each 2,000 km. Then, each tire will be on each wheel 
for 2,000 km, and will be the spare for 2,000 km. Another way, with less 
tire switching, is to switch the tire on a different wheel with the current 
spare each 2,000 km. This involves moving only 2 tires each 2,000 km. The 
diagram of tire positions is
 
  02000  4000  6000  8000
A B   S B S A S AS A
C D   C DC D B DB C
 SABCD
 
Dave

On Tuesday, August 28, 2012 11:09:47 AM UTC-5, Prem wrote:

 Guys Something good to share here..

 Query :-  Tomorrow I am Planning to take my car for a ride of 1 ( Ten 
 Thousands )  Km. As the journey will be rough so I am planning to pack 5 
 new tyres..  Now being very conservative, I want to use each of them such 
 that they all wear equally.. Now the question is how shall I achieve it and 
 what will be the total journey traveled by each on of them.



-- 
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/-/xtgmVV4zXA8J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Printing random word from file

[Dave]

@Kailash: I assumed a function random() which generates uniformly 
distributed double precision random numbers between 0 and 1. Usually such a 
generator would produce numbers with 53 bit precision, so I guess that is 
between 15 and 16 digits after the decimal point. Just google random 
number generator for a variety of methods to do this.
 
Dave

On Sunday, August 26, 2012 9:03:21 AM UTC-5, kailash wrote:

 @Dave: Can you throw some light on random() function?? How it is 
 generating numbers between 0.0 and 1.0, and how many digits are there after 
 the point...because if there is only one digit then we will not be able 
 to print words after 10th place because 10*0.1(lowest number generated by 
 random())=1...since lowest number generated by the random() function is not 
 able to convert 10th word into printable situation,so we can't print words 
 above 10th place (inclusive)  so it's not solving the original 
 problem???

 On Sun, Aug 26, 2012 at 3:55 AM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Kunal: Yes. You are missing that you don't know the number of words in 
 the file in advance. So, to use your method, you would have to read the 
 file once to find n, and then read through it again to select the lucky_pos 
 th word. The method I proposed only requires reading the file once. 
  
 Furthermore, assuming that rand() produces a random non-negative integer, 
 rand()%n is not equiprobable for all values of n. Consider n = 3. Then 
 since rand() takes on 2^31 values, rand()%3 cannot take on the values 0, 1, 
 and 2 with equal probability since 2^31 is not divisible by 3.
  
 Dave

 On Saturday, August 25, 2012 1:44:03 PM UTC-5, Kunal Patil wrote:

 How about using rand()%n ??
 Like, calculate lucky_pos = rand()%n
 Then print word at lucky_pos th position...
 Am I missing anything? All words are still equiprobable to get printed 
 right?
 On Aug 20, 2012 11:45 AM, Dave dave_an...@juno.com wrote:

 @Navin: Okay. Here is a paraphrase. Assume double function random() 
 returns a uniformly distributed random number = 0.0 and  1.0.
  
 read first word from file into string save;
 int i = 1
 while not EOF
 {
 read next word from file into string temp;
 i++;
 if( i * random()  1.0 )
 copy temp to save;
 }
 print save;
  
 Dave

 On Monday, August 20, 2012 12:02:54 AM UTC-5, Navin Kumar wrote:

 @Dave sir, I didn't get your logic. Can you please elaborate it? 

 On Sun, Aug 19, 2012 at 4:08 AM, Dave dave_an...@juno.com wrote:

 @Navin: Here is the algorithm:
  
 Save the first word. 
 For i = 2, 3, ..., n = number of words in the file
 replace the saved word with the i-th word with probability 1/i.
 When EOF is reached, every word in the file will have probability 1/n 
 of being the saved word. Print it.
  
 Dave
  
 On Saturday, August 18, 2012 1:28:56 AM UTC-5, Navin Kumar wrote:

 Print a *Random word* from a file. Input is path to a file, 

 constraints- No extra memory like hashing etc. All the words in the 
 file should have equal probability.

  -- 
 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/
 **ms**g/algogeeks/-/HxO-wNzEP9gJhttps://groups.google.com/d/msg/algogeeks/-/HxO-wNzEP9gJ
 .

 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com**.
 For more options, visit this group at http://groups.google.com/**
 group**/algogeeks?hl=enhttp://groups.google.com/group/algogeeks?hl=en
 .


  -- 
 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/-/crET-x06vpkJhttps://groups.google.com/d/msg/algogeeks/-/crET-x06vpkJ
 .
 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com.
 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.

  -- 
 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/-/pvqb27sRhFAJ.

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 For more options, visit this group at 
 http://groups.google.com/group/algogeeks?hl=en.




 -- 

 --

 ‘Kailash Bagaria’
 B-tech 4th year
 Computer Science  Engineering
 Indian Institute of Technology, Roorkee
 Roorkee, India (247667)



-- 
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/-/AiUxsEuB3DAJ.
To post

Re: [algogeeks] Re: Printing random word from file

[Dave]

@Pankaj: My only complaint is that rand()%n is not uniformly distributed 
between 0 and n-1. To see this, suppose rand() produces positive 32-bit 
integers, so they have the range 0 to 2^31 - 1 = 2,147,483,647. Now, 
suppose there are 100,000 words in the file. When you are computing 
rand()%10, you will get each of the numbers 0 to 83,646 on average 
21,475 times out of 2^31 random numbers, but you will get the numbers 
83,647 to 99,999 only 21,474 times out of every 2^31 random numbers. Thus, 
the first numbers in the file will appear with slightly too high a 
probability and the numbers at the end of the file will be selected with 
slightly too low a probability.
 
That's why I prescribed a double precision random number generator that 
generates uniformly-distributed numbers between 0 and 1, and wrote the 
test  i * random()  1.
 
Dave

On Tuesday, August 28, 2012 7:59:13 AM UTC-5, Pankaj wrote:

 @all-This is almost the same question asked in facebook.. 
 Dave sir is correct!
 Example-file contain only a b a c;
 Then step1:
 save a;
 step2:
 save b with probability of value 0 by rand()%2;
 therefore pr[1]=1/2;pr[2]=1/2;
 step3;
 save a with probability of value 0 by rand()%3;
 therefore pr[1]=1/2*2/3=1/3;
 pr[2]=1/2*2/3=1/3;
 pr[3]=1/3;
 step4;
 all same similraly =1/4..and dis continues..


-- 
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/-/gWo4UhJ1uhsJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Search an element in a sorted and pivoted array

[Dave]

@Rahul: Please tell us what you mean by a pivoted array.
 
Dave

On Tuesday, August 28, 2012 12:56:03 PM UTC-5, rahul sharma wrote:

 plz provide me algo for this,thnx 

-- 
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/-/iomheqkDEd0J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Question on checking divisibility of binomial coefficients of a number by a prime number

[Dave]

@Ankit: I haven't written code for this problem, but here is how I would do 
it. You are given values of n and P, with n being up to a 500-digit number 
(e.g., stored in an array, with say 9 digits of the number stored in each 
of up to 112 (500/9 rounded up) integers and P fitting in one integer. 
 
Write n in base P. You do this using long division to divide n by P. Just 
simulate what you do when you use long division by hand. The remainder is 
the low-order base-P digit of n. Repeat the process on the quotient to get 
successive base-P digits of n, until the quotient is zero. What you now 
have computed is the m_i of the Wikipedia article. 
 
Note the Consequence in the article, that the binomial coefficient is 
divisible by the prime if any n_i is greater than the corresponding m_i. 
Note that the binomial coefficient is divisible by the prime if and only if 
the binomial coefficient is zero modulo the prime. So how many possible k 
= n are there for which any of the n_i (the base-P digits of k) exceed the 
corresponding m_i? It is easier to calculate the number of k with all n_i 
= m_i: this is just one less than the product all of the (m_i + 1). So 
calculate this number in base-P arithmetic. Then subtract it from the 
base-P representation of n to get the base-P representation of the answer. 
 
Note that we never calculated any binomial coefficients to determine the 
answer!
 
Now convert the base-P representation of the answer back to base 10 to the 
9th power and print it out. You will have to use long long int (64 bits) 
for some of the calculations, although the base-P digits of n and P will 
fit in ordinary 32-bit ints.
 
Dave
 
On Sunday, August 26, 2012 6:56:19 PM UTC-5, Ankit Singh wrote:

 @dave: 
 Can u Please elaborate your idea??
 I didn't understand lucas theorem and in that theorem, i see too much 
 calculation and here we have to deal with testcases upto 100 and each 
 testcase containing n in range of 10500. 


  
 On Mon, Aug 27, 2012 at 4:02 AM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Ankit: Apply Lucas' Theorem, which you can find written up in Wikipedia.
  
 Dave

 On Sunday, August 26, 2012 3:57:18 PM UTC-5, Ankit Singh wrote:

 In mathematics, *binomial coefficients* are a family of positive 
 integers that occur as coefficients in the binomial theorem. [image: 
 \tbinom nk] denotes the number of ways of choosing k objects from n 
 different objects.

 However when n and k are too large, we often save them after modulo 
 operation by a prime number P. Please calculate how many binomial 
 coefficients of n become to 0 after modulo by P.

 *Input*

 The first of input is an integer T , the number of test cases.

 Each of the following T lines contains 2 integers, n and prime P.

 *Output*

 For each test case, output a line contains the number of [image: 
 \tbinom nk]s (0=k=n) each of which after modulo operation by P is 0.

 *Sample Input*

 3

 2 2

 3 2

 4 3

 *Sample Output*

 1

 0

 1

 *Constraints:*

 T is less than 100

 n is less than 10500.
  P is less than 109.
  
  
  
  
 I Have applied a logic that if any binomial coefficient can be written 
 as n!/(n-k)!k!  so if (n/p)((n-k)/p+k/p) so that coefficient will be 
 divisiblr by prime number p. but the problem is range of is so large so if 
 i give an input of that much range it will take more then 15 min . although 
 complexity of my code is O(n/2) but my program keep on running because of 
 very high range of input. Can anyone help me in this please??
  
 Thank you

  -- 
 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/-/aLFSGCkdtmsJ.

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/1fxRn6HSPaMJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] max sum b/w 2 leaf nodes in a binary tree

[Dave]

@Ravi: That is also my understanding, so the solution involves traversing 
the tree and keeping track of the values of the two largest leaf nodes.
 
Dave

On Monday, August 27, 2012 12:53:05 PM UTC-5, Ravi Maggon wrote:

 @atul
 I think he is asking for max. sum of elements between 2 leaf nodes and not 
 the max distance between two nodes.

 On Sun, Aug 26, 2012 at 6:12 PM, atul anand atul.8...@gmail.comjavascript:
  wrote:

 its the diameter of tree.
 you can find implementation on geeksforgeeks

 On 8/25/12, kunal rustgi rustog...@gmail.com javascript: wrote:
  Hi,
 
  Can anyone suggest the best approach for finding max sum b/w 2 leaf 
 nodes
  in a binary tree ( not BST )  ?
 
  --
  You received this message because you are subscribed to the Google 
 Groups
  Algorithm Geeks group.
  To post to this group, send email to algo...@googlegroups.comjavascript:
 .
  To unsubscribe from this group, send email to
  algogeeks+...@googlegroups.com javascript:.
  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 algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 For more options, visit this group at 
 http://groups.google.com/group/algogeeks?hl=en.




 -- 

 

 *Regards
 *Ravi Maggon

 Member Technical - IT/Front Office

 D.E. Shaw  Co.
  

-- 
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/-/3KkVfNZkjO4J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] amazon Interview

[Dave]

@Atul007: No, because a (1,4) tile will not fit on a (2,3) tile.
 
Dave

On Sunday, August 26, 2012 7:45:27 AM UTC-5, atul007 wrote:

 @kailash : you can simply find area of each slab area=x*y ,,,store it; 
 then just run LIS on this area. 

 On 8/26/12, Kailash Bagaria kbkailas...@gmail.com javascript: wrote: 
  Yeah Atul is right. 
  Here is my solution:-- 
  1) first rearrange the dimensions of slabs i.e. put bigger dimension in 
 y 
  and smaller dimenson in x (rotate the slab) 
  2) then arrange all slabs in increasing order of x dimension 
  3) and then find the longest increasing sub-sequence based on y 
  dimension.. 
  
  Ex:- (2,5),(5,1),(1,3),(1,2),(6,1) 
  
  Step-1= (2,5),(1,5),(1,3),(1,2),(1,6) 
  
  Step-2= (1,2),(1,3),(1,5),(1,6),(2,5) 
  
  Step-3= LIS=4  {  (1,2),(1,3),(1,5),(1,6)   OR   
 (1,2),(1,3),(1,5),(2,5) 
  } 
  
  Correct me if i wrong... 
  
  On Sun, Aug 26, 2012 at 3:54 PM, atul anand 
  atul.8...@gmail.comjavascript: 

  wrote: 
  
  its a LIS problem. 
  
  need to think for n-dimension... 
  
  On 8/26/12, Ravi Ranjan ravi.c...@gmail.com javascript: wrote: 
   You are given many slabs each with a length and a breadth. A slab i 
 can 
  be 
   put on slab j if both dimensions of i are less than that of j. In 
 this 
   similar manner, you can keep on putting slabs on each other. Find the 
   maximum stack possible which you can create out of the given slabs 
   
   and for general n-dimesions 
   
   -- 
   You received this message because you are subscribed to the Google 
   Groups 
   Algorithm Geeks group. 
   To post to this group, send email to 
   algo...@googlegroups.comjavascript:. 

   To unsubscribe from this group, send email to 
   algogeeks+...@googlegroups.com javascript:. 
   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 
  algo...@googlegroups.comjavascript:. 

  To unsubscribe from this group, send email to 
  algogeeks+...@googlegroups.com javascript:. 
  For more options, visit this group at 
  http://groups.google.com/group/algogeeks?hl=en. 
  
  
  
  
  -- 
  
  -- 
  
  ‘Kailash Bagaria’ 
  B-tech 4th year 
  Computer Science  Engineering 
  Indian Institute of Technology, Roorkee 
  Roorkee, India (247667) 
  
  -- 
  You received this message because you are subscribed to the Google 
 Groups 
  Algorithm Geeks group. 
  To post to this group, send email to algo...@googlegroups.comjavascript:. 

  To unsubscribe from this group, send email to 
  algogeeks+...@googlegroups.com javascript:. 
  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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/ABJAgG77YhkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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 checking divisibility of binomial coefficients of a number by a prime number

[Dave]

@Ankit: Apply Lucas' Theorem, which you can find written up in Wikipedia.
 
Dave

On Sunday, August 26, 2012 3:57:18 PM UTC-5, Ankit Singh wrote:

 In mathematics, *binomial coefficients* are a family of positive integers 
 that occur as coefficients in the binomial theorem. [image: \tbinom 
 nk]denotes the number of ways of choosing k objects from n different objects.

 However when n and k are too large, we often save them after modulo 
 operation by a prime number P. Please calculate how many binomial 
 coefficients of n become to 0 after modulo by P.

 *Input*

 The first of input is an integer T , the number of test cases.

 Each of the following T lines contains 2 integers, n and prime P.

 *Output*

 For each test case, output a line contains the number of [image: \tbinom 
 nk]s (0=k=n) each of which after modulo operation by P is 0.

 *Sample Input*

 3

 2 2

 3 2

 4 3

 *Sample Output*

 1

 0

 1

 *Constraints:*

 T is less than 100

 n is less than 10500.
 P is less than 109.
  
  
  
  
 I Have applied a logic that if any binomial coefficient can be written as 
 n!/(n-k)!k!  so if (n/p)((n-k)/p+k/p) so that coefficient will be 
 divisiblr by prime number p. but the problem is range of is so large so if 
 i give an input of that much range it will take more then 15 min . although 
 complexity of my code is O(n/2) but my program keep on running because of 
 very high range of input. Can anyone help me in this please??
  
 Thank you


-- 
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/-/aLFSGCkdtmsJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Printing random word from file

[Dave]

@Kunal: Yes. You are missing that you don't know the number of words in the 
file in advance. So, to use your method, you would have to read the file 
once to find n, and then read through it again to select the lucky_pos th 
word. The method I proposed only requires reading the file once. 
 
Furthermore, assuming that rand() produces a random non-negative integer, 
rand()%n is not equiprobable for all values of n. Consider n = 3. Then 
since rand() takes on 2^31 values, rand()%3 cannot take on the values 0, 1, 
and 2 with equal probability since 2^31 is not divisible by 3.
 
Dave

On Saturday, August 25, 2012 1:44:03 PM UTC-5, Kunal Patil wrote:

 How about using rand()%n ??
 Like, calculate lucky_pos = rand()%n
 Then print word at lucky_pos th position...
 Am I missing anything? All words are still equiprobable to get printed 
 right?
 On Aug 20, 2012 11:45 AM, Dave dave_an...@juno.com javascript: 
 wrote:

 @Navin: Okay. Here is a paraphrase. Assume double function random() 
 returns a uniformly distributed random number = 0.0 and  1.0.
  
 read first word from file into string save;
 int i = 1
 while not EOF
 {
 read next word from file into string temp;
 i++;
 if( i * random()  1.0 )
 copy temp to save;
 }
 print save;
  
 Dave

 On Monday, August 20, 2012 12:02:54 AM UTC-5, Navin Kumar wrote:

 @Dave sir, I didn't get your logic. Can you please elaborate it? 

 On Sun, Aug 19, 2012 at 4:08 AM, Dave dave_an...@juno.com wrote:

 @Navin: Here is the algorithm:
  
 Save the first word. 
 For i = 2, 3, ..., n = number of words in the file
 replace the saved word with the i-th word with probability 1/i.
 When EOF is reached, every word in the file will have probability 1/n 
 of being the saved word. Print it.
  
 Dave
  
 On Saturday, August 18, 2012 1:28:56 AM UTC-5, Navin Kumar wrote:

 Print a *Random word* from a file. Input is path to a file, 

 constraints- No extra memory like hashing etc. All the words in the 
 file should have equal probability.

  -- 
 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/-/HxO-wNzEP9gJhttps://groups.google.com/d/msg/algogeeks/-/HxO-wNzEP9gJ
 .

 To post to this group, send email to algo...@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+...@**
 googlegroups.com.
 For more options, visit this group at http://groups.google.com/**
 group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.


  -- 
 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/-/crET-x06vpkJ.
 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/pvqb27sRhFAJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Hii

[Dave]

@MH: What happens is that it does not answer the given question.
 
Dave 

On Wednesday, August 22, 2012 1:00:53 PM UTC-5, The Mad Hatter wrote:

 On 08/14/2012 05:56 PM, ragavenderan venkatesan wrote: 
  Given Xor of 3 numbers, How can we derive back those 3 numbers? 
  Can any one explain with an example? 
  

 maybe you're just making the wrong question :) 

 x = 1 
 y = 2 
 x = x XOR y 
 y = y XOR x 
 x = x XOR y 

 what happens? 


-- 
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/-/2hRCLd21O0wJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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:

[Dave]

@Wladimirufc: You responded that the type is int. This data type (usually) 
is 32 bits in length, and stores integers in the twos-complement number 
system. See http://en.wikipedia.org/wiki/Two%27s_complement for an 
explanation of this number system. In this number system, the bits 
(numbered 0 to 31 from the right) have values 2^i (2 to the ith power) for 
i = 0, 1, ..., 30, while bit 31 has value -2^31. 
 
In your code, you set x to have a 1-bit in bit 31 and zeros elsewhere. 
Thus, the value of x is -2^31, which is the value printed by the first 
printf() statement. This value is negative, so the value is negated. In 
twos-complement arithmetic, a value is negated by complementing the value 
(switching 0s to 1s and 1s to 0s) and then adding 1. I.e., the statement x 
= -x is functionally equivalent to x = (~x) + 1. For your value of x, the 
resulting value is the same as the original value, so the second printf() 
statement also prints the value -2^31.
 
I'm glad you asked this question because it is very important to understand 
how quantities are stored in C and how the arithmetic works.
 
Dave

On Tuesday, August 21, 2012 11:25:11 AM UTC-5, wladimirufc wrote:

  Somebody could explain to me why this happen:
  x = (131);
  printf(%d\n,x);
  if(x0) x = -x;
  printf(%d\n,x);

 Output:

 -2147483648
 -2147483648

 Wladimir Araujo Tavares
 *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
 Homepage http://lia.ufc.br/%7Ewladimir/ | 
 Maratonahttps://sites.google.com/site/quixadamaratona/|
 *

   


-- 
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/-/7a3Wer6PRRQJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[Dave]

@Megha: Answered in one line of code in the post 
https://groups.google.com/d/msg/algogeeks/Fa-5AQR3ACU/jlmjb_nEZCsJ, which 
also contains a link to an explanation of how the algorithm works.
 
Dave

On Tuesday, August 21, 2012 8:23:21 AM UTC-5, megha agrawal wrote:


Can anyone suggest solution for this problem?


You are given an unsigned integer.Write a function to print the next
number which will be having same number of 1 bits present in given num.
eg) 6(110) to 9(1001)



-- 
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/-/F8_qYQin6_MJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re:

[Dave]

@Wladimirufc: As I said, this is the functional equivalent. Most computer 
cpus would have a negate instruction which performs these operations in the 
chip's circuitry, or achieve the same result by subtraction from zero.
 
Dave

On Tuesday, August 21, 2012 4:58:14 PM UTC-5, wladimirufc wrote:

 I understand two complement but i don`t knew it  this instruction x = -x 
 was translate in  x =(~x) + 1

 thanks!

 Wladimir Araujo Tavares
 *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
 Homepage http://lia.ufc.br/%7Ewladimir/ | 
 Maratonahttps://sites.google.com/site/quixadamaratona/|
 *

   


 On Tue, Aug 21, 2012 at 2:36 PM, gmag...@gmail.com javascript: 
 gmag...@gmail.com javascript: wrote:

 @dave Nice explanation!


 Yanan Cao



 On Tue, Aug 21, 2012 at 10:32 AM, Dave dave_an...@juno.com javascript:
  wrote:

 @Wladimirufc: You responded that the type is int. This data type 
 (usually) is 32 bits in length, and stores integers in the twos-complement 
 number system. See http://en.wikipedia.org/wiki/Two%27s_complement for 
 an explanation of this number system. In this number system, the bits 
 (numbered 0 to 31 from the right) have values 2^i (2 to the ith power) for 
 i = 0, 1, ..., 30, while bit 31 has value -2^31. 
  
 In your code, you set x to have a 1-bit in bit 31 and zeros elsewhere. 
 Thus, the value of x is -2^31, which is the value printed by the first 
 printf() statement. This value is negative, so the value is negated. In 
 twos-complement arithmetic, a value is negated by complementing the value 
 (switching 0s to 1s and 1s to 0s) and then adding 1. I.e., the statement x 
 = -x is functionally equivalent to x = (~x) + 1. For your value of x, the 
 resulting value is the same as the original value, so the second printf() 
 statement also prints the value -2^31.
  
 I'm glad you asked this question because it is very important to 
 understand how quantities are stored in C and how the arithmetic works.
  
 Dave

 On Tuesday, August 21, 2012 11:25:11 AM UTC-5, wladimirufc wrote:

  Somebody could explain to me why this happen:
   x = (131);
  printf(%d\n,x);
  if(x0) x = -x;
  printf(%d\n,x);

 Output:

 -2147483648
 -2147483648

 Wladimir Araujo Tavares
 *Federal University of Ceará http://lia.ufc.br/%7Ewladimir/
 Homepage http://lia.ufc.br/%7Ewladimir/ | 
 Maratonahttps://sites.google.com/site/quixadamaratona/|
 *

   

  -- 
 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/-/7a3Wer6PRRQJ.

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/wkyMQqvnOnkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Printing random word from file

[Dave]

@Navin: Okay. Here is a paraphrase. Assume double function random() returns 
a uniformly distributed random number = 0.0 and  1.0.
 
read first word from file into string save;
int i = 1
while not EOF
{
read next word from file into string temp;
i++;
if( i * random()  1.0 )
copy temp to save;
}
print save;
 
Dave

On Monday, August 20, 2012 12:02:54 AM UTC-5, Navin Kumar wrote:

 @Dave sir, I didn't get your logic. Can you please elaborate it? 

 On Sun, Aug 19, 2012 at 4:08 AM, Dave dave_an...@juno.com 
 javascript:wrote:

 @Navin: Here is the algorithm:
  
 Save the first word. 
 For i = 2, 3, ..., n = number of words in the file
 replace the saved word with the i-th word with probability 1/i.
 When EOF is reached, every word in the file will have probability 1/n of 
 being the saved word. Print it.
  
 Dave

 On Saturday, August 18, 2012 1:28:56 AM UTC-5, Navin Kumar wrote:

 Print a *Random word* from a file. Input is path to a file, 

 constraints- No extra memory like hashing etc. All the words in the file 
 should have equal probability.

  -- 
 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/-/HxO-wNzEP9gJ.

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/crET-x06vpkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Printing random word from file

[Dave]

@Navin: Here is the algorithm:
 
Save the first word. 
For i = 2, 3, ..., n = number of words in the file
replace the saved word with the i-th word with probability 1/i.
When EOF is reached, every word in the file will have probability 1/n of 
being the saved word. Print it.
 
Dave

On Saturday, August 18, 2012 1:28:56 AM UTC-5, Navin Kumar wrote:

 Print a *Random word* from a file. Input is path to a file, 

 constraints- No extra memory like hashing etc. All the words in the file 
 should have equal probability.

-- 
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/-/HxO-wNzEP9gJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: MICROSOFT QUESTION

[Dave]

@Navin: Why? No division is used.
 
Dave

On Thursday, August 16, 2012 9:20:03 AM UTC-5, Navin Kumar wrote:

 We have to consider cases when an element is zero. 

 On Thu, Aug 16, 2012 at 7:07 PM, shady sin...@gmail.com javascript:wrote:

 well we can do with just one array. Overwrite the answer directly on 
 left[] array.


 On Thu, Aug 16, 2012 at 6:47 PM, mohit mohitsi...@gmail.comjavascript:
  wrote:


 here are the steps :
 1) Construct a temporary array left[] such that left[i] contains product 
 of all elements on left of A[i] excluding A[i].
 2) Construct another temporary array right[] such that right[i] contains 
 product of all elements on on right of A[i] excluding A[i].
 3) To get OUT[], multiply left[] and right[]. 

 time complexity : O(n)


 On Thursday, August 16, 2012 2:26:58 PM UTC+5:30, ram wrote:


 Hi,

This is a microsoft question asked in our campus previous year. 
 Anyone having idea please share it here...

Given an array of n elements A[n]. Write a program to create a new 
 array OUT[n], 



 which has its elements as multiplication of all the elements in 
 the input array A[n] except that element (i.e.) OUT[2] = A[0] * A[1] * 
 A[3] * ? * A[n-1]. 
  Constraint is one should not use division operator.

  -- 
 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/-/iqyLUMLQRS0J.

 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/cOrXdXwNPUQJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] MICROSOFT QUESTION

[Dave]

@Shady: You can do it with just the input array and the output array. In 
the language of Atul007, put temp2 in the output array, and calculate temp1 
as a scalar, i.e., one element at a time as you replace the elements of 
temp2 with the result.
 
Dave

On Thursday, August 16, 2012 5:40:23 AM UTC-5, shady wrote:

 for n elements, space used - 2n
 can we do better ?

 On Thu, Aug 16, 2012 at 3:20 PM, atul anand atul.8...@gmail.comjavascript:
  wrote:

 input :   23   45
 temp1 : 26   24   120
 temp2 : 120  60  20   5

 for given input ..take tow temp array.
 temp1[i] = input[0] * input[1] * input[2] * input[3]..input[i]
 temp2[i] = input[i] * input [i + 1] * input[i + 2]input[n];

 now out[i] = temp1[i-1] * temp2[i+1];


 On Thu, Aug 16, 2012 at 2:26 PM, Hariraman R rphar...@gmail.comjavascript:
  wrote:


 Hi,

This is a microsoft question asked in our campus previous year. 
 Anyone having idea please share it here...


Given an array of n elements A[n]. Write a program to create a new 
 array OUT[n], 

 which has its elements as multiplication of all the elements in the 
 input array A[n] except that element (i.e.) OUT[2] = A[0] * A[1] * A[3] * ? 
 * A[n-1]. 
  Constraint is one should not use division operator.

  -- 
 You received this message because you are subscribed to the Google 
 Groups Algorithm Geeks group.
 To post to this group, send email to algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 algo...@googlegroups.comjavascript:
 .
 To unsubscribe from this group, send email to 
 algogeeks+...@googlegroups.com javascript:.
 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 view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/u9VqcQM6sz0J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: coin problem

[Dave]

@Navin: Divide the coins into two groups of 10, and then flip all of the 
coins in one of the groups. Suppose group A has x heads and 10 - x tails. 
Then before you flip them, group B has 10 - x heads and x tails. After you 
flip them, group B has x heads and 10 - x tails.
 
Dave

On Tuesday, July 31, 2012 2:03:09 AM UTC-5, Navin Kumar wrote:

 You are blindfolded and 20 coins are placed on the table in front of you. 
 Out of them 10 coins have heads facing up and other tails. You are allowed 
 to flip and move the coins. You should divide those coins into two sets 
 such that one set contains 10 heads and other tails. You are allowed to 
 only move or flip the coins

-- 
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/-/5D_9gPnjvZ0J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: absolute minimum difference

[Dave]

@s_m154: Sort the array in O(n log n) and then compare adjacent numbers to 
find the closest pair in O(n). Total: O(n log n).
 
Dave

On Friday, July 27, 2012 10:41:28 AM UTC-5, s_m154 wrote:

 Can you please give the algo of solving it in O(nlogn)

 On Friday, 27 July 2012 15:35:24 UTC+5:30, Navin Kumar wrote:

 Given array of integers (0 or +ve or -ve value) find two elements having 
 minimum difference in their absolute values.
 e.g. Input {10 , -2, 4, 9,-20,17,-8,14,12)
 output {9,-8}

 I have solved it in O(nlogn). can it be solved in O(n).



-- 
You received this message because you are subscribed to the Google Groups 
Algorithm Geeks group.
To view this discussion on the web visit 
https://groups.google.com/d/msg/algogeeks/-/9HjgwKTqomAJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: absolute minimum difference

[Dave]

@Arun: I left out that you sort the array by absolute values and compare 
absolute values of adjacent elements. The sorted array would be {-2, 4, -8, 
9, 10, 12, 14, 17, -20}. Then abs(abs(-8) - abs(9)) is the smallest 
difference.
 
Dave
 
Dave

On Friday, July 27, 2012 11:21:52 PM UTC-5, Arun Kindra wrote:

 @Dave Sir : Sir if u sort the array(given above) the array would be: 
 -20,-8-2,4,9,10,12,14,17, and according to ur suggestion, the only ans is 
 {9,10}...but one of the ans {9,-8} is also possible...as he is asking 
 the difference in absolute values. 

 correct me if i m wrong...


-- 
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/-/xqgVivlgw68J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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

[Dave]

@Ahmad: This is known as a Collatz Sequence. It is hypothesized that the 
sequence will eventually reach 1 for every starting number N. So here is an 
algorithm to find where they meet, using O(1) space:
 
1. Generate each sequence and count the number of iterations required to 
reach 1. You need not store the sequences. Call the iteration counts C1 and 
C2.
2a. If C1 = C2, restart sequence 1 and iterate it for C1 - C2 steps. Then 
restart sequence 2 and iterate the two sequences simultaneoulsy until they 
agree.
2b. If C2  C1, restart sequence 2 and iterate it for C2 - C1 steps. Then 
restart sequence 1 and iterate the two sequences simultaneously until they 
agree.
 
Dave

On Thursday, July 26, 2012 12:39:44 PM UTC-5, Ali Ahmad Ansari wrote:

 Given a number N, generate a sequence S such that
 S[ 0 ] = N
 S[ i+1 ] = (3 * S[ i ] + 1) / 2 if S[ i ] is odd,
 = S[ i ] / 2, if S[ i ] is even,
 till you reach 1.
 For example for N = 5, the sequence is 5, 8, 4, 2, 1
 Given two numbers 20 and 35, generate the sequence S for A
 and B, and find the number where the two sequences meet.
 a.20
 b.30
 c.35
 d.40


-- 
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/-/lBJL5zrohL8J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Directi Written Q 2012

[Dave]

@Ruru:
 
int i,j,sum=100*101/2;
for( i = 1 ; i = 100 ; ++i )
{
j = i;
while( j )
{
j  = 1;
sum -= j
}
}
printf(%i\n,sum);
 
Dave
 
On Tuesday, July 24, 2012 4:39:42 AM UTC-5, ruru wrote:

 find no. of 1's in binary format of numbers from 1 to 100. like for 
 1 to 10 answer is 17 


-- 
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/-/c-FrS-OzdhsJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.

Re: [algogeeks] Re: Finding the repeated element

[Dave]

@Arun: The referenced algorithm solves the wrong problem. The problem given 
has n-2 unique elements and 1 element repeated twice. The referenced 
algorithm has n-1 elements that occur in pairs and one that is unique; 
xoring will solve this problem, but it won't help solve the given one.
 
Dave

On Monday, July 23, 2012 12:55:01 PM UTC-5, Arun Kindra wrote:

 This will help u
 http://www.geeksforgeeks.org/archives/570 

-- 
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/-/EFi5PG1OKTkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Appropriate data structure

[Dave]

@All: We seem to have different understandings of the problem. So Navin, as 
original poster, answer this question: Is k known in advance, or is it 
given in the request for the min and max elements. I assumed the latter, so 
that one request could ask for the max and min of the last 5 days and 
another could ask for the max and min for the last 100 days. Others seem to 
assume that k is known as the data are collected.
 
Dave

On Saturday, July 14, 2012 2:55:48 PM UTC-5, Navin Kumar wrote:

 A set of integer values are being received (1 per day). Store these values 
 and at any given time, retrieve the min and max value over the last k days. 
 What data structures would you use for storing and retrieving ?

-- 
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/-/c58RGUBQobUJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Remove duplicates from min-heap.

[Dave]

@Navin: A sorted array is a heap. So use the second half of a heap sort 
algorithm to produce the array in sorted order. You can store the sorted 
array backwards in the original array. Then reverse the array and squeeze 
out the duplicates. O(n log n).
 
Dave

On Saturday, July 14, 2012 3:28:29 PM UTC-5, Navin Kumar wrote:

 Remove duplicates from a min-heap.


-- 
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/-/0aCpM-WSME0J.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from 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: Appropriate data structure

[Dave]

@Navin: I would use a linked list containing the value and date, with extra 
pointers to the next larger element and the next smaller element. 
 
New items are inserted at the head of the list. Then the next larger 
pointer is updated by searching the list of next larger pointers, beginning 
with the original head's next larger pointer, for the first element larger 
than the current element; if no larger element is found, set the next 
larger pointer to null. The next smaller pointer is updated similarly.
 
When a request is made, the list formed by the next larger pointers, 
starting with the head node, is searched for the last item whose date 
differs from the current date by  k, and similarly the list formed by the 
next smaller pointers.
 
Dave

On Saturday, July 14, 2012 2:55:48 PM UTC-5, Navin Kumar wrote:

 A set of integer values are being received (1 per day). Store these values 
 and at any given time, retrieve the min and max value over the last k days. 
 What data structures would you use for storing and retrieving ?

-- 
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/-/57HnzcO4goUJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.