[algogeeks] Re: find output

[sankalp srivastava]

A better place to put these types of questions would be www.stackoverflow.com

On Jul 4, 10:45 pm, amit kumar  wrote:
> thanx guys...
>
> On Mon, Jul 4, 2011 at 5:11 PM, mahesh.jnumc...@gmail.com <
>
>
>
>
>
>
>
> mahesh.jnumc...@gmail.com> wrote:
> > In while loop, the value of i will be used as 0 as it is post decrement so
> > the value of i will decrement after the while loop is executed.
> > so 0!=0 will fail and the value of i will get decrement and will be printed
> > as -1.
>
> > On Mon, Jul 4, 2011 at 3:54 PM, amit the cool 
> > wrote:
>
> >> main()
> >> {
> >> int i=0;
> >> while(+(+i--)!=0)
> >> i-=i++;
> >> printf("%d",i);
> >> }
>
> >> output sud be 1
> >> bt it is -1;
> >> why??
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: array size problem

[sankalp srivastava]

due to constant folding

On Jul 4, 6:54 am, Navneet Gupta  wrote:
> If you can, refer to "Constants" chapter in Bruce Eckel. He he smartly
> explained how const are different for C & C++.
>
> The e-book is free to download from net.
>
>
>
>
>
>
>
>
>
> On Mon, Jul 4, 2011 at 2:50 AM, Gene  wrote:
> > Why do bicycles have 2 wheels and tricycles 3?  The designers made
> > them that way.
>
> > So you're probably asking why they were designed that way.
>
> > C++ came after C.  In general C++ seeks to de-emphasize use of the pre-
> > processor because macro substitution is generally considered to make
> > maintenance more difficult.
>
> > Consequently, in C you would say
> > #define ArraySize 100
> > and this will work in C++, too.  But C++ gives you the addtional
> > "preferred" way.
>
> > On Jul 3, 4:17 pm, Deoki Nandan  wrote:
> >> WHY?
> >> In C++, you can do something like
>
> >> const int ArraySize = 100;
> >> int Array[ArraySize];
>
> >> while in ANSI C, this would be flagged as an error.
>
> >> --
> >> **With Regards
> >> Deoki Nandan Vishwakarma
>
> >> *
> >> *
>
> > --
> > You received this message because you are subscribed to the Google Groups 
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to 
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group 
> > athttp://groups.google.com/group/algogeeks?hl=en.
>
> --
> --Navneet

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

[algogeeks] Re: c code help

[sankalp srivastava]

@ankit agarwal , it is giving zero because the region the pages are
allocated for it in the .rodata section (With pointer to it pushed on
the stack) is zeroed out .It can even give segmentation fault in many
cases and the behaviour here in operating system and compiler
dependent

On Jun 23, 5:14 pm, Anika Jain  wrote:
> oki.. thanx :)
>
> On Thu, Jun 23, 2011 at 5:39 PM, Ankit Agarwal wrote:
>
>
>
> > 1) p1[-3] is an invalid address and thereby, it is giving 0.
>
> > 2) p1[3]='e' having 101 as ASCII value, thus -p1[3]=-101 as integer.
>
> > On Thu, Jun 23, 2011 at 5:36 PM, Anika Jain wrote:
>
> >> 1)
> >> int main()
> >> {
> >>     char *p1="cquestionbank";
> >>     printf("%d",p1[-3]);
> >>     return 0;
> >> }
>
> >> why is it giving 0??
>
> >> 2)
> >> int main()
> >> {
> >>     char *p1="cquestionbank";
> >>     printf("%d",-3[p1]);
> >>     return 0;
> >> }
>
> >> why is this giving -101??
>
> >>  --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > Ankit Agarwal
>
> > *Be the change that you want to see in the world... :)*
> > *- Gandhiji*
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -

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

[algogeeks] Re: Google Question

[sankalp srivastava]

1,2,43,41,5 , 6
Start at a[3] and a[5] Swap them up .
Reversing it , we get
1,2,43,5,6,41
This does not work
 .
On Jun 23, 9:05 pm, Swathi  wrote:
> We just need to find the start and end of the decreasing sequence then we
> have to reverse the elements in that decreasing sequence by swapping the
> elements at both the edges...
>
> On Thu, Jun 23, 2011 at 2:13 PM, sankalp srivastava <
>
>
>
> richi.sankalp1...@gmail.com> wrote:
> > @piyush Sinha
>
> > How can you do it in O(1) space and O(n) time dude .The inplace
> > merging of d sorted arrays take space O(log d) space at least i
> > think .Plus even at every step , we have to do O(log n) comparisions
> > to find the next larger or smaller element .How can this be O(n) ???
>
> > WAiting eagerly for a reply
> > On Jun 22, 3:24 pm, Dumanshu  wrote:
> > > @Piyush: could u plz post the link to the same?
>
> > > On Jun 22, 2:15 pm, Piyush Sinha  wrote:
>
> > > > This question has been discussed over here once...It was concluded
> > > > that this can be solved in O(n) if we know there is a fixed range up
> > > > to which the elements keep on increasing and decreasing..for example
> > > > in an array of 12 elements, we know 3 elements keep on increasing
> > > > monotonically, then 3 elements keep on decreasing monotonically and so
> > > > on
>
> > > > On 6/22/11, chirag ahuja  wrote:
>
> > > > > Given an array of size n wherein elements keep on increasing
> > > > > monotonically upto a certain location after which they keep on
> > > > > decreasing monotonically, then again keep on increasing, then
> > > > > decreasing again and so on. Sort the array in O(n) and O(1).
>
> > > > > I didn't understand the question, any array of n elements will be
> > like
> > > > > this except when first there is a decrese from index 0 to a higher
> > > > > index. Any ideas about how to solve it in given constraints??
>
> > > > > --
> > > > > You received this message because you are subscribed to the Google
> > Groups
> > > > > "Algorithm Geeks" group.
> > > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > > To unsubscribe from this group, send email to
> > > > > algogeeks+unsubscr...@googlegroups.com.
> > > > > For more options, visit this group at
> > > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > > > --
> > > > *Piyush Sinha*
> > > > *IIIT, Allahabad*
> > > > *+91-8792136657*
> > > > *+91-7483122727*
> > > > *https://www.facebook.com/profile.php?id=10655377926*-Hidequoted
> > text -
>
> > > > - Show quoted text -
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -

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

[algogeeks] Re: sort the array

[sankalp srivastava]

People should not just come over  here  , write one word and go .If
you cannot explain you're logic with an example , means you haven't
even tried the problem .You just want to boast you're adroit .In place
merging of two sorted is not an easy problem . .

On Jun 22, 9:48 pm, ankit mehta  wrote:
> Yes thats what I am saying that algorithm presented by Mr. Navneet
> wont work.
>
> On Jun 22, 9:40 pm, Apoorve Mohan  wrote:
>
>
>
>
>
>
>
> > @ankit: we need an inplace algorithm :)

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

[algogeeks] Re: Google Question

[sankalp srivastava]

@piyush Sinha

How can you do it in O(1) space and O(n) time dude .The inplace
merging of d sorted arrays take space O(log d) space at least i
think .Plus even at every step , we have to do O(log n) comparisions
to find the next larger or smaller element .How can this be O(n) ???

WAiting eagerly for a reply
On Jun 22, 3:24 pm, Dumanshu  wrote:
> @Piyush: could u plz post the link to the same?
>
> On Jun 22, 2:15 pm, Piyush Sinha  wrote:
>
>
>
>
>
>
>
> > This question has been discussed over here once...It was concluded
> > that this can be solved in O(n) if we know there is a fixed range up
> > to which the elements keep on increasing and decreasing..for example
> > in an array of 12 elements, we know 3 elements keep on increasing
> > monotonically, then 3 elements keep on decreasing monotonically and so
> > on
>
> > On 6/22/11, chirag ahuja  wrote:
>
> > > Given an array of size n wherein elements keep on increasing
> > > monotonically upto a certain location after which they keep on
> > > decreasing monotonically, then again keep on increasing, then
> > > decreasing again and so on. Sort the array in O(n) and O(1).
>
> > > I didn't understand the question, any array of n elements will be like
> > > this except when first there is a decrese from index 0 to a higher
> > > index. Any ideas about how to solve it in given constraints??
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > *Piyush Sinha*
> > *IIIT, Allahabad*
> > *+91-8792136657*
> > *+91-7483122727*
> > *https://www.facebook.com/profile.php?id=10655377926*-Hide quoted text -
>
> > - Show quoted text -

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

[algogeeks] Re: BST

[sankalp srivastava]

If nothing is allowed , as in extra space etcetera We can use morris
traversal to find the inorder of the tree .

On Jun 19, 3:25 am, kumar vr  wrote:
> Balance the tree and return the Root.
>
> On Sun, Jun 19, 2011 at 12:10 AM, hary rathor wrote:
>
> > then you can use iterative  method instead of recursion ...
>
> >  --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: Building a Binary tree with XOR

[sankalp srivastava]

you might want to explain what you want to do with an example !

On Apr 20, 11:09 am, sunil  wrote:
> Hi All,
>
> Before starting any binary tree problem I will be creating such kind
> of binary tree and will be solving that problem accordingly.
>
> From the last few days I am trying to code to build a binary tree with
> "Exclusive Operators". Here I am trying to build the tree in the level
> order way like all the elements will be placed in the queue in the
> order of levels so that the final binary tree will be almost complete
> binary tree.
>
> In general the left node will contain the left side tree adress
> details and right node will contain the right tree details.
> But the XOR Binary trees will be holding the XOR values of parent and
> left child in the left node and in the same way the parent and right
> child will be in the right part.
>
> Here I am unable to track the "parent" of a particular node after the
> level 3. Does it possible to create a XOR binary tree with the level
> order mechanism. If possible, could you provide me clues in resolving
> this problem.
>
> My files looks like as below
>
> Header file:
> 
> #include
> #include
> using namespace std;
> typedef unsigned long pointer;
>
> struct BTXNode
> {
>        int data;
>        struct BTXNode* fleft;
>        struct BTXNode* fright;
>
> };
>
> class BTX
> {
>
>        struct BTXNode *root;
>
>        public:
>        BTX()
>        {
>                root=NULL;
>        }
>        struct BTXNode* getNode(int data);
>        int insertAtLeaf(struct BTXNode* node);
>
> };
>
> --
>
> CPP file
> ---
> #include "btf_xor.h"
>
> struct BTXNode* BTX::getNode(int data)
> {
>        struct BTXNode* node=new BTXNode();
>
>        node->data=data;
>        node->fleft=NULL;
>        node->fright=NULL;
>
>        return node;
>
> }
>
> int BTX::insertAtLeaf(struct BTXNode* nd)
> {
>        cout<<"insertAtLeaf"<<" Data is "        bool  right_ind=false;
>        struct BTXNode *parent=NULL;
>        if(!root)
>        {
>                root=nd;
>                return 1;
>        }
>        queue q;
>        q.push(root);
>        q.push(NULL);
>
>        while(!q.empty() && set_ind)
>        {
>
>                struct BTXNode *temp=q.front();
>                q.pop();
>
>                if(temp)
>                {
>                        cout<<"temp->data is"fleft != parent)
>                        {
>                                struct BTXNode* left=(struct BTXNode*)
> ((pointer)temp->fleft^(pointer)parent);
>
>                                q.push(left);
>                                right_ind=true;
>                        }
>                        else
>                        {
>                                nd->fleft=(struct BTXNode*)
> ((pointer)temp ^ (pointer)nd->fleft);
>                                nd->fright=(struct BTXNode*)
> ((pointer)temp ^ (pointer)nd->fright);
>                                //temp->fleft=(struct BTXNode*)
> ((pointer)nd ^ (pointer)parent);
>                                temp->fleft=(struct BTXNode*)
> ((pointer)nd ^ (pointer)temp->fleft);
>                                right_ind=false;
>                                set_ind=false;
>
>                        }
>                        if(right_ind)
>                        {
>                                if(temp->fright != parent)
>                                {
>                                     struct BTXNode* right=(struct
> BTXNode*)((pointer)temp->fright^(pointer)parent);
>
>                                     q.push(right);
>                                     right_ind=true;
>                                }
>                                else
>                                {
>                                      nd->fright=(struct BTXNode*)
> ((pointer)temp ^
> (pointer)nd->fright);
>                                      nd->fleft=(struct BTXNode*)
> ((pointer)temp ^ (pointer)nd->fleft);
>
>                                      //temp->fright=(struct BTXNode*)
> ((pointer)nd ^
> (pointer)parent);
>                                      temp->fright=(struct BTXNode*)
> ((pointer)nd ^ (pointer)temp->fright);
>
>                                      set_ind=false;
>                                }
>                        }
>                        parent=temp;
>                }
>                else
>                {
>                        if(!q.empty())
>                        {
>                                q.push(NULL);
>                        }
>
>                }
>        }
>
> }
>
> int main()
> {
>        BTX btx;
>        btx.insertAtLeaf(btx.getNode(10) );
>        btx.insertAtLeaf(btx.getNode(8));
>        btx.insertAtLeaf(btx.getNode(12));
>        btx.insertAtLeaf(btx.getNode(7));
>        btx.insertAtLeaf(btx.getNode(9));

[algogeeks] Re: Reading Huge input from the terminal in least time.

[sankalp srivastava]

use this
#include
#include

char ipos, opos, InpFile[2000], OutFile[2000], DIP[20];
inline int input(int flag=0) {

while(*ipos <= 32) ++ipos;//skips white spaces

if ( flag ) return (*ipos++ - '0'); / For getting Boolean Characters
*/
int x=0, neg = 0;char c;
while( true ) {
c=*ipos++;
if(c == '-') neg = 1;
else {
if (c<=32) return neg?-x:x;
x=(x<<1)+(x<<3)+c-'0';
}
}
}
inline void output(int x,int flag) {
int y,dig=0;
if(x<0){
*opos++='-';
x=-x;}

while (x||!dig) { y=x/10;DIP[dig++]=x-((y << 3) + (y << 1))+'0';x=y;}
while (dig--) *opos++=DIP[dig];
*opos++= flag ? '\n' : ' ';
}
inline void InitFASTIO() {
ipos = InpFile; opos = OutFile;
fread_unlocked(InpFile,2000,1,stdin);
}
inline void FlushFASTIO() {
fwrite_unlocked(OutFile,opos-OutFile,1,stdout);
}



On Apr 20, 8:06 am, abhijith reddy  wrote:
> You could read input character by character using getchar_unlocked() untill
> you hit a space or new line or EOF.
> Alternatively you read the whole input at once using fread_unlocked() and
> then process it as per your need.
>
>
>
>
>
>
>
> On Wed, Apr 20, 2011 at 7:41 AM, shubham  wrote:
> > Hello Geeks,
> > Suppose we have a 2-d array arr[1000][1000] capable of storing 10^6
> > elements in it. Input is supplied one row at a time. Then what is the
> > best possible way to read this much data in the least amount of time
> > as scanf() or cin takes a lot of time?
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: Amazon Question

[sankalp srivastava]

We can traverse 2 levels , in order to find all the cousins of the
common grandparent . Each grandparent (each node uptil height depth-2)
will have at most four cousin grandsons .

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

[algogeeks] Re: Lets C Who Really Loves Perfect Square .................

[sankalp srivastava]

@dave
But you are going over elements from 35000 to 98000 something anyway
How is it O(sqrt n) ?
But I don't think any other approach exists .(One is to use
permutations (10!-9!) )

On Feb 27, 3:03 am, Dave  wrote:
> Another optimization: Since the sum of the digits of n^2 is 45, n^2 is
> divisible by 9. Thus, we need consider only n values that are
> divisible by 3. Thus, the outer for-loop can be written
>
> for( n = 31992 ; n < 99381 ; n+=3 )
>
> Dave
>
> On Feb 23, 7:02 pm, Dave  wrote:
>
> > Try this:
>
> >         int i,k,n;
> >         long long j,nsq;
> >         for( n = 31623 ; n < 10 ; ++n )
> >         {
> >                 nsq = (long long)n * (long long)n;
> >                 j = nsq;
> >                 k = 0;
> >                 for( i = 0 ; i < 10; ++i )
> >                 {
> >                         k |= (1 << (j % 10));
> >                         j /= 10;
> >                 }
> >                 if( k == 01777 )
> >                         printf("%i %lli\n",n,nsq);
> >         }
>
> > It finds 76 answers in the blink of an eye, the first being 32043^2
> > and the last being 99066^2.
>
> > Dave
>
> > On Feb 22, 3:17 pm, bittu  wrote:
>
> > > How to find a number of 10 digits (non repeated digits) which is a
> > > perfect square? perfect square examples: 9 (3x3) 16 (4x4) 25(5x) etc.
> > > Ten digit number example 1,234,567,890
>
> > > Thanks & Regards
> > > Shashank- Hide quoted text -
>
> > - Show quoted text -

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

[algogeeks] Re: Antipodal points

[sankalp srivastava]

The points must satisfy the equation

(x-x1)(x-x2)+(y-y1)(y-y2)=0

Circle centered at origin

x2+y2=Some radius .With N points on the circle , we find out the
radius

In order to find if the two points are antipodal , we check the first
equation putting the two points and checking for any other point on
the circle if it satisfies the equation . Test for antinodality .

This will do in O(1) .
Given N points and we have to find if two points are antinodal

On Feb 26, 11:15 am, Mohan Mangal  wrote:
> Hi Vinay,
>
> Here the condition is Point lies on same circle..
> hope you got it.
>
>
>
> On Sat, Feb 26, 2011 at 10:58 AM, vinay reddy  wrote:
> > Hi Dave,
> > I don't think ur logic will cover all cases like   (1,1)(-3,-3),      (1,1)
> > (2,2)  a line connecting these points passes through origin,
> > i think the solution is, we need to compute the slope of the point at index
> > i with origin and build a binary tree with theses slopes.
> > but worst cases of this algo is N*N , if we try balancing the tree while
> > inserting I guess it can be done in NlogN
> > Thanks
> > Vinay
>
> > On Fri, Feb 25, 2011 at 9:20 AM, Gene  wrote:
>
> >> Dave's solution is best if numerical error is possible.
> >> If the points are precise, you can also do it in linear time.  Just hash
> >> the points on abs(y/x).
>
> >> --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Regards,
> Mohan Mangal
> Software Engineer, Bangalore
> Mob- 80952-03670

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

[algogeeks] Re: 25february

[sankalp srivastava]

19 (I'm driving )
Ironically I read this puzzle in chacha chaudhary comics :P

On Feb 26, 8:31 pm, anuja verma  wrote:
> 19(I m d driver and I m 19)
>
> On Feb 26, 12:35 pm, Lavesh Rawat  wrote:
>
> > *Bus Driver Problem Solution*
>
> > ok let's say you're driving a bus and it's empty. At the first stop two(2)
> > people get on. At the second stop five(5) people get on and one(1) person
> > exits. At the third stop six(6) people get on and four(4) people exit. How
> > old is the bus driver?
>
> > Update Your Answers at : Click
> > Here
>
> > Solution:
> > Will be updated after 1 day
>
> > --
>
> >                     "Never explain yourself. Your friends don’t need it and
> > your enemies won’t believe it" .

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

Re: Fwd: [algogeeks] Binary Tree Amazon

[sankalp srivastava]

Why should we start traversing towards right ?
root will be the ultimate parent anyways . May be I din get your
approach .Can you elaborate with an example as given by the Thread
starter ?
For vertical level 1 . The node is 10 and hence the sum is 10 .
For vertical line 2 (level 2) , going left and right gives a wrong
from the test case given .

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

[algogeeks] Re: SPOJ problem code:MAJOR

[sankalp srivastava]

A few problems with your code :

1)Very Unclear (sorry !):- Either use a camelCase like java or use the
c++ underscores style .Paste ur code on pastebin etc.
2)Too many loops :- It is O(n)  , but perhaps O(4000*n) , much worse
than O(n^2) in this case.
3)The problem is based on majority element concept :- No it's not !
It's a simple hashing problem .
4)Use scanf and printf , never ever use cin and cout , they are too
slow .(Same holds for java , use printwriter , never scanner etc. )


5)AC code :-http://pastebin.com/FkBiS6S3

PS:Nice practice problem , it's been 2 months since I opened spoj
(Increased my points by .6 :D):P

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

[algogeeks] Re: amazon c questn

[sankalp srivastava]

You can also free the memory of q , we don't need it anymore .
but , the code is just fine .

On Feb 13, 5:03 pm, dinesh bansal  wrote:
> On Tue, Jan 11, 2011 at 10:14 PM, snehal jain  wrote:
> > what is the wrong in the program?
>
> > main()
> > {
> > char *p,*q;
> > p=(char *)malloc(25);
>
> Check for p against NULL.
>
> > q=(char *)malloc(25);
>
> Check for p against NULL.
>
> > strcpy(p,"amazon");
> > strcpy(q,"hyd");
> > strcat(p,q);
>
> compilation error
>
> > printf("%s"p);
>
> Free allocated memory.
>
> > }
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Dinesh Bansal
> The Law of Win says, "Let's not do it your way or my way; let's do it the
> best way."

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

[algogeeks] Re: Majority Element

[sankalp srivastava]

What is a majority element ?
If you are refering to your previous post , then , use hashing

On Feb 13, 10:12 pm, Akshata Sharma  wrote:
> oops... ignore the post :-/
>
> On Feb 13, 10:07 pm, Akshata Sharma  wrote:
>
>
>
> > Given an element and an array, how will you find whether the element
> > is the majority element of the array or not in linear time?

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

[algogeeks] Re: Binary Tree Amazon

[sankalp srivastava]

Just a slight addition , you would also like to keep a record for the
maximum range of the levels (assuming the function is called as
(root , 0))


On Feb 14, 5:25 pm, jalaj jaiswal  wrote:
> use hash
>
> take an array verticalsum[]={0};
>
> the function will be like this
> void vertcal_sum(node *root, int level){
>         if(root!=NULL){
>              verticalsum[level]+=root->data;
>              vertcal_sum(root->left,level-1);
>              vertcal_sum(root->left,level+1);
>       }
>
>
>
>
>
> }
> On Mon, Feb 14, 2011 at 5:04 PM, bittu  wrote:
> > Given a binary tree with no size limitation, write a program to find
> > the sum of each vertical level and store the result in an appropriate
> > data structure (Note: You cannot use an array as the tree can be of
> > any size).
>
> >                                                      4
> >                                                  /       \
> >                                                7          8
> >                                            /      \      /  \
> >                                          10      11 /     13
> >                                                    12
>
> > here 4(root) , 11(leftsubtree's right child ), 12 (rightsubtree's left
> > child) are in same vertical Line
>
> > so here vertical line 1 is fro 10
> > vertical line 2 sum is 7
>
> > vertical line  3 sum is 4+11+12=27 (May Have Some Doubt So i Have
> > represented the figure in correct way)
>
> > vertical line  4 is 8
> > vertical line  5 is 13
>
> > Hope its clear to every one
>
> > Thanks & Regards
> > Shashank Mani
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> With Regards,
> *Jalaj Jaiswal* (+919019947895)
> Software developer, Cisco Systems
> B.Tech IIIT ALLAHABAD

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

[algogeeks] Re:

[sankalp srivastava]

First question
mode switch time < context switch time .

t1 we have embed tag
refresh -> we have meta tag
automatically redirect --> again meta tag
Display client time -- > javascript or ajax (Alert(some function ))

Third :-
It uses DP   , also in a bottom up fashion .

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

[algogeeks] Re: Minimum positive-sum subarray

[sankalp srivastava]

@above guy with cheers and all and snehal

the best way to prove wrong is by a test case , so ,

-1 -2 3 4

Ricky's solution will give the answer as 4 , while the answer is 7

@snehal .
[quote]if indices starting at 1
bothers you then take

P[i]= A[0]  + A[1] +  + A[i]
its one and the same thing.. [\Quote]
I'm really not that stupid to bother about an off-by-one error :-)
Your algo rephrased :-
 P[i] = A[1] + A[2] + … + A[i]
so ,
P[1]=-1
P[2]=-3
P[3]=0
P[4]=4

Q[i].Value = P[i].
Q[i].Index = i

So ,

Q[1]=-1 , 1
Q[2]=-3 , 2
Q[3]=0 , 3
Q[4]=4 , 4

Now , as u said , let's sort it

new Q={{4 , 4} ,{0 , 3} ,{-1 , 1} ,{-3 , 3}}
You din mention anything after this  , so I dunnoe what you plan up
from  here . How are we going to get the answer {3 , 4 } from here ?

Now ,


On Feb 2, 10:06 pm, Ricky  wrote:
> Hi you can try the following code snippet:
>         int array[] = {11, -12, 15, -3, 8, -9, 1, 8, 10, -2};
>         int length = 10;
>
>         int max = 0;
>         int current = 0;
>
>         for (int i = 0; i < length; i++)
>         {
>                 current += array[i];
>                 max = max > current ? max : current;
>         }
>         std::cout<<"Max is : "<
> Cheers!!
>
> On Feb 2, 9:04 pm, snehal jain  wrote:
>
>
>
> > @ above
> > didnt get you? why is the solution wrong? and if indices starting at 1
> > bothers you then take
>
> > P[i]= A[0]  + A[1] +  + A[i]
> > its one and the same thing..
>
> > On Wed, Feb 2, 2011 at 6:02 PM, sankalp srivastava <
>
> > richi.sankalp1...@gmail.com> wrote:
>
> > > This solution is wrong , never has it been said that the indices will
> > > occur from 1.i (if that is the case , you don't need to sort ,
> > > just return the maximum /minimum sum obtained as a result)
>
> > > The indices were b/w i..j such that 1<=i<=j<=n
>
> > > O(n) solution does not exist .The state space tree will have n! leaf
> > > nodes(because there is some ordering on the input data , otherwise it
> > > would have 2^n leaf nodes) .Traversing the tree will take O(log n!)
> > > steps , or O(n log n)
> > > In fact a slight modification to this , the subset sum problem id NP-
> > > complete .
> > > But with the Q[i] array , you can get the answer with simple recursion
> > > ( or bfs or state space search or dp ) .
>
> > > On Feb 2, 1:33 pm, snehal jain  wrote:
> > > > @ above
> > > > its nt any homework question.. i found it a good question... aftr
> > > spending a
> > > > lot of time i came up with following solution
>
> > > > Given Input Array A
>
> > > > form the prefix sum array P of A.
>
> > > > i.e P[i] = A[1] + A[2] + … + A[i]
>
> > > > Now create another array Q of pairs (Value, Index)
>
> > > > such that
>
> > > > Q[i].Value = P[i].
> > > > Q[i].Index = i
>
> > > > Now sort that array Q, considering only Q[i].Value for comparison.
>
> > > > We get a new sorted array Q’ such that Q’[i].Value Q’[i].Index
>
> > > > Time complexity o( nlogn)
>
> > > > and my O(n) which i posted earlier is giving incorrect result in some
> > > > case..so ignore that..
>
> > > > so does there exist O(n) solution for it also.. i had tried a lot but
> > > could
> > > > not figure out. but i think it should exist as there is for the other
> > > > variation..
>
> > > > On Tue, Feb 1, 2011 at 8:24 PM, sankalp srivastava <
>
> > > > richi.sankalp1...@gmail.com> wrote:
>
> > > > > You should not post homework problems .
> > > > > 1)For divide and conquer :-
> > > > >       Read about interval trees  , binary indexed trees , segments
> > > > > trees .
> > > > >       Solve this using interval tree (By the time you solve a few
> > > > > basic problems of interval tree , you would be able to figure out a
> > > > > solution)
>
> > > > > the function to calculate the parent will be
> > > > > 1) first check if the two are +ve
> > > > > 2) if yes , join both of them and also iterate on the sides left by
> > > > > both , to see if you can include them also (You only need to see the
> > > > > positive elements , no negative elements )
>
> > > > > T(n)=2T(n/2)+O(n)
>
> > > > > I gan explain in detail , please correct me if im wrong
>
> > > > > Logic :- Basically in t

[algogeeks] Re: codechef problem

[sankalp srivastava]

Don't answer this problem , it's from codechef February challenge !

On Feb 2, 6:11 pm, tech rascal  wrote:
> In a plane given n points (x1,y1) (x2,y2)(xn,yn), find the the
> maximum number of collinear points.
> plz tell me the best way to do that.

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

[algogeeks] Re: Minimum positive-sum subarray

[sankalp srivastava]

This solution is wrong , never has it been said that the indices will
occur from 1.i (if that is the case , you don't need to sort ,
just return the maximum /minimum sum obtained as a result)

The indices were b/w i..j such that 1<=i<=j<=n

O(n) solution does not exist .The state space tree will have n! leaf
nodes(because there is some ordering on the input data , otherwise it
would have 2^n leaf nodes) .Traversing the tree will take O(log n!)
steps , or O(n log n)
In fact a slight modification to this , the subset sum problem id NP-
complete .
But with the Q[i] array , you can get the answer with simple recursion
( or bfs or state space search or dp ) .

On Feb 2, 1:33 pm, snehal jain  wrote:
> @ above
> its nt any homework question.. i found it a good question... aftr spending a
> lot of time i came up with following solution
>
> Given Input Array A
>
> form the prefix sum array P of A.
>
> i.e P[i] = A[1] + A[2] + … + A[i]
>
> Now create another array Q of pairs (Value, Index)
>
> such that
>
> Q[i].Value = P[i].
> Q[i].Index = i
>
> Now sort that array Q, considering only Q[i].Value for comparison.
>
> We get a new sorted array Q’ such that Q’[i].Value Q’[i].Index
>
> Time complexity o( nlogn)
>
> and my O(n) which i posted earlier is giving incorrect result in some
> case..so ignore that..
>
> so does there exist O(n) solution for it also.. i had tried a lot but could
> not figure out. but i think it should exist as there is for the other
> variation..
>
> On Tue, Feb 1, 2011 at 8:24 PM, sankalp srivastava <
>
>
>
> richi.sankalp1...@gmail.com> wrote:
>
> > You should not post homework problems .
> > 1)For divide and conquer :-
> >       Read about interval trees  , binary indexed trees , segments
> > trees .
> >       Solve this using interval tree (By the time you solve a few
> > basic problems of interval tree , you would be able to figure out a
> > solution)
>
> > the function to calculate the parent will be
> > 1) first check if the two are +ve
> > 2) if yes , join both of them and also iterate on the sides left by
> > both , to see if you can include them also (You only need to see the
> > positive elements , no negative elements )
>
> > T(n)=2T(n/2)+O(n)
>
> > I gan explain in detail , please correct me if im wrong
>
> > Logic :- Basically in the subproblem , we would have founded the
> > maximum subarray in that well , subarray (short of words ) .So , if we
> > want to ,we can only increase the solution in the next subarray (the
> > second subproblem )
> > So , there will be three cases
>
> > Either the subarray , the most minimum sum in one of the subproblems
> > will be the answer
> > The answer will be from between the gap of the indices between the
> > solutions of the two subproblems
> > The answer will be any combination of the two
>
> > All these three can be checked in O(n) itself .
>
> > 2)Using DP(I don't know how many dp (pure dp i mean) algorithms are in
> > O(nlog n) .Never heard of any with the pure dp approach and an n log n
> > solution )
>
> > DP(classical for maximum positive sum array ) can be done by going
> > through two loops
>
> > dp[i]= minimum positive sum for an array with index (last index =i )
> > p[i]= start index corresponding to this dp[i]
>
> > dp[i]= minimum sum condition ( for each i > update p[i] accordingly .Then return  the minimum amongst dp[i] and
> > corresponding p[i] .
>
> > This is a complete search , so I don't think it will get wrong .
>
> > And i don't think it could be solved in O(n log n) (at least with
> > dp) .Because the search space tree would be of height O(log n) (with
> > no overlapping problems ) and dp lives upon overlapping subproblems .
> > Or may be , if someone could provide with a O( n log n) solution
>
> > Regards ,
> > Sankalp Srivastava
>
> > "I live the way I type , fast and full of errors "
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: google questions

[sankalp srivastava]

@above
I said some augmentation , that's why I said it (And also I like
tries :D)
If some non-determinism is condoned , may be you can use Rabin-Karp
method to improve upon storage .

On Feb 2, 1:28 pm, snehal jain  wrote:
> @ above
> you approach trie needs lot of optimization.. this will take up lot of
> space...trie is suitable in case where we want to reduce search complexity
> and its space complexity is very bad.. so hashing should be better here as
> compared to trie..
>
>  i think shashank's solution is better...
>
> On Tue, Feb 1, 2011 at 7:15 PM, sankalp srivastava <
>
>
>
> richi.sankalp1...@gmail.com> wrote:
> > I think , as juver++ said ,  you should also try reading on the
> > internet about these kinds of problems .This can be solved with an
> > augmentation of a trie (keeping a count variable at the leaf
> > ( maintaining a counter for all the word frequencies
> > accordingly )) .Just print the top ten results in the end .time
> > complexity will be O(n , log n ) .We can improve upon this solution a
> > lot using other forms of tries and some augmentation
>
> > PS:This will take some time if we do it for n characters , but since
> > you explicitly asked for 10 characters , so be it !
>
> > For your second question , try seraching "globbing" (For the
> > masochists , download the source code for glob library and go through
> > the code )
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: Amazon Written Tes Q1

[sankalp srivastava]

+Correction to the above post
This is not possible even with a counting sort because insertion still
takes O(n*n)
merge sort seems to be the best for it

On Jan 31, 6:23 pm, sankalp srivastava 
wrote:
> @manoj
> the great recursion problem has the time complexity as
> tn=2(T(n/2))+O(1) . It is not linear .
>
> ur algo is O(nlog n)
> This can be possible using a counting sort (again , use Bitsets to
> save ur space )

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

[algogeeks] Re: top search queries

[sankalp srivastava]

@guy above juver++
The solution , i don't think can get better than this , because you
need to store the querries anyway (at least for the output )

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

[algogeeks] Re: Minimum positive-sum subarray

[sankalp srivastava]

You should not post homework problems .
1)For divide and conquer :-
   Read about interval trees  , binary indexed trees , segments
trees .
   Solve this using interval tree (By the time you solve a few
basic problems of interval tree , you would be able to figure out a
solution)


the function to calculate the parent will be
1) first check if the two are +ve
2) if yes , join both of them and also iterate on the sides left by
both , to see if you can include them also (You only need to see the
positive elements , no negative elements )

T(n)=2T(n/2)+O(n)

I gan explain in detail , please correct me if im wrong

Logic :- Basically in the subproblem , we would have founded the
maximum subarray in that well , subarray (short of words ) .So , if we
want to ,we can only increase the solution in the next subarray (the
second subproblem )
So , there will be three cases

Either the subarray , the most minimum sum in one of the subproblems
will be the answer
The answer will be from between the gap of the indices between the
solutions of the two subproblems
The answer will be any combination of the two

All these three can be checked in O(n) itself .

2)Using DP(I don't know how many dp (pure dp i mean) algorithms are in
O(nlog n) .Never heard of any with the pure dp approach and an n log n
solution )

DP(classical for maximum positive sum array ) can be done by going
through two loops

dp[i]= minimum positive sum for an array with index (last index =i )
p[i]= start index corresponding to this dp[i]

dp[i]= minimum sum condition ( for each ihttp://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: google questions

[sankalp srivastava]

I think , as juver++ said ,  you should also try reading on the
internet about these kinds of problems .This can be solved with an
augmentation of a trie (keeping a count variable at the leaf
( maintaining a counter for all the word frequencies
accordingly )) .Just print the top ten results in the end .time
complexity will be O(n , log n ) .We can improve upon this solution a
lot using other forms of tries and some augmentation

PS:This will take some time if we do it for n characters , but since
you explicitly asked for 10 characters , so be it !

For your second question , try seraching "globbing" (For the
masochists , download the source code for glob library and go through
the code )

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

[algogeeks] Re: Amazon Again

[sankalp srivastava]

@wei.qui

On a second thought , if the petrol pumps have many petrol pumps
connected to it , we cannot find the answer your way or the method
suggested by me previously .
Thus , the solution becomes one to find out the Eulerian Path
(constraint based of course )

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

[algogeeks] Re: Divide the array into groups

[sankalp srivastava]

@above
Many ways to do this problem

One will be to find the bfs (there will be many and this will lead to
a forest )
This , in turn can be done in O(e+v) , using adjancy list or matrix .
Whenever , we cannot go further , start from any new uncovered node ,
and keep exploring recursively .Keep a boolean flag array for the
elements you have already covered .

Also  , this looks like a union find problem .So one can also do this
using disjoint set data structure .

http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=disjointDataStructure

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

[algogeeks] Re: first larger element in unsorted array...

[sankalp srivastava]

Another approach would be to use a counting sort method (less space
efficient though )
So , for space efficiency , we can use a bitset .element insertion
will take O(n) time in the set (with a space complexity of O(log n) )

so , for the above elements , the bitset will look like
(the p# shows the index corresponding to the array)
0p10p2p3p4p5p6p7

Now , start from the 1st element in the bitset , and find the next non-
zero element print it ..continue the loop from this element .
Not very space efficient I suppose , but it is still O(n) and time is
O(n) too .

@abhijit reddy
Ur simple dp is wrong , you should also process the left part as
pointed by juver++

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

[algogeeks] Re: Amazon Written Tes Q1

[sankalp srivastava]

@manoj
the great recursion problem has the time complexity as
tn=2(T(n/2))+O(1) . It is not linear .

ur algo is O(nlog n)
This can be possible using a counting sort (again , use Bitsets to
save ur space )

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

[algogeeks] Re: Divide the array into groups

[sankalp srivastava]

why have you divided it into three . I mean it can be divided into
many groups of consecutive .
Please write the statement properly !

On Jan 30, 11:13 am, snehal jain  wrote:
> @nishanth
> divide into groups ( not necessarily 2) in as many group as possible.. such
> that elements in each group is consecutive
>
> another example to clearify
>
> A= { 9,7, 13, 11,6,12,8,10,3, 4, 2, 16,14,17,13,15)
> ans
> <9,7,13,11,6,12,8,10>
> <3,4,2>
> <16,14,17,13,15>
>
>
>
> On Sun, Jan 30, 2011 at 11:32 AM, nishaanth  wrote:
> > @snehal..i guess you are missing something in the question...divide it into
> > 2 groups such that (there should be some other condition or criterion).
>
> > On Sun, Jan 30, 2011 at 11:29 AM, snehal jain wrote:
>
> >> my approach
>
> >> sort in nlogn and then while traversing the array put the elements in a
> >> group till they are consecutive . when a[i+1]!=a[i]+1 then put a[i+1] in
> >> different group.. now we need to rearrange elements in the group so that
> >> they are according to the given array.. but that will make it O(n^2) ..
> >> anyone with better ideas?
>
> >> On Fri, Jan 21, 2011 at 1:20 PM, snehal jain wrote:
>
> >>> Divide a list of numbers into groups of consecutive numbers but their
> >>> original order should be preserved.
> >>> Example:
> >>> <8,2,4,7,1,0,3,6>
> >>> Two groups:
> >>> <2,4,1,0,3> <8,7,6>
> >>> Better than O(n^2) is expected.
>
> >>> --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com >>>  .com>
> >>> .
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >>  --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com >>  .com>
> >> .
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > S.Nishaanth,
> > Computer Science and engineering,
> > IIT Madras.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: Google Question

[sankalp srivastava]

Suppose I press As only throughout .
We will have the number of As as A*(number of keystrokes) .This is the
least we can get provided we play stupidly enough .

On Jan 29, 9:16 pm, Saikat Debnath  wrote:
> @ Sankalp : plz explain this line of yours : No. of As=A*(total number
> of keystrokes)  , gives us a bound . We
> should have a lower bound as this , we can always get this much As
>
> On Jan 29, 5:32 pm, sankalp srivastava 
> wrote:> We can do it Using a binary search approach (The cost function is
> > monotonic over here , so we can use binary search)
>
> > No. of As=A*(total number of keystrokes)  , gives us a bound . We
> > should have a lower bound as this , we can always get this much As
>
> > Take the initial value as high and low as possible
>
> > say left=1 and right=10^9
> > mid=left+right/2;
> > if(can_get(this much As))
> >        then , left=mid+1;
>
> > else if(cannot get this much As)
> >         then ,
> >               right=mid
> > Continue this search until left > maximum value which you can get using the given combinations

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

[algogeeks] Re: Amazon Again

[sankalp srivastava]

[quote]"We have a car and we need to find
a petrol pump which can provide so much of petrol that we can take a
full of the circle."[/quote]

So , we just need to find a petrol pump which takes you "just" a full
circle , not anything ahead , not anything behind .

1)Sort the petrol he can get from maximum stations .If the total
distance is not given , calculate this while sorting .
Binary search over this array for the required distance .

complexity :-O(nlogn+k)
2)Hash it !! keep a hash for all the distance in some boolean
array .now find out the one which can get you the full circle , O(n)
complexity . Not space efficient .

3)Using dynamic programming .

dp[i][j] :-The distance we still need to cover (j) .while , we are on
the started at the ith station .
dp[i][0]:- answer , we need to look at the all the dp pairs for the
answer .
dp[i][j]= min(dp[i+next[i][j-d[i][next[i]]])

Basically a BFS . O(n^2) . worst case .

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

[algogeeks] Re: Frequently one of the Top Question Asked in Amazon

[sankalp srivastava]

Spiral order .. means zigzag order for example

 1
2 3
4   5  6   7

Then , you need to print it in the order
1->2-3->7->6->5->4

Two of my friends were asked this questions in the interview , so I
will list both of the approaches .

1)Use 1 stack and 1 queue .

push the elements of one level in stack 1
and the other in queue2
print both the stack and queue recursively.

algo :-
printZigZag(node * node , int level)
{
   if(node==NULL)
  return ;
   if(level==0)
   {
 level=1;
 stack1.push(node->data);
 printZigZag(node->left , level);
 printZigZag(node->right , level);
}
else
{
level=0;
stack2.push(node->data);
printZigZag(node->left , level)
printZigZag(node->right , level)
}
}
After this recursion ends , the two stacks will have the contents as
(1)   (2)
4  2
5  3
6
7
1

Another approach would be to use two stacks . google it up .
and like this , now just print it recursively

On Jan 29, 10:17 pm, saurabh gupta  wrote:
> what do you mean by spiral order ?
>
>
>
>
>
> On Sat, Jan 29, 2011 at 8:25 PM, bittu  wrote:
> > Convert BT in to DLL such that DLL represents the Sprial order
> > traversal of BT.
>
> > "Inplace"
>
> > its Written Test Question & They wants Exact Working Code...Not
> > Approach..Be Clear..Try to provide best solutions
>
> > Thanks & Regards
> > Shashank " "The best way to escape from a problem is to solve it."
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
> Says he feels all alone in a threatening world where what lies ahead is
> vague and uncertain. Doctor says "Treatment is simple. Great clown
> Pagliacci is in town tonight. Go and see him. That should pick you up." Man
> bursts into tears. Says "But, doctor...I am Pagliacci."

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

[algogeeks] Re: design a data structure

[sankalp srivastava]

Also , there is a pretty nice theorem on the fact that , if an array's
size is increased/decreased by a constant size (like in STL vector
class), the sequence of these doubling operations always take place
O(1) time .

On Jan 30, 3:44 pm, juver++  wrote:
> 1. Add element to the end of the array.
> 2. Find median of the array, and partion the array into two sets, the second
> one (where element >= median) is removed.
>
> At each operation 2, array's size decreasing by factor 0.5.  

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

[algogeeks] Re: design a data structure

[sankalp srivastava]

Another approach will be to insert the elements in order and remove
the first(or the second) half in operation 2
Another approach would be to use a bitset  , just mark all the
elements in the specific range as 0 . We are not supposed to retrieve
the elements so , keep a bit corresponding to every element (has the
number , find it's position and put it there , a simple one one
mapping will do)
Now , just mark all top elements as false on the second go .
PS:Would come up with the proof for amortized complexity soon , but
can be done something like this

First operation O(1) , second operation O(n) .However , we can only
insert or delete , from this sequence of n items , in O(n) time in the
worst case . These operations can be completed in a sequence in O(n)
time . So the amortized complexity should be O(n)/n
or O(1) .
On Jan 30, 3:44 pm, juver++  wrote:
> 1. Add element to the end of the array.
> 2. Find median of the array, and partion the array into two sets, the second
> one (where element >= median) is removed.
>
> At each operation 2, array's size decreasing by factor 0.5.  

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

[algogeeks] Re: Amazon Again

[sankalp srivastava]

I'm sure you have misstated the problem statement

just find out the total path length and return the first petrol pump
which gives you the required milage
go greedy

On Jan 28, 5:09 pm, bittu  wrote:
> There are N petrol pumps along a circular path. Every petrol pump
> gives some amount of fixed petrol. Need not to be unique and in no
> particular order means it is random. We have a car and we need to find
> a petrol pump which can provide so much of petrol that we can take a
> full of the circle. Mileage of car is fixed.
> Distance between adjacent petrol pumps are given.
>
> Thanks & Regards
> Shashank

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

[algogeeks] Re: Google Question

[sankalp srivastava]

We can do it Using a binary search approach (The cost function is
monotonic over here , so we can use binary search)

No. of As=A*(total number of keystrokes)  , gives us a bound . We
should have a lower bound as this , we can always get this much As

Take the initial value as high and low as possible

say left=1 and right=10^9
mid=left+right/2;
if(can_get(this much As))
   then , left=mid+1;

else if(cannot get this much As)
then ,
  right=mid
Continue this search until lefthttp://groups.google.com/group/algogeeks?hl=en.

[algogeeks] Re: Good Maths Question

[sankalp srivastava]

Yuo might wanna check out The latest codeforces beta round problem
C .

On Jan 28, 8:34 pm, nishaanth  wrote:
> @All... According to the constraints(SPOJ problem) wont this dp solution
> time out ?
>
> On Tue, Jan 25, 2011 at 12:23 AM, sankalp srivastava <
>
>
>
>
>
> richi.sankalp1...@gmail.com> wrote:
> > Correct me if I'm wrong
>
> > dp[i][j]=how many numbers of length i with the last digit j(int base
> > 10)
> > dp[0][j]=0
> > dp[i][0]=dp[i-1][0] , last digit can't be zero otherwise the number
> > has i-1 digits , not j;
>
> > now the recursion to pass from one state to the next
>
> > dp[i][j]=dp[i-1][k]+1(for each value of k such that k is less than j ,
> > from 0 to k)
> > That is to say , the number of numbers with length i and last digit
> > j , will be equal to the number of numbers with the last digit k , for
> > each k less than j .One is added because , we must not have included
> > the 0 in the last case , but we will include the zero case here . this
> > one corresponds to zero case .
>
> > Finally , the answer will be
>
> > dp[n][j]  , 1<=j<=9 , sum up all these and u have the answer
> > For example for 2 digits
> > dp[1][1-9]=1 , as nothing preceeds them and as said in the problem ,
> > one digit numbers are always increasing/decreasing .
> > next dp[2][1]=dp[1][1](As only 1 is less than  , equal to 1 , the last
> > digit in this state)
> > dp[2][2]=dp[1][1]+dp[1][2] =2( 1,2 and 2,2)
> > Continuing this way , we will get the answer , may be 50  , though i
> > din code it .
>
> > similarly , for 3 digits
>
> > Correct me if not!
>
> > On Jan 25, 12:06 am, juver++  wrote:
> > > dp[i][j] - how many numbers of length i and with the last digit j.
> > > Apply the scheme to increasing and decreasing number, then find ratio.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.

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

[algogeeks] Re: Prime Numbers

[sankalp srivastava]

Okay I got it  myself

@OP
This can be done in O(n*k*logn)
where k is of order 10^3 at the very max , when u need a prime like 1
trillion

On Jan 28, 6:44 pm, sankalp srivastava 
wrote:
> Correct me if I'm wrong , but according to you , will this be the
> approach ?
>
> boolean array[10];
> int primes[100];
> void seive()
> {
>   int index=0;
>   for(int i=2;i*i<10;i++)
>   {
>          if(isprime[i])
>           {
>               primes[index++]=i;
>               for(int j=i*2;j<100;j+=i)
>               {
>                    isprimes[i]= false;
>                }
>
>            }
>    }
>    int kindex=index;
>
> }
>
> /*
>  But now , how should I find out the 1 millionth prime number ?
>  It requires another seive , i know , but it requires still bigger
> range  */
> Can you give me a pseudocode ?
> */
>
> On Jan 26, 8:20 pm, juver++  wrote:
>
>
>
> > @above One million is 10^6.
> > Problem wants 1 million of prime numbers. Not the prime numbers in range
> > 1..1000.
> > So, you should use two sieves.

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

[algogeeks] Re: zig zag

[sankalp srivastava]

No , actually it's not ... it's O(n^2) , I misunderstood the
"subsequence" thing , it could be discontinuous .. we , then need to
find the maximum of dp[l] ...

the second term makes sure that the sign of the two quantities is
alternating i.e. positive or negative !

On Jan 29, 11:06 am, nishaanth  wrote:
> @above...can you please enlighten me about the second term in the dp
> expression
> And are you sure its O(n) ?
>
> On Fri, Jan 28, 2011 at 7:08 PM, sankalp srivastava <
>
>
>
>
>
> richi.sankalp1...@gmail.com> wrote:
> > This can be done in O(n) very easily , similar to Longest increasing
> > subsequence
>
> > Solution :-
>
> > dp[l]= maximum length of the zigzag sequence upto the length l
>
> > //At any position , the particular number in the array can either
> > extend the zigzag sequence containing the last element or it can start
> > one of it's own . So the recurrance becomes
>
> > dp[i]= max(dp[j]) ,and diff[A[p[j]]]^(A[i]-A[p[j]]&31)!=0 , j
> > find out the maximum in this array , it will get you the answer .
>
> > PS:- You can also check out the Topcoder tutorials .
>
> > On Jan 27, 7:41 pm, bittu  wrote:
> > > well I found it  as it  Can be Done in O(n). but with additional space
> > > O(n)
> > > here program is written in Java
>
> > > public class ZigZag
> > > {
>
> > >  public int longestZigZag(int[] sequence)
> > >   {
> > >   if (sequence.length==1) return 1;
> > >   if (sequence.length==2) return 2;
> > >   int[] diff = new int[sequence.length-1];
>
> > >   for (int i=1;i > >  {
> > >    diff[i-1]=sequence[i]-sequence[i-1];
> > >   }
>
> > >   //90% Program is done here it self. by looking at the sign if
> > > alternative number in auxiliary array we can count longest  zigzag
> > > array
>
> > >   int sign=sign(diff[0]);
> > >   int count=0;
> > >   if (sign!=0)
> > >    count=1;
>
> > >    for (int i=1;i > >   {
> > >    int nextsign=sign(diff[i]);
> > >    if (sign*nextsign==-1){
> > >     sign=nextsign;
> > >     count++;
> > >    }
> > >   }
> > >   return count+1;
> > >  }
>
> > >  public int sign(int a)
> > >  {
> > >   if (a==0) return 0;
> > >   return a/Math.abs(a);
> > >  }
>
> > >  public static void main(String[] args)
> > >   {
> > >   ZigZag z = new ZigZag();
> > >   System.out.println(z.longestZigZag(new int[] { 1, 7, 4, 9, 2, 5 }));
> > >   System.out.println(z.longestZigZag(new int[] { 1, 17, 5, 10, 13, 15,
> > > 10, 5, 16, 8 }));
>
> > >    }
>
> > > }
>
> > > Try for Inplace
>
> > > Thanks & Regards
> > > Shashank Mani ""The best way to escape from a problem is to solve it."
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.

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

[algogeeks] Re: and or tree

[sankalp srivastava]

I am not sure you mentioned the problem statement correctly , anyways
here goes my solution .

recurse(int valuerequired , node * n , int value_now , int steps)
{
  if(node==NULL)
  return 0;

  else if(valuerequired== value_now)
 return steps;
   //we need to see the minimum number of gates to be flipped in order
to achieve the desired answer . We can flip this  gate , the gate ,
the gate left to it , and the gate right to it .
// thus the answer is
else  return min(recurse(valuerequired , node->left ,
value_now  , steps+1) , recurse(valuerequired , node->right ,
value_now , steps+1))

}

/*
 I did not quite understand the question though , can you provide with
an example ?
*/

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

[algogeeks] Re: Prime Numbers

[sankalp srivastava]

Correct me if I'm wrong , but according to you , will this be the
approach ?

boolean array[10];
int primes[100];
void seive()
{
  int index=0;
  for(int i=2;i*i<10;i++)
  {
 if(isprime[i])
  {
  primes[index++]=i;
  for(int j=i*2;j<100;j+=i)
  {
   isprimes[i]= false;
   }

   }
   }
   int kindex=index;

}

/*
 But now , how should I find out the 1 millionth prime number ?
 It requires another seive , i know , but it requires still bigger
range  */
Can you give me a pseudocode ?
*/

On Jan 26, 8:20 pm, juver++  wrote:
> @above One million is 10^6.
> Problem wants 1 million of prime numbers. Not the prime numbers in range
> 1..1000.
> So, you should use two sieves.

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

[algogeeks] Re: zig zag

[sankalp srivastava]

This can be done in O(n) very easily , similar to Longest increasing
subsequence

Solution :-

dp[l]= maximum length of the zigzag sequence upto the length l

//At any position , the particular number in the array can either
extend the zigzag sequence containing the last element or it can start
one of it's own . So the recurrance becomes

dp[i]= max(dp[j]) ,and diff[A[p[j]]]^(A[i]-A[p[j]]&31)!=0 , j wrote:
> well I found it  as it  Can be Done in O(n). but with additional space
> O(n)
> here program is written in Java
>
> public class ZigZag
> {
>
>  public int longestZigZag(int[] sequence)
>   {
>   if (sequence.length==1) return 1;
>   if (sequence.length==2) return 2;
>   int[] diff = new int[sequence.length-1];
>
>   for (int i=1;i  {
>    diff[i-1]=sequence[i]-sequence[i-1];
>   }
>
>   //90% Program is done here it self. by looking at the sign if
> alternative number in auxiliary array we can count longest  zigzag
> array
>
>   int sign=sign(diff[0]);
>   int count=0;
>   if (sign!=0)
>    count=1;
>
>    for (int i=1;i   {
>    int nextsign=sign(diff[i]);
>    if (sign*nextsign==-1){
>     sign=nextsign;
>     count++;
>    }
>   }
>   return count+1;
>  }
>
>  public int sign(int a)
>  {
>   if (a==0) return 0;
>   return a/Math.abs(a);
>  }
>
>  public static void main(String[] args)
>   {
>   ZigZag z = new ZigZag();
>   System.out.println(z.longestZigZag(new int[] { 1, 7, 4, 9, 2, 5 }));
>   System.out.println(z.longestZigZag(new int[] { 1, 17, 5, 10, 13, 15,
> 10, 5, 16, 8 }));
>
>    }
>
> }
>
> Try for Inplace
>
> Thanks & Regards
> Shashank Mani ""The best way to escape from a problem is to solve it."

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

[algogeeks] Re: 2 d matrix

[sankalp srivastava]

@above person
ur solution is O(n^3) in worst case !let's say the row[] and col[]
arrays formed are

col[]=123 124 125 126
row[]=127 , 128, 129,126

every element of row[] traverses through n  elements of the array
col[] and and makes O(n) comparisons in the worst case . Thus , each
traversal requires O(n^2) time , and there can be O(n^3) traversals ,
so , time taken will be O(n^3).

However sorting one of these arrays ,makes the time complexity as
O(n^2log n)

On Jan 26, 3:03 pm, bittu  wrote:
> As Navies it can be done in O(n^2)
>
> Make numbers by using every elements in the row in array row[].
> Similarly convert column elements into numbers and put them in array
> col[]. Now compare both the arrays where the number matches print the
> index of both row[] and col[] array...
>
> eg:-
> 2, 3, 4
> 3, 4, 5
> 6, 5, 1
>
> col[] contains 236, 345, and 451 and row[] contains 234, 345, and 651.
> On Comparison both has 345 as common total with index (1,1) and is the
> desired answer.
>
> use 2d matrix..makes it easy
>
> Time Complexity is at Most O(n^2)
>
> Thanks & Regards
> Shashank Mani  " Best Way to Escape From the Problem is to Solve It"

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

[algogeeks] Re: find a line

[sankalp srivastava]

@dave , There is a proof for it .

Let's say there is a point x0 , y0 .. and I claim that between any two
points ... x1,y1 and x2,y2 assuming they are non-collinear having a
line b/w them a line of some slope passes somewhere b/w them .This
collinearity does not affect our result .

Let's say a point x',y' divides this line into ratio m:n , this is the
point where this line is intersected by the line from x0 , y0 .. as
x1 ,y1 and x2,y2 are non-collinear , this point will always exist .
The slope of this line can be determined from the points x0,y0 and
x',y'   , which is always real .hope this makes sense to u !!

On Jan 26, 7:11 am, Dave  wrote:
> @Sankalp: So what is your code? And what is the equation of the line?
> As I said, you can't always use a line through the origin.
>
> Dave
>
> On Jan 25, 5:49 am, sankalp srivastava 
> wrote:
>
>
>
> > @dave
> > In this case , I could just shift my origin to the lowermost point :)
>
> > On Jan 25, 10:14 am, Dave  wrote:
>
> > > @Sankalp: I wanted a point far enough outside the region that a line
> > > from any point in the region could not contain any other point in the
> > > region. There are several implications: 1) if the point is to the left
> > > of the region, it can't have an integer y coordinate between 0 and B.
> > > That is where the 0.5 comes from. Second, it seemed reasonable, but
> > > not necessary, to put Y near the middle of the range [0, B]. Then I
> > > just solved for an  X that guaranteed that the slope of the line from
> > > any point in the region to the point (X, Y) had slope m satisfying  -1/
> > > A < m < 1/A. Then a line through any point (x1,y) could not intersect
> > > any point (x2,y-1) or (x3,y+1) within the region.
>
> > > Regarding your algorithm: What does it do with A = B = 5 and points
> > > {(1,1), (2,2), (3,3), (4,4), (1,4)}. This example shows that you can't
> > > always use a line through (0,0).
>
> > > Dave
>
> > > On Jan 24, 10:15 pm, sankalp srivastava 
> > > wrote:
>
> > > > @
> > > > Dave
> > > > How did you come up with this solution?
> > > > Also Y=floor(B)/2+.5 , X=-A*(B-Y)  or X=-AB +AY or Y=X/A+B . this is
> > > > the equation of a line with slope 1/A and an intercept of B on Y
> > > > axis .I don't quite get this.!!Please elaborate .
> > > > Meanwhile , this is my approach .
>
> > > > The slope of the line wil be between the maximum's of the two points
> > > > i.e in the case of (10,0)..(10,10)...It will be between 0 and 90
> > > > degrees as all the points lie between them . Now we can just binary
> > > > search over this slope checking for the slope values . The slope and
> > > > set cardinality is also a monotonic function , so I guess binary
> > > > search approach will work , but the time taken will be nlog n . Please
> > > > correct me if I'm wrong .
> > > > #include
> > > > struct point
> > > > {
> > > >         int x ;
> > > >         int y ;};
>
> > > > using namespace std ;
> > > > // the given points
> > > > point p[100];
> > > > int main()
> > > > {
> > > >         int n;
> > > >         cin>>n;//number of points
> > > >         for(int i=0;i > > >         {
> > > >                 cin>>p[i].x>>p[i].y;
> > > >         }
> > > >         int high=90;
> > > >         int low=0;
> > > >         int mid;
> > > >         //the line is supposed to start from 0,0
> > > >         while(low<=high)
> > > >         {
> > > >                 mid=(high+low)/2;
> > > >                 if(haspoints(mid)<0)
> > > >                         //upper has less points than below
> > > >                         low=mid+1;
> > > >                 else if(haspoints(mid)>0)
> > > >                         //lower has more points than upper
> > > >                         high=mid-1;
> > > >                 else
> > > >                 {//we found our answer
> > > >                         cout< > > >                         return 0;
> > > >                 }
> > > >         }
> > > >         return 0;
>
> > > > }
>
> > > > On Jan 24, 9:30 am, Dave  wrote:
>
> > > > > Generalizing the pro

[algogeeks] Re: Prime Numbers

[sankalp srivastava]

Use a seive . it's complexity is O(nlog n)
1 million is 1*10^7 , this will run within time limit ... assuming u
optimize ur code enough !!

On Jan 26, 5:48 pm, juver++  wrote:
> Generate primes numbers for the range 1..10^7 using sieve.
> Than apply sieve bigger range using these prime numbers.

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

[algogeeks] Re: Amazon Question

[sankalp srivastava]

I don't seem to understand ur solution .
[quote] For every none leaf node , go to the last node in it's left
subtree and mark the right child of that node as x [\quote]. How are
we going to refer to the right child now ??We have removed it's
reference now !!

It is to be repeated for every node except the non leaf nodes . This
will take O(n*n) time in worst case , say a leftist tree with only
left pointers . root makes n-1 traversals , root's left subtree's root
makes n-2 , and so on.

Go to the largest node in the left subtree .This means go to the left
subtree and keep on going to the right until it becomes null  , in
which case  , you make y->right as x . This means effectively , that y
is the predecessor of x , in the tree . Considering a very good code ,
it may take O(1) space , but you will still need additional pointers.
Take the case below .

1
   2 3
1  1.5   2.5   4

for node 2 , you will go to 1 , which is the successor of 2 , you make
2->right=1  but what about node 1.5 ???
same is the case with node 3 ... 3->right=2.5 . How will we refer to 4
now ??

Now using inorder traversal with a count , I will start at 1->left , 2-
>left = 1 , then 2 ... then 2->right = 1 again . then 1 , and then 1-
>right=3 ...clearly , this will not give us a solution .
A reverse inorder looks just fine to me .

On Jan 26, 3:14 pm, Ritu Garg  wrote:
> @Algoose
>
> I said ..*.For every node x,go to the last node in its left subtree and mark
> the right child of that node as x.*
>
> it is to be repeated for all nodes except leaf nodes.
> to apply this approach ,you need to go down the tree.No parent pointers
> required.
> for every node say x whose left sub tree is not null ,go to the largest node
> in left sub-tree say y.
> Set  y->right = x
> y is the last node to be processed in left sub-tree of x hence x is
> successor of y.
>
>
>
> On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase  wrote:
> > @ritu
> > how would you find a successor without extra space if you dont have a
> > parent pointer ?
> > for Instance from the right most node of left subtree to the parent of left
> > subtree(root) ?
> > @Juver++
> > Internal stack does count as extra space !!
>
> > On Wed, Jan 26, 2011 at 3:02 PM, ritu  wrote:
>
> >> No,no extra space is needed.
> >> Right children which are NULL pointers are replaced with pointer to
> >> successor.
>
> >> On Jan 26, 1:18 pm, nphard nphard  wrote:
> >> > If you convert the given binary tree into right threaded binary tree,
> >> won't
> >> > you be using extra space while doing so? Either the given tree should
> >> > already be right-threaded (or with parent pointers at each node) or
> >> internal
> >> > stack should be allowed for recursion but no extra space usage apart
> >> from
> >> > that.
>
> >> > On Wed, Jan 26, 2011 at 3:04 AM, ritu  wrote:
> >> > > it can be done in O(n) time using right threaded binary tree.
> >> > > 1.Convert the tree to right threaded tree.
> >> > > right threaded tree means every node points to its successor in
> >> > > tree.if right child is not NULL,then it already contains a pointer to
> >> > > its successor Else it needs to filled up as following
> >> > >      a. For every node x,go to the last node in its left subtree and
> >> > > mark the right child of that node as x.
> >> > > It Can be done in O(n) time if tree is a balanced tree.
>
> >> > > 2. Now,Traverse the tree with Inorder Traversal without using
> >> > > additional space(as successor of any node is available O(1) time) and
> >> > > keep track of 5th largest element.
>
> >> > > Regards,
> >> > > Ritu
>
> >> > > On Jan 26, 8:38 am, nphard nphard  wrote:
> >> > > > Theoretically, the internal stack used by recursive functions must
> >> be
> >> > > > considered for space complexity.
>
> >> > > > On Mon, Jan 24, 2011 at 5:40 AM, juver++ 
> >> wrote:
> >> > > > > internal stack != extra space
>
> >> > > > > --
> >> > > > > You received this message because you are subscribed to the Google
> >> > > Groups
> >> > > > > "Algorithm Geeks" group.
> >> > > > > To post to this group, send email to algogeeks@googlegroups.com.
> >> > > > > To unsubscribe from this group, send email to
> >> > > > > algogeeks+unsubscr...@googlegroups.com >> > > > >  .com>
> >>  >>  roups.com>
>
> >> > >  >> > >  roups.com>
> >>  >>  glegroups.com>
>
> >> > > > > .
> >> > > > > For more options, visit this group at
> >> > > > >http://groups.google.com/group/algogeeks?hl=en.
>
> >> > > --
> >> > > You received this message because you are subscribed to the Google
> >> Groups
> >> > > "Algorithm Geeks" group.
> >> > > To post to this group, send email to algogeeks@googlegroups.com.
> >> > > To unsubscribe from this group, send email to
> >> > > algogeeks+unsubscr...@googlegroups.com >> > >  .com>
> >>  >>  roups.com>
>
> >> > > .
> >> > > For more options, visit this group at
> >> > >http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> You received this message because you are subscribed to the Googl

[algogeeks] Re: find a line

[sankalp srivastava]

@dave
In this case , I could just shift my origin to the lowermost point :)

On Jan 25, 10:14 am, Dave  wrote:
> @Sankalp: I wanted a point far enough outside the region that a line
> from any point in the region could not contain any other point in the
> region. There are several implications: 1) if the point is to the left
> of the region, it can't have an integer y coordinate between 0 and B.
> That is where the 0.5 comes from. Second, it seemed reasonable, but
> not necessary, to put Y near the middle of the range [0, B]. Then I
> just solved for an  X that guaranteed that the slope of the line from
> any point in the region to the point (X, Y) had slope m satisfying  -1/
> A < m < 1/A. Then a line through any point (x1,y) could not intersect
> any point (x2,y-1) or (x3,y+1) within the region.
>
> Regarding your algorithm: What does it do with A = B = 5 and points
> {(1,1), (2,2), (3,3), (4,4), (1,4)}. This example shows that you can't
> always use a line through (0,0).
>
> Dave
>
> On Jan 24, 10:15 pm, sankalp srivastava 
> wrote:
>
>
>
> > @
> > Dave
> > How did you come up with this solution?
> > Also Y=floor(B)/2+.5 , X=-A*(B-Y)  or X=-AB +AY or Y=X/A+B . this is
> > the equation of a line with slope 1/A and an intercept of B on Y
> > axis .I don't quite get this.!!Please elaborate .
> > Meanwhile , this is my approach .
>
> > The slope of the line wil be between the maximum's of the two points
> > i.e in the case of (10,0)..(10,10)...It will be between 0 and 90
> > degrees as all the points lie between them . Now we can just binary
> > search over this slope checking for the slope values . The slope and
> > set cardinality is also a monotonic function , so I guess binary
> > search approach will work , but the time taken will be nlog n . Please
> > correct me if I'm wrong .
> > #include
> > struct point
> > {
> >         int x ;
> >         int y ;};
>
> > using namespace std ;
> > // the given points
> > point p[100];
> > int main()
> > {
> >         int n;
> >         cin>>n;//number of points
> >         for(int i=0;i >         {
> >                 cin>>p[i].x>>p[i].y;
> >         }
> >         int high=90;
> >         int low=0;
> >         int mid;
> >         //the line is supposed to start from 0,0
> >         while(low<=high)
> >         {
> >                 mid=(high+low)/2;
> >                 if(haspoints(mid)<0)
> >                         //upper has less points than below
> >                         low=mid+1;
> >                 else if(haspoints(mid)>0)
> >                         //lower has more points than upper
> >                         high=mid-1;
> >                 else
> >                 {//we found our answer
> >                         cout< >                         return 0;
> >                 }
> >         }
> >         return 0;
>
> > }
>
> > On Jan 24, 9:30 am, Dave  wrote:
>
> > > Generalizing the problem, let there be n points (x_i, y_i), where x_i
> > > and y_i are integers with 1 <= x_i <= A and 1 <= y_i <= B. A line
> > > separating the points into two sets of equal cardinality can be found
> > > as follows: Let Y = floor(B/2) + 0.5, and let X = -A * (B - Y). Find
> > > the slopes of the lines from the point (X, Y) to each (x_i, y_i). The
> > > point (X, Y) is constructed so that each of these slopes will be
> > > distinct. Find the median M of these slopes. Then the line
>
> > > y = M(x - X) + Y
>
> > > will separate the points as desired. It will pass through exactly one
> > > of the points if n is odd, and will miss all of the points if n is
> > > even. This is O(n) in time and O(n) in space, where n is the number of
> > > points.
>
> > > Dave
>
> > > On Jan 21, 11:45 pm, Divya Jain  wrote:
>
> > > > assume the region to be (0,0) , (10,0), (0,10), (10,10)
>
> > > > On 22 January 2011 08:33, Dave  wrote:
>
> > > > > @Divya: The coordinates of the points are between 0 and 1 and are
> > > > > integers. That can't be right.
>
> > > > > Dave
>
> > > > > On Jan 21, 1:46 pm, divya  wrote:
> > > > > > Within a 2D space, there is a batch of points(no duplicate) in the
> > > > > > region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide
> > > > > > the region to 2 parts with half points in each .the input will

[algogeeks] Re: Good Maths Question

[sankalp srivastava]

Correct me if I'm wrong

dp[i][j]=how many numbers of length i with the last digit j(int base
10)
dp[0][j]=0
dp[i][0]=dp[i-1][0] , last digit can't be zero otherwise the number
has i-1 digits , not j;

now the recursion to pass from one state to the next

dp[i][j]=dp[i-1][k]+1(for each value of k such that k is less than j ,
from 0 to k)
That is to say , the number of numbers with length i and last digit
j , will be equal to the number of numbers with the last digit k , for
each k less than j .One is added because , we must not have included
the 0 in the last case , but we will include the zero case here . this
one corresponds to zero case .

Finally , the answer will be

dp[n][j]  , 1<=j<=9 , sum up all these and u have the answer
For example for 2 digits
dp[1][1-9]=1 , as nothing preceeds them and as said in the problem ,
one digit numbers are always increasing/decreasing .
next dp[2][1]=dp[1][1](As only 1 is less than  , equal to 1 , the last
digit in this state)
dp[2][2]=dp[1][1]+dp[1][2] =2( 1,2 and 2,2)
Continuing this way , we will get the answer , may be 50  , though i
din code it .

similarly , for 3 digits

Correct me if not!

On Jan 25, 12:06 am, juver++  wrote:
> dp[i][j] - how many numbers of length i and with the last digit j.
> Apply the scheme to increasing and decreasing number, then find ratio.

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

[algogeeks] Re: find a line

[sankalp srivastava]

@
Dave
How did you come up with this solution?
Also Y=floor(B)/2+.5 , X=-A*(B-Y)  or X=-AB +AY or Y=X/A+B . this is
the equation of a line with slope 1/A and an intercept of B on Y
axis .I don't quite get this.!!Please elaborate .
Meanwhile , this is my approach .

The slope of the line wil be between the maximum's of the two points
i.e in the case of (10,0)..(10,10)...It will be between 0 and 90
degrees as all the points lie between them . Now we can just binary
search over this slope checking for the slope values . The slope and
set cardinality is also a monotonic function , so I guess binary
search approach will work , but the time taken will be nlog n . Please
correct me if I'm wrong .
#include
struct point
{
int x ;
int y ;
};
using namespace std ;
// the given points
point p[100];
int main()
{
int n;
cin>>n;//number of points
for(int i=0;i>p[i].x>>p[i].y;
}
int high=90;
int low=0;
int mid;
//the line is supposed to start from 0,0
while(low<=high)
{
mid=(high+low)/2;
if(haspoints(mid)<0)
//upper has less points than below
low=mid+1;
else if(haspoints(mid)>0)
//lower has more points than upper
high=mid-1;
else
{//we found our answer
cout< wrote:
> Generalizing the problem, let there be n points (x_i, y_i), where x_i
> and y_i are integers with 1 <= x_i <= A and 1 <= y_i <= B. A line
> separating the points into two sets of equal cardinality can be found
> as follows: Let Y = floor(B/2) + 0.5, and let X = -A * (B - Y). Find
> the slopes of the lines from the point (X, Y) to each (x_i, y_i). The
> point (X, Y) is constructed so that each of these slopes will be
> distinct. Find the median M of these slopes. Then the line
>
> y = M(x - X) + Y
>
> will separate the points as desired. It will pass through exactly one
> of the points if n is odd, and will miss all of the points if n is
> even. This is O(n) in time and O(n) in space, where n is the number of
> points.
>
> Dave
>
> On Jan 21, 11:45 pm, Divya Jain  wrote:
>
>
>
> > assume the region to be (0,0) , (10,0), (0,10), (10,10)
>
> > On 22 January 2011 08:33, Dave  wrote:
>
> > > @Divya: The coordinates of the points are between 0 and 1 and are
> > > integers. That can't be right.
>
> > > Dave
>
> > > On Jan 21, 1:46 pm, divya  wrote:
> > > > Within a 2D space, there is a batch of points(no duplicate) in the
> > > > region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide
> > > > the region to 2 parts with half points in each .the input will be an
> > > > array of points and the length of the array.
> > > > struct point{
> > > > int x;
> > > > int y;};
>
> > > > input : struct point * points, int length
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com > >  ­.com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.-Hide quoted text -
>
> > - Show quoted text -

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

[algogeeks] Re: find a way

[sankalp srivastava]

@ above
In that case  , it will be a simple dynamic programming based
recursion

assuming the total distance one has to cover is n ;
d[i][j]=minimum number of fuel stations to stop at in order to cross i
stations and with j miles still to go .
dp[n][0]= minimum number of fuel stations to stop at in order cross n
stations and with 0 miles still to go (Assuming the nth stop coincides
with the destination B .In case it does not , we can answer something
like dp[n][p]  , where p is the distance to go from nth stop to A)

The recursion
dp[i][k]= min(dp[i+1][k- distance b/w the ith and (i+1)th fuel
station] , dp[i+1][k- distance +lk]+1)(lk= distance we can cover on
this stop)

base case dp[0][j]=0;(for each j )// we have to cover no more stations
therefore

On Jan 22, 9:40 pm, Divya Jain  wrote:
> if u can take only a certain amount of fuel from a particaular station ie
> station xi can provide li amoutn of fuel.. then wat?
>
> On 22 January 2011 13:46, Terence  wrote:
>
>
>
> > Greedy-Approach.
> > Refueling only when you have to.
>
> > On 2011-1-22 15:59, snehal jain wrote:
>
> >> Suppose you want to travel from city A to city B by car, following a
> >> fixed route. Your car can travel m miles on a full tank of gas, and
> >> you have a map of the n gas stations on the route between A and B that
> >> gives the number of miles between each station.
> >> Design an algorithm to find a way to get from A to B without running
> >> out of gas that minimizes the total number of refueling stops, in O(n)
> >> time.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Extracting random element from a bitset

[sankalp srivastava]

How will one go about extracting a random number from a bitset ?
let's say i have a bitset
1001101000100010001
where 1 denote what numbers are currently present in the set
How can one extract these ones in a random manner .Generating a random
number modulo size of the bitset won't work as it can land upon a zero
value as well and this , in worst case can take O(size of bitset *
genarating pseudo random number ) time which is very costly .
Anybody knows how to do this ?

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

Re: [algogeeks] stack

[sankalp srivastava]

@anurag
I meant the sorting without using any auxiliary data structure .Also  we
have to put the element in the tree and carry out a traversal for every
element we insert in the tree .This takes O(n*logn) time ,
If one can sort the elements using a stack in O(n) time , we better sort
with this method , say "Stack sort"
Moral:-No (comparison based )sorting method exists for which time complexity
is less than O(n*log n)
also , without using any auxialliary data structure , we cannot create all
the permutations of the stack
Refer Donald knuth's TAOCP for more details
On Mon, Jun 14, 2010 at 9:18 AM, Anurag Sharma wrote:

> Why not just pop all elements from stack ( O(n) )  and insert it in a self
> balancing Binary Search Tree (like RB Tree) (O(log(n) ) and then do and
> inorder traversal ( O(n) )and push elements in stack again.
> Time = O(nlog(n) + n)
> Space=O(n) (for storing the tree)
>
> Anurag Sharma
>
>
>
> On Sun, Jun 13, 2010 at 9:25 PM, Jitendra Kushwaha <
> jitendra.th...@gmail.com> wrote:
>
>> Stack can be sorted in O(n^2).
>>
>> @sankalp:
>>  Stack can always be sorted. Why do you think it cant be in some cases ?
>>
>> One can think like insertion sort
>> algo :
>> 1. for i in (1,n)
>>   2. Pop up the top n-1 element and keep nth element in global variable
>> say "hold"
>>   3. while pushing get the position for "hold" and push it there
>>
>> for loop will take O(n) and step 2 will take take O(n) time. So overall
>> O(n^2) complexity
>> Program can be done with recursion using a variable (hence O(1) space).
>> But it will use system stack :)
>>
>>
>> Any comments OR better solution is welcomed??
>>
>> --
>> Regards
>> Jitendra Kushwaha
>> MNNIT, Allahabad
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] c array

[sankalp srivastava]

don't ever use a TC compiler , the most obsolete and mad compiler of all .
Every compiler tries to fix the bug in ur code by some way or the other
using some .Even gcc has a lot of bugs , in the sense it will return an exit
status even if returning a void , but this is on ubuntu and haven't tries
mingW yet . Any

On Sun, Jun 13, 2010 at 1:47 PM, divya jain wrote:

> i use tc
>
>
> On 13 June 2010 13:11, ram  wrote:
>
>> @rohit bro
>>
>> http://www.mingw.org/
>>
>> *MinGW*, a contraction of "Minimalist GNU for Windows", is a port of the
>> GNU Compiler Collection (GCC), and GNU Binutils, for use in the development
>> of native Microsoft Windows applications.
>>
>>
>>
>>
>>
>> *From:* algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] *On
>> Behalf Of *Rohit Saraf
>> *Sent:* 13 June 2010 08:19
>>
>> *To:* algogeeks@googlegroups.com
>> *Subject:* Re: [algogeeks] c array
>>
>>
>>
>> @ram : i guess you have used some longer string and not "strings"
>>
>>
>>
>> btw..  what is Mingw ?
>>
>> gcc/g++ is not mingw, i guess
>>
>>
>> --
>> Rohit Saraf
>> Second Year Undergraduate,
>> Dept. of Computer Science and Engineering
>> IIT Bombay
>> http://www.cse.iitb.ac.in/~rohitfeb14
>>
>> On Sun, Jun 13, 2010 at 8:13 AM, ram  wrote:
>>
>> D:\code\samplecode\main.cpp|5|error: initializer-string for array of chars
>> is too long|
>>
>>
>>
>> I get this error on gcc (Mingw) .
>>
>>
>>
>> Though the array indexing starts from 0.
>>
>> The length specified in char str[7] is always straightforward . in this
>> case char str[7]  . the length of str is seven not eight ;hence the error
>>
>> --
>>
>> ram
>>
>>
>>
>> *From:* algogeeks@googlegroups.com [mailto:algoge...@googlegroups.com] *On
>> Behalf Of *sharad kumar
>> *Sent:* 13 June 2010 07:59
>> *To:* algogeeks@googlegroups.com
>> *Subject:* Re: [algogeeks] c array
>>
>>
>>
>> hey array indexing starts from 0 rite??
>> then y shld u get overflow in first place..
>> s t  r  i n g s \0
>> 0 1 2 3 4 5 6 7
>>
>> On Sat, Jun 12, 2010 at 9:14 PM, divya  wrote:
>>
>> #include
>> int main()
>> {
>>
>> char str[7]="strings";
>> printf("%s\n",str);
>> return 0;
>> }
>>
>> here i m nt getting overflow error whereas if i write stringss instead
>> of strings then there is overflow error.. isnt null stored after s in
>> strings nd 1st case shd also give overflow???
>>
>> --
>>
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>>
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>>
>>
>> --
>> yezhu malai vaasa venkataramana Govinda Govinda
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>> --
>>
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

-- 
You received this message because you are subscribed to the Google Groups 
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit 

Re: [algogeeks] stack

[sankalp srivastava]

it's not always possible to sort a stack in all the cases , consider the
stack 2143 and one tries to sort it feeding the elements in order , we have
now whatever popping technique we use , we cannot have a 1234 kind of
stack in order .The maximum number of permutations we can have with a stack
is 2nCn -2nCn-1 which does not necessarily include the permutated group . In
general , we can pop the elements in a decreasing order in the same order as
they are entered . Try sortin the stack with an input of 4132 .now possible


On Sun, Jun 13, 2010 at 1:57 PM, jaladhi dave wrote:

> what do you mean by sorting elements in stack  ? A stack is a data
> structure in which the relative position of elements depend on their order
> of insertion.
>
> If we sort elements in stack, how does it retain the property of a stack ?
>
> If we really want that property, we will have O(n) rather than O(1) insert
> and maintain two pointers. Stack next and sorted next.
>
>
> On Sun, Jun 13, 2010 at 1:05 PM, jalaj jaiswal 
> wrote:
>
>> how to sort elements of stack using constant space
>>
>> --
>> With Regards,
>>
>> +919026283397
>> B.TECH IT
>> IIIT ALLAHABAD
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] nibbles

[sankalp srivastava]

this can be done using the same code as of Sharad above , the only
difference being the mask bits , we mask  four bits of a nibble by the
anding with 0001 , 0010 , 0101 and 1000 .. now , we feed these into the
given number .I mean all the bits as below ..
Suppose we have a nibble as 1100 and we want it to be 0011 , so after
masking , we have the four bits as 1000 , 0100 ,  and  respectively
.We feed the given bits in a reverse order into a nibble (or a character for
that matter ) in a reverse order .
So first bit(1000) is shifted right 3 times and added to result , second
shifted 1 times and added , third shifted 1 time but to the left and fourth
3 times to the left . we add all of the to have the answer  .

On Sun, Jun 13, 2010 at 1:56 PM, jalaj jaiswal wrote:

> can any one explain it using an example...
> let say my nibble is 0100... i have to print 0010... in one go using
> bitwise operators...
> please explain through example
>
> @ sharad ... your code is to swap two nibbles in a character
>
>
> On Sun, Jun 13, 2010 at 1:39 PM, jaladhi dave wrote:
>
>> Write a c-macro to use assembly swap opcode.
>>
>> On Sat, Jun 12, 2010 at 9:35 PM, jalaj jaiswal > > wrote:
>>
>>>
>>> write an algorithm to reverse a nibble in one pass...using bitwise
>>> operators
>>> --
>>> With Regards,
>>> Jalaj Jaiswal
>>> +919026283397
>>> B.TECH IT
>>> IIIT ALLAHABAD
>>>
>>> --
>>> You received this message because you are subscribed to the Google Groups
>>> "Algorithm Geeks" group.
>>> To post to this group, send email to algoge...@googlegroups.com.
>>> To unsubscribe from this group, send email to
>>> algogeeks+unsubscr...@googlegroups.com
>>> .
>>> For more options, visit this group at
>>> http://groups.google.com/group/algogeeks?hl=en.
>>>
>>
>>  --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>
>
>
> --
> With Regards,
> Jalaj Jaiswal
> +919026283397
> B.TECH IT
> IIIT ALLAHABAD
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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

Re: [algogeeks] The Mystery Spiral

[sankalp srivastava]

all of these are with the unstandarized conio library ..use curses or
ncurses instead or tput system call

On Wed, Apr 28, 2010 at 8:45 AM, Chinmay S  wrote:

> Yes there definitely is a fine distinctions between the two cases you
> mention.
>
> The program above fills the N*N numbers in spiral in decreasing order and
> then prints the matrix contents left to right , top to bottom.
>
> For the second program (that also prints in spiral order):
>
> http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral-part2/
>
> GoodLUCK!!
>
>  --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>

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