[algogeeks] Re: Largest rectangle in a binary matrix

[Modeling Expert]

this is asnwered here
http://groups.google.com/group/algogeeks/browse_thread/thread/84b94e7527805334/fb1378d5744e0208?lnk=gst&q=rectangle+binary+matrix#fb1378d5744e0208


On Dec 8, 7:29 pm, Aditya Agrawal  wrote:
> ravi is right ..http://alexeigor.wikidot.com/kadane
>
> On Wed, Dec 8, 2010 at 7:31 PM, Prims  wrote:
> > Hello Gobind
>
> > The link contains the solution for finding the largest square in a
> > binary matrix which is not valid in case of largest rectangle.
>
> > -Prims
>
> > On Dec 8, 6:38 pm, GOBIND KUMAR  wrote:
> > > Hi,
> > >     Solution is available athttp://geeksforgeeks.org/?p=6257
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: binary matrix

[Modeling Expert]

2 things
1.  There was a small type in end where I said Time complexity :O ( 2
* m * n )  , actually its space complexity.
Time complexity is  O ( m * n^2 )

2. I got some requests to explain this with an example so I solved
this for a matrix which is as following
 0  1  1  0  1
  1  1  0  1  0
  0  1  1  1  0
  1  1  1  1  0
  1  1  1  1  1
  0  0  0  0  0

I have uploaded solution at
http://groups.google.com/group/algogeeks/web/binaryMatrix_Rectangle.pdf

plz review .

-Manish



On Nov 2, 9:02 am, Ankit Babbar  wrote:
> @Modeling Expert:  Can you please explain your algo with an example...
>
> especially calculating the area of rectangles using min depth and its
> traversal through the matrix...
>
> On Tue, Oct 5, 2010 at 7:24 PM, Modeling Expert 
>
>
> > wrote:
> > For square matrix , link suggested by Amit would work. Finding a sub-
> > rectangle is tougher.
>
> > I would go this way; First scan from bottom right till top left and
> > for every Non-zero member in matrix create this pair ( width ,
> > depth ).
>
> > Width is  how many continuous 1's ( including itself ) are there to
> > its right,
> > Depth is  how many continuous 1's ( including itself ) are there down
> > wards
>
> > now select a point P(i,j) , which has value Pair ( W , D ) it means
> > W-1 columns to right and D-1 rows below are '1' , Note: it doesn't
> > give any info about diagonal
> >                                    entries to P , and we will see ,
> > we actually don't need them.
>
> >  Now think about all possible rectangles which could be made when P is
> > left top corner
> >  so go columnwise from i to  i + 1 , i +2 ,  i + (W-1) points ( call
> > it P' point ) , at every step, see the minimum depth for all points
> > between P and P' and keep calculating area by width X minDepth
>
> >  e.g. P has width = 3, depth = 4 and co-ordinates (i,j ) then go like
> > this
> > Area for A[i,j] and  P'[i, j+1 ]  = 2 X MinDepth( P, P')   //A1
> > Area for A[i,j] and  P"[i, j+2 ]  = 3 X MinDepth( P, P', P")   //A2  :
> > Note MinDepth is Minimum Depth of all three points so far
> >  Take Max of A1,A2 and you would have max rectangle which could be
> > created by having P as top left corner.
>
> > Now , keep traveling P throughout this Matrix.
>
> > There are few optimisation. A point with width W and depth D can AT
> > MAX has a rectangle with AREA MAX = W * D so next time consider points
> > only whose W * D > Max Area calcuated so far.E.g if you have already
> > got a point which has sub rectangle with area = 12 no need to look for
> > points which has such (W,D) pairs = ( 2,3) , (4,2) , (3,3)  etc .
>
> > Time complextiy :
> > First time reverse traversal O(m * n )  /// m Rows , n Columns
> >   Second time , MAX AREA calculation for each points , worse case
> > o(n) as we need to travel only column wise as explained above
> >   Above action to be done for m*n points so total O( mn * n ) =
> > O(mn^2)
>
> > So total Time = O ( m * n^2 )
>
> > Time complexity :O ( 2 * m * n ) as W and D pair for each entry has to
> > be maintained
>
> > Suggestions, Clarifications, Modifications ?
> > -Manish
>
> > --
> > 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.
>
> --
> Regards,
> Ankit Babbar

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

[algogeeks] Re: Implement a phone book.

[Modeling Expert]

Create two trees , one for numbers another for name .  You can search
in respective tree for name or number based search.
You can also search by prefix , all leaf nodes from the prefix-node
would give you all matches.

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

[algogeeks] Re: binary matrix

[Modeling Expert]

For square matrix , link suggested by Amit would work. Finding a sub-
rectangle is tougher.

I would go this way; First scan from bottom right till top left and
for every Non-zero member in matrix create this pair ( width ,
depth ).

Width is  how many continuous 1's ( including itself ) are there to
its right,
Depth is  how many continuous 1's ( including itself ) are there down
wards

now select a point P(i,j) , which has value Pair ( W , D ) it means
W-1 columns to right and D-1 rows below are '1' , Note: it doesn't
give any info about diagonal
entries to P , and we will see ,
we actually don't need them.

 Now think about all possible rectangles which could be made when P is
left top corner
 so go columnwise from i to  i + 1 , i +2 ,  i + (W-1) points ( call
it P' point ) , at every step, see the minimum depth for all points
between P and P' and keep calculating area by width X minDepth

 e.g. P has width = 3, depth = 4 and co-ordinates (i,j ) then go like
this
Area for A[i,j] and  P'[i, j+1 ]  = 2 X MinDepth( P, P')   //A1
Area for A[i,j] and  P"[i, j+2 ]  = 3 X MinDepth( P, P', P")   //A2  :
Note MinDepth is Minimum Depth of all three points so far
  Take Max of A1,A2 and you would have max rectangle which could be
created by having P as top left corner.

Now , keep traveling P throughout this Matrix.

There are few optimisation. A point with width W and depth D can AT
MAX has a rectangle with AREA MAX = W * D so next time consider points
only whose W * D > Max Area calcuated so far.E.g if you have already
got a point which has sub rectangle with area = 12 no need to look for
points which has such (W,D) pairs = ( 2,3) , (4,2) , (3,3)  etc .

Time complextiy :
First time reverse traversal O(m * n )  /// m Rows , n Columns
   Second time , MAX AREA calculation for each points , worse case
o(n) as we need to travel only column wise as explained above
   Above action to be done for m*n points so total O( mn * n ) =
O(mn^2)

So total Time = O ( m * n^2 )

Time complexity :O ( 2 * m * n ) as W and D pair for each entry has to
be maintained


Suggestions, Clarifications, Modifications ?
-Manish







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

[algogeeks] Re: Design an algorithm

[Modeling Expert]

use array/vector of int to store value. E.g.
if you want to store value : 23451023456678, you can't in a normal int
or long
but You can have int array /vector , say "int  A[SIZE] "  or "
vector A(SIZE,0)
A[0]  78
A[1]   66
A[2]   45
..
..

I have coded this long back to calculate factorial of big numbers
if I use Array  SIZE = 10K , I can find max factorial of 3249 ( 10,000
digits )

for 1! , I tried with  Array  SIZE = 100K , I got answer which has
'35659' digits !

Let me know if my hint make sense.

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

[algogeeks] Re: apple problem

[Modeling Expert]

recurssion...

At any point X

val_t  getMax( position X){

( ! End of Table )
sum =  GetApples[X] +  MAX ( getMax(X_down) , getMax
( X_right) ) ;

returnn sum ;
}

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

[algogeeks] Re: do this: two numbers with min diff

[Modeling Expert]

Trying to put down a method, I think would work ( with a small running
example )

//! Assuming non--negative numbers and difference is MOD of difference
of numbers

Let array be A[1..n]//! e.g.  { 11 , 6 , 17 , 9 ]
Start with pari ( A[1], A[2] ) and difference be D = | A[1] - A[2]
|/// A[1] = 11 , A[2] = 6  , D = 5

   Now take A[3] , see if it lies b/w A[1] and A[2] //!  A[3] = 17 ,
is it b/w { 11, 6} => NO
   if NO , continue
   else
   check where left or right member of pair is closer to
it   //! pair = (11,6) , next num = 9
   new pair = (Left,A[3])  OR ( A[3],
right )//! new pair = (11,9)

Time : O(n) as we are traveling array once
Space Coplexity : O(1) just need to store pair of numbers..


Thoughts ?
-Manish

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

[algogeeks] Re: Arrays

[Modeling Expert]

no need to addi all element if overflow is feared , subtract values
for given index in the loop
something like this
   result = 0 ;
   for(count = 0; count < n ;count ++){
  result  += (B[count]-A[count]);
   }
   result += B[count] ; //! this is the answer...

-Manish


On Sep 21, 9:44 am, Baljeet Kumar  wrote:
> There can be overflow in case of adding up all the elements. Use Xor
> instead.
>
>
>
>
>
> > int result = 0;
> > for (int i = 0; i < n ;i++){
> >       result ^= A[i]^B[i];
> > }
>
> > result ^= B[n]; <=== (correction)
> > result is the number we need.
>
> > On Tue, Sep 21, 2010 at 9:48 AM, vishal raja wrote:
>
> >> add up all the elements in array A  say sumA and array B say sumB
> >> ,substract the sumA from sumB... You'll get the element.
>
> >> On Tue, Sep 21, 2010 at 5:36 AM, Anand  wrote:
>
> >>> Two unsorted arrays are given A[n] and B[n+1]. Array A contains n
> >>> integers and B contains n+1 integers of which n are same as in array B but
> >>> in different order and one extra element x. Write an optimized algorithm 
> >>> to
> >>> find the value of element x. Use only one pass of both arrays A and B.
>
> >>> --
> >>> 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.
>
> > --
> > Baljeet Kumar
>
> --
> Baljeet Kumar

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

[algogeeks] Re: Amazon: sort array

[Modeling Expert]

@Anand , thanx for info , but does the question asked requires so
much ?
I felt , you have two sorted sub arrays so simply merging it (of merge
sort fame ! ) would solve it , isn't it ?

On Jul 3, 9:24 am, ankur bhardwaj  wrote:
> @anand: this code will not work when n is not power of 2.
>
> check for this example:
>
> {2, 4, 55, 25, 15}
>
> Output was:
>
> 0 4
> 0 2
> 1 3
> 0 1
> 2 3
> 2 4 25 55 15 0 0 0
> ascending order

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

[algogeeks] Re: Call a function before main() in C

[Modeling Expert]

Can some one explain in detail why this program behaves the way it
does. I mean , static/const objects would have been allocated space in
data segment at compile time , then why constructor is getting called
during run before main ? What goes in background for this ?

-Manish



On Jun 30, 1:00 am, Varma  wrote:
> Hi All,
> Is there any way to call our function before main() is called ?
>
> I know there is a way in C++  as below , but Is there a standard way
> in C ?
>
> #include 
> class CStatic
> {
>public:
>CStatic() { cout << "Before Main!" << endl; }
>~CStatic() { cout << "After Main!" << endl; }
>
> };
>
> CStatic cs;
> int main()
> {
>cout << "Begin Main" << endl;
>cout << "Doing something" << endl;
>cout << "End Main" << endl;
>
> }

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

[algogeeks] Re: unique number in an array

[Modeling Expert]

use hash table , and if you find for a number , a entry already
exists , mark it unwanted !
in the end , hash table entries are unique numbers .

@kunzmilan : could you explain a bit more, couldn't get full idea of
what you wrote

-Manish

On Jun 14, 1:19 pm, kunzmilan  wrote:
> Write the array as a vector string S, eg
> (1,0,0,0...)
> (0,0,1,0...)
> (0,0,0,1...)
> etc.
> Find the quadratic form S^T.S. On its diagonal, occurences of all
> numbers are counted.
> kunzmilan
>
> On 13 čvn, 20:44, jalaj jaiswal  wrote:
>
> > give an algo to find a unique number in an array
>
> > for eg a[]={1,3,4,1,4,5,6,1,5}
>
> > here 3 is the unique number as it occur only once... moreover array contains
> > only 1 unique number
>
> > --
> > 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.

[algogeeks] Re: file handing

[Modeling Expert]

@Divya
For (3) : You are getting last line twice because of wrong usage of
feof(fp). Remember , feof() returns true after EOF file is reached and
not when EOF is read.
feof tells you end of file is reached and it can tell that only after
reading EOF and not while reading it !!
So after last line is printed , feof(fp) is still false, and then
program tries to read from file where it fails ( but no one checks
there if fgets(...) fails ) and program prints the old value (i.e.
last line ) . You can cross check this by making str null after every
print and you would see its not last line but the last value stored by
'str' which is printed. You should ideally do !feof(fp) after fgets()
OR use fgets() to check file end by " feof() != NULL OR similar
way.

Hope it helps.




On Jun 13, 8:57 pm, jalaj jaiswal  wrote:
> declaration of fclose in stdio.h is as fclose (FILE*);
> so it has too many arguments...
> On Sun, Jun 13, 2010 at 9:06 PM, divya jain wrote:
>
>
>
> > sorry i pasted wrong questn unser 2..
>
> > the real question is
>
> > which file will get closed through fclose()
> > #include
> > int main()
> > {
> > FILE *fp,*fs,*ft;
> > fp=fopen("a.c","r");
> > fs=fopen("b.c","r");
> > ft=fopen("c.c","r");
> > fclose(fp,fs,ft);
> > return 0;
> > }
>
> > 3. yes it is feof..srry typed it wrong... nd fgets(str,80,fp) is perfectly
> > fine.. now the ans to this questn is that last line of the file will be
> > printed twice...( which i m unable to get why)...plzz explain...
>
> > @ souravsain plzz ignore this mail..srry for the inconvenience..
>
> > On 13 June 2010 17:37, jalaj jaiswal  wrote:
>
> >> in question 1... ch gets the value of EOF... so first kicit 44-a
> >> gokulpeth\0 nagpur will get printed and then the value of EOF..
>
> >>  question number 2 .. seems to me as nrml ...i think myfile.c only gets
> >> closed
>
> >> in question number 3..it shld be fgets(str,79,fp)
>
> >> On Sun, Jun 13, 2010 at 2:49 PM, divya  wrote:
>
> >>> 1. wat ll be the o/p. plz explain y?
> >>> // abc.c contains "kicit 44-a gokulpeth\0 nagpur"
> >>> #include
> >>>  #include
> >>>  int main()
> >>>  {
> >>>  unsigned char ch;
> >>>  FILE *fp;
> >>>  fp=fopen("abc.c","r");
> >>>  if(fp==NULL)
> >>>  {
> >>>  printf("unable to open the file \n");
> >>>  exit(1);
> >>>  }
> >>>  while((ch=getc(fp))!=EOF)
> >>>  printf("%c",ch);
> >>>  fclose(fp);
> >>>  printf("\n",ch);
> >>>  return 0;
> >>>  }
>
> >>>  2.which file will get closed through fclose() in the following
> >>> program and why?
> >>> #include
> >>>          int main()
> >>>  {FILE *fp;
> >>>  char ch;
> >>>  int i=1;
> >>>  fp=fopen(myfile.c","r");
> >>>          while((ch=getc(fp)!=EOF))
> >>>          {
> >>>                  if(ch=='\n')
> >>>                          i++;
> >>>          }
>
> >>>          fclose(fp);
> >>>          return 0;
> >>>  }
>
> >>>  3.point out the error if any in following
>
> >>> #include
> >>>          int main()
> >>>  {
> >>>          FILE *fp;
> >>>          char str[80];
> >>>          fp=fopen("trial","r");
> >>>          while(!eof(fp))
> >>>          {
> >>>                  fgets(str,80,fp);
> >>>                  puts(str);
> >>>          }
> >>>          fclose(fp);
> >>>          return 0;
> >>>  }
>
> >>> --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to 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.
>
> --
> 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.

[algogeeks] Re: bits

[Modeling Expert]

@jalaj

Yes , this is endian ness specific. On windows/x86 linux which are
little endian, ch[0] would be lower 8 bits. On solaris/power pc which
are big endian this would be upper 8 bits. e.g.
union a temp;
temp.i = 0x12345678   //! here big end is 0x12 and little end is 0x78
then temp.ch[0] = 78 //! Little end first for little endian

and temp.ch[0] = 0x12 for big endian



On Jun 13, 9:18 pm, jalaj jaiswal  wrote:
> hey i too have a doubt... and its just 1 ... i'll not ask c/c++ again,,,
>
> we have a union a{
>                        int i;
>                        char ch[4];
>                 }
> int here is of 4 bytes.
> i initialise i=512...
> what value will ch[0] get the upper 8 bits or the lower 8 bits... is it big
> endian or little endian dependent... please explain this ??
>
> On Sun, Jun 13, 2010 at 9:43 PM, Rohit Saraf 
> wrote:
>
>
>
> > I agree mass bombarding with such questions is not very good.. but one
> > doesn't join groups and all for getting a few doubts cleared.
> > Anyways, i have no problem with anything. :D
>
> > --
> > 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 9:26 PM, souravsain  wrote:
>
> >> and @rohit you will get better insight into the topic by more expert
> >> people by posting the question in right forum. I guess thats a win-win
> >> situation for one who has the question as he is get to know more and
> >> for people you are interested in going through C++ questions as they
> >> will read views from many more experts :)
>
> >> On Jun 13, 7:31 pm, Rohit Saraf  wrote:
> >> > @Souravsain : Is there any serious problem in this. Anyone can just add
> >> a
> >> > [C++] in the subject and uninterested people can make filters in gmail
> >> :)
>
> >> > --
> >> > Rohit Saraf
> >> > Second Year Undergraduate,
> >> > Dept. of Computer Science and Engineering
> >> > IIT 
> >> > Bombayhttp://www.cse.iitb.ac.in/~rohitfeb14
>
> >> > On Sun, Jun 13, 2010 at 6:35 PM, souravsain 
> >> wrote:
> >> > > @divya
>
> >> > > Lets keep discussions in t his group limited to Algos and problems
> >> > > neutral to any language.
>
> >> > > Request you to post these C++ / C language specific questions to those
> >> > > language specific groups. This will not only help this group remain
> >> > > confined to its core purpose but will help you get better insights to
> >> > > ur problem by language specific geeks there. For C++ I would recommend
> >> > > you to try the group
> >> > >http://groups.google.co.in/group/comp.lang.c++.moderated/topics?hl=en.
>
> >> > > Regards,
> >> > > Sourav
>
> >> > > On Jun 13, 2:29 pm, divya  wrote:
> >> > > > tell the o/p of following with explanations
>
> >> > > > 1. #include
> >> > > > int main()
> >> > > > {
> >> > > >   struct value
> >> > > > {
> >> > > > int bit1:1;
> >> > > > int bit3:4;
> >> > > > int bit4:4;
>
> >> > > > }bit;
>
> >> > > > printf("%d\n",sizeof(bit));
> >> > > > return 0;
>
> >> > > > }
>
> >> > > > 2.
> >> > > > #include
> >> > > > int main()
> >> > > > {
> >> > > > struct value
> >> > > > {
> >> > > > int bit1: 1;
> >> > > > int bit3: 4;
> >> > > > int bit4: 4;} bit={1,2,2};
>
> >> > > > printf("%d %d %d\n",bit.bit1,bit.bit3,bit.bit4);
> >> > > > return 0;
>
> >> > > > }
>
> >> > > > 3 can bit field be used in union??
>
> >> > > --
> >> > > 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.-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 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 thi

[algogeeks] Re: Print large Fibonacci numbers

[Modeling Expert]

you can also use http://gmplib.org/
-Manish

On Jun 11, 10:12 pm, Raj N  wrote:
> Ya thanks !!
>
> On Fri, Jun 11, 2010 at 10:31 PM, Rohit Saraf
> wrote:
>
> > Fibonacci numbers can be calculated very efficiently
> > using matrix multiplications.
>
> > I hope you can think it/google it now.. that is better  than me writing so
> > much again :)
>
> > --
> > Rohit Saraf
> > Second Year Undergraduate,
> > Dept. of Computer Science and Engineering
> > IIT Bombay
> >http://www.cse.iitb.ac.in/~rohitfeb14
>
> > On Fri, Jun 11, 2010 at 8:12 PM, Raj N  wrote:
>
> >> How to print very large Fibonacci numbers eg fib(1000).
> >> My approach:
> >> When any one of fib(i-1) or fib(i-2) has more than 12 or 13 digits,
> >> partition them into groups of 4 digits and put them in a linked list.
> >> fib(i-1) is put in list1, fib(i-2) in list2. Perform the addition of
> >> these long numbers and overwrite in list2.
> >> Now to find next fib list1 is taken as fib(i-2) and list2 as fib(i-1)
> >> and this repeats until we approach the given number and finally the
> >> result is in list2.
> >> As the number of digits goes on increasing, the list is constructed
> >> dynamically.
>
> >> If anyone has an efficient approach pls tell me.
>
> >> --
> >> 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.

[algogeeks] Re: Array Problem

[Modeling Expert]

@sourav : if I understood problem correctly , you can't change the
list ( hence you can't sort ).
and list can containt + . - ive ints .
e.g. say list is

 7 9 1 -4 8 0 0 0 3 1 0

Here answer is index(0) - index(-4) = 11

@divya : didn't get what you said , but guess you also thought of
sorting array .

Correct me if I am wrong here.
-Manish

On Jun 12, 2:48 pm, divya jain  wrote:
> i think we need to maintain an array of index as well such that while
> subtracting smallest element from largest element of sorted array we need to
> check if index of largest is greater than index of smallest. if no..then
> this is not the solution..
>
> On 12 June 2010 14:20, Modeling Expert  wrote:
>
> > Let's say array A , 1 till n
>
> > s_index = 1;  e_index = n ;
> > start  = &A[s_index] ;
> > end = &A[e_index];
> > result = 0;                  //!  j - i
> > if ( *end > *start ){
> >    result =  index(end) - index(start)  ( only of its greater than
> > previous value of result )
> >    break ;
> > }else{
> >     end-- ;  //! till you reach start
> > }
>
> > now increment start , and repeat the process but only from A[n] till
> > A[++result] , going further
> > down is not required now.
>
> > Average time < o(n^2)
>
> > Worst case : let's say we have descending array of ints, theno(n^2)
>
> > Please suggest improvements
>
> > On Jun 12, 12:14 am, amit  wrote:
> > > given an array A of n elements.
> > > for indexes j , i such that j>i
> > > maximize( j - i )
> > > such that A[j] - A [ i ]> 0 .
>
> > > Any Algorithm less than O(n^2) would do.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: sum to x

[Modeling Expert]

My previous post went unfinished :((
anyway this is summary of algo . (as N is very large , sorting could
be costly so this method doesn't do that )

algo ::
have a map

1. For given number , if its less than Sum S , make map[S-number] =
true  only if map[number] does not exist
2. for Next  number , if map[number] is true , we got a pair
( number , map[number]) else do 1

For exampe S = 100 , if we get 20 , let's make map[80] = true ;
next if we get 80 , we will first check map[80] and if its true , we
get a pair.

If there are repetations , we can take map of  where second
argument is count of first element ,
say of 20 comes 4 times we will store map[20] = 4




On Jun 12, 11:40 am, Chakravarthi Muppalla 
wrote:
> I would use an array.
>
> a[] = 1 3 7 8 9 78 67 23
> a[] = 1 3 7 8 9 23 67 78 //sort the array
> reqSum = 30;
> for i :a.length-1; i>=0; i--
>      t = reqSum - a[i];
>      if(t is negative) continue;
>       find(t);//in the rest of the array;(binary search)
>       if(t found in the array) return index of t, current value of i;
>  I guess it works.(we may have to use a hash map to speed it up in the long
> run).
>
> On Sat, Jun 12, 2010 at 10:29 AM, Rohit Saraf
> wrote:
>
>
>
> > I guess it can be done in efficiently using a simple divide and conquer
> > scheme almost imitating mergesort.
> > Can you think of it now? :D
>
> > --
> > Rohit Saraf
> > Second Year Undergraduate,
> > Dept. of Computer Science and Engineering
> > IIT Bombay
> >http://www.cse.iitb.ac.in/~rohitfeb14
>
> > On Fri, Jun 11, 2010 at 10:07 PM, sharad kumar 
> > wrote:
>
> >> all possible pairs
>
> >> --
> >> 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.
>
> --
> Thanks,
> Chakravarthi.

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

[algogeeks] Re: Array Problem

[Modeling Expert]

Let's say array A , 1 till n

s_index = 1;  e_index = n ;
start  = &A[s_index] ;
end = &A[e_index];
result = 0;  //!  j - i
if ( *end > *start ){
result =  index(end) - index(start)  ( only of its greater than
previous value of result )
break ;
}else{
 end-- ;  //! till you reach start
}

now increment start , and repeat the process but only from A[n] till
A[++result] , going further
down is not required now.

Average time < o(n^2)

Worst case : let's say we have descending array of ints, theno(n^2)

Please suggest improvements










On Jun 12, 12:14 am, amit  wrote:
> given an array A of n elements.
> for indexes j , i such that j>i
> maximize( j - i )
> such that A[j] - A [ i ]> 0 .
>
> Any Algorithm less than O(n^2) would do.

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

[algogeeks] Re: sum to x

[Modeling Expert]

As problem says N is very large, I think sorting is not the right
thing as that would be minimum (n log n) time
how about this
Let's say sum is S
we take an map map and start reading integerts num
if ( num > S ) discard
else {
   if ( && map[num] == false){
  map[ S - num ] = true ;
   } else {

}


On Jun 12, 11:40 am, Chakravarthi Muppalla 
wrote:
> I would use an array.
>
> a[] = 1 3 7 8 9 78 67 23
> a[] = 1 3 7 8 9 23 67 78 //sort the array
> reqSum = 30;
> for i :a.length-1; i>=0; i--
>      t = reqSum - a[i];
>      if(t is negative) continue;
>       find(t);//in the rest of the array;(binary search)
>       if(t found in the array) return index of t, current value of i;
>  I guess it works.(we may have to use a hash map to speed it up in the long
> run).
>
> On Sat, Jun 12, 2010 at 10:29 AM, Rohit Saraf
> wrote:
>
>
>
> > I guess it can be done in efficiently using a simple divide and conquer
> > scheme almost imitating mergesort.
> > Can you think of it now? :D
>
> > --
> > Rohit Saraf
> > Second Year Undergraduate,
> > Dept. of Computer Science and Engineering
> > IIT Bombay
> >http://www.cse.iitb.ac.in/~rohitfeb14
>
> > On Fri, Jun 11, 2010 at 10:07 PM, sharad kumar 
> > wrote:
>
> >> all possible pairs
>
> >> --
> >> 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.
>
> --
> Thanks,
> Chakravarthi.

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

[algogeeks] templates overloading

[Modeling Expert]

If we have templatized functions , return type becomes part of
function signature ( which is not the case when we have normal non-
templatized functions ) , So we can have two functions like these who
differ only in return type

template int foo(T)
{ cout << " this " ; }

template bool foo(T)
{ cout << " that " ; }

Questions is how do I call these functions. If I do like these
int k = foo(12) ; it cribbs that this call is ambiguos. How do we
avoid this ambiguity  ??

On googling it I could find one cast which solves this , but I could
not understand it fully
((int(*)(char))foo)('a');

Can some one explain in simple terms.

-Manish

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

[algogeeks] Re: string question

[Modeling Expert]

I would make two routines,
first which would give me substrings of string ( similar to strtok )
Then I would either use finite state automata while searching reverse
way , that should work ?

About window solution , I am getting few ideas but not sure how would
I differentiate for 'eo' to get correcet results in case of
"eeo"  and  "eoo"  though with FS automata I don't see this issue.

thoughts ?



On May 17, 4:52 pm, divya jain  wrote:
> the output shd be epo..
>
> hint to the problem :   PROBLEM DO NOT READ IF U WANT TO SOLVE THE URSELF
> it involves the concept of finding window
> u hv to 1st search for the window which contains all characters of string.
> then u have to alter window so as to get minmum length window..
>
> On 17 May 2010 16:44, Modeling Expert  wrote:
>
>
>
> > @Divya
> > BigS =" Hellepo What's up"
> > SmallS = 'eo'
> > o/p should be ?  "ellepo" OR "epo" ?
>
> > if its "ellepo" DP would work fine . If its "eo" probably need some
> > modification in DP.
>
> > -Manish
>
> > On May 16, 8:36 pm, Navin Naidu  wrote:
> > > @Sharad: yup
>
> > > On Sun, May 16, 2010 at 8:36 PM, Rohit Saraf <
> > rohit.kumar.sa...@gmail.com>wrote:
>
> > > > @Navin: and that works ! :)
> > > > @all : i am sure no heuristic/greedy strategy can be applied.
> > > > @divya : did you check your array partitioning algorithm with my
> > example !
>
> > > > --
> > > > Rohit Saraf
> > > > Second Year Undergraduate,
> > > > Dept. of Computer Science and Engineering
> > > > IIT Bombay
> > > >http://www.cse.iitb.ac.in/~rohitfeb14<http://www.cse.iitb.ac.in/%7Erohitfeb14>
> > <http://www.cse.iitb.ac.in/%7Erohitfeb14>
>
> > > >  --
> > > > 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.
>
> > > --
> > > Thanks & Regards,
>
> > > - NMN
>
> > > --
> > > 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 athttp://
> > 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 
> athttp://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: k the smallest in BST without using static variable

[Modeling Expert]

@kaushik where are you creating explicit stack ? It has to be outside
inorder(Root) , right ?
If yes , then you can use only a count and that should work .  Make
kth bit of count = 1 , rest all 0.
Just  before printing in Inorder , right shift count and when it
becomes ZERO , that's the value you are looking for.

If no  , please explain bit more in detail about it.

On May 16, 9:44 am, satwik krishna  wrote:
> @Rohit
> Can u pass on thje link of morris inorder
>
> On 5/15/10, Rohit Saraf  wrote:
>
>
>
>
>
> > there  is something called morris inorder traversal.
> > credits to donald knuth
>
> > On 5/15/10, kaushik sur  wrote:
> > > Hi Friends
>
> > > I have encountered the question in sites - "Given a Binary Search
> > > Tree, write a program to print the kth smallest element without using
> > > any static/global variable. You can't pass the value k to any function
> > > also."
>
> > > I have tried my hands using  explicit stack for inorder and keeping a
> > > non-static count variable.
>
> > > I welcome any better solution, time and space efficient.
>
> > > Best Regards
> > > Kaushik Sur
>
> > > --
> > > 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.
>
> > --
> > --
> > Rohit Saraf
> > Second Year Undergraduate,
> > Dept. of Computer Science and Engineering
> > IIT Bombay
> >http://www.cse.iitb.ac.in/~rohitfeb14
>
> > --
> > 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 
> athttp://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: string question

[Modeling Expert]

@Divya
BigS =" Hellepo What's up"
SmallS = 'eo'
o/p should be ?  "ellepo" OR "epo" ?

if its "ellepo" DP would work fine . If its "eo" probably need some
modification in DP.

-Manish


On May 16, 8:36 pm, Navin Naidu  wrote:
> @Sharad: yup
>
> On Sun, May 16, 2010 at 8:36 PM, Rohit Saraf 
> wrote:
>
>
>
> > @Navin: and that works ! :)
> > @all : i am sure no heuristic/greedy strategy can be applied.
> > @divya : did you check your array partitioning algorithm with my example !
>
> > --
> > Rohit Saraf
> > Second Year Undergraduate,
> > Dept. of Computer Science and Engineering
> > IIT Bombay
> >http://www.cse.iitb.ac.in/~rohitfeb14
>
> >  --
> > 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.
>
> --
> Thanks & Regards,
>
> - NMN
>
> --
> 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 
> athttp://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: BST

[Modeling Expert]

sorry , there was a typo
'Have two array" read it as "Have two pointers"

-Manish


On May 16, 1:04 pm, Modeling Expert 
wrote:
> @Divya I think your solution is correct. To do in constant time , we
> can use BST itself instead of storing in array.
> Have two array , make first point to left most , make second point to
> right most member, now start your algorithm while making
> these two pointers move. Left pointer should move in 'inorder' style
> while right pointer should move in 'reverse inorder style'
> if ( *LeftPtr + * RightPtr > k ) Decrement ( RightPtr)
> if ( *LeftPtr + * RightPtr < k ) Increment (LeftPtr)
> else WeHaveAnswer
>
> -Manish
>
> On May 15, 6:49 am, Yalla Sridhar  wrote:
>
>
>
> > if the tree has parent pointer then we can apply similar approach,,
> > increment and decrenent... and can also be done in O(1)
>
> > have to poninters pointed to the min and max nodes and them move pointers by
> > checking the sums..
>
> > On Fri, May 14, 2010 at 5:03 PM, anna thomas  wrote:
> > > @rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
> > > req sum, increment the 1st ptr(ptr at beginning of array). If sum > req 
> > > sum,
> > > then decrement the 2nd ptr(ptr at end of array)
> > > In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum > 6)
> > > dec ptr2 1+4 = 5 (sum < 6)
> > > inc ptr2: 2+4 =6 (got the ans)
>
> > > But the qs mentions that it should be in O(1) space.
> > > Regards,
> > > Anna
>
> > >  On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf  > > > wrote:
>
> > >> @divya : i guess... it wont work.
> > >> consider Array {1,2,3,4,123456}
> > >> and you want sum 6.
>
> > >> @prashant: Is it O(n)?
>
> > >> I guess after converting to array and removing all entries > sum, we
> > >> should start with the smallest element
> > >> and scan the elements from last till we get some value x which together
> > >> with the smallest value sums to < sum. Call this position POS1.
> > >> If we get required sum somewhere in the process, cool !
> > >> Else take drop the elements after POS1 and also the smallest element.
> > >> Recurse on the remaining.
>
> > >> --
> > >> Rohit Saraf
> > >> Second Year Undergraduate,
> > >> Dept. of Computer Science and Engineering
> > >> IIT Bombay
> > >>http://www.cse.iitb.ac.in/~rohitfeb14
>
> > >> On Fri, May 14, 2010 at 3:51 PM, Prashant K 
> > >> wrote:
>
> > >>> i think it can done like this,
> > >>> assume we have to find 'x' and 'y'  wer s='x'+'y'
>
> > >>> 1) select ith node from tree (from beginning to end)
> > >>> 2) y= s - " ith number (node)"
> > >>> 3) now search for 'y' in BST if we found then there is node such that s=
> > >>> x + y; otherwise no..
>
> > >>> -- Prashant Kulkarni
> > >>> || Lokaha Samastaha Sukhino Bhavanthu ||
> > >>> || Sarve Jana Sukhino Bhavanthu ||
>
> > >>> On Fri, May 14, 2010 at 2:47 AM, divya jain 
> > >>> wrote:
>
> > >>>> form a sorted  array from inorder traversal of tree. now take to
> > >>>> pointers one to the beginning of array and other at the end. now check 
> > >>>> if
> > >>>> the sum of element is greater than reqd sum then increment 1st ptr. if 
> > >>>> their
> > >>>> sum is less than reqd sum then decrement 2nd ptr. if their sum is 
> > >>>> equal to
> > >>>> the reqd sum then this is the ans..
> > >>>> hope it will work..
>
> > >>>> On 13 May 2010 20:11, jalaj jaiswal  wrote:
>
> > >>>>> given a bst... find two nodes whose sum is equal to a number k ... in
> > >>>>> O(n) time and constant space...
>
> > >>>>> --
> > >>>>> 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 

[algogeeks] Re: frequency

[Modeling Expert]

@sharad : Thanx !! But is it really O(K) ?
if you use map for say "AMAZON" you need 5 (chars) + ( 5*4)
( ints) = 25 bytes. + some more space due to MAP structure
One more char and you are crossing 26 bytes solution provided by
Jalaj.  Think about storing "Allodoxaphobia"
A= 3 , L = 2 O = 3 , D = 1 X = 1 P =1 H = 1 B = 1 I = 1  , 9 chars so
9* ( 1+4) = 45 bytes !!!

Using uint8_t char_array[26]  would have been cheaper ( uint8_t is
typedef of unsigned char ) ??

Am I correct ?

-Manish
PS: I am not a student , working as device modeling guy at a
semiconductor company where we don't use Algorithms at all :( Joined
this community recently to brush up my long-forgotten skills :)

On May 16, 5:10 pm, sharad kumar  wrote:
> @Modelling expert.
>
> #include
> #include
> #include
> using namespace std;
> int main()
> {
>     string s="amazon";
>     int i=0,j=0;
>     mapmp;
>     for(i=0;i     {
>                              mp[s.at(i)]++;
>                              }
>                              for(i=0;i                              {
>                                   cout<                                   }
>                                   cin.sync();
>                                   cin.get();
>                                   return 0;
>                                   }
> PS.r u from Institute of mathematical Research science or CMI ...
>
> On Sun, May 16, 2010 at 1:50 PM, Modeling Expert <
>
>
>
> cs.modelingexp...@gmail.com> wrote:
> > @sharad : Can you explain with same 'amazon' example for key mapping.
> >  if we have O(K) hash map, how would we map keys as We need to
> > 'remember' mapping to print things back .
> > e.g. ASCII valueof (C1)% sizeof(string) could be equal to
> > valueof(C2)%sizeof(string) where strins is  "C1C2..."
>
> > @divya your solution looks OK to me , its would be O(k) for space,
> > time O ( KlgK) , right ?
>
> > On May 14, 8:20 am, sharad kumar  wrote:
> > > cant u use a hash map  of O(K) where K is distinct elements in
> > > string..
>
> > > On Thu, May 13, 2010 at 8:13 PM, jalaj jaiswal <
> > jalaj.jaiswa...@gmail.com>wrote:
>
> > > > input a character array from the user and output in the following way.
> > > > example string is amazon.. then output should be a2m1z1o1n1
>
> > > > i did it taking a 26 size array... some better solution ??
>
> > > > --
> > > > 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.
>
> > > --
> > > 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 athttp://
> > 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.
>
> --
> 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 
> athttp://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: BST

[Modeling Expert]

@Divya I think your solution is correct. To do in constant time , we
can use BST itself instead of storing in array.
Have two array , make first point to left most , make second point to
right most member, now start your algorithm while making
these two pointers move. Left pointer should move in 'inorder' style
while right pointer should move in 'reverse inorder style'
if ( *LeftPtr + * RightPtr > k ) Decrement ( RightPtr)
if ( *LeftPtr + * RightPtr < k ) Increment (LeftPtr)
else WeHaveAnswer


-Manish

On May 15, 6:49 am, Yalla Sridhar  wrote:
> if the tree has parent pointer then we can apply similar approach,,
> increment and decrenent... and can also be done in O(1)
>
> have to poninters pointed to the min and max nodes and them move pointers by
> checking the sums..
>
>
>
> On Fri, May 14, 2010 at 5:03 PM, anna thomas  wrote:
> > @rohit: Divya's soltn works in this way, if the sum of 2 nos is less than
> > req sum, increment the 1st ptr(ptr at beginning of array). If sum > req sum,
> > then decrement the 2nd ptr(ptr at end of array)
> > In ur example: ptr1 pts to 1 and ptr2 to 123456 (sum > 6)
> > dec ptr2 1+4 = 5 (sum < 6)
> > inc ptr2: 2+4 =6 (got the ans)
>
> > But the qs mentions that it should be in O(1) space.
> > Regards,
> > Anna
>
> >  On Fri, May 14, 2010 at 4:20 PM, Rohit Saraf  > > wrote:
>
> >> @divya : i guess... it wont work.
> >> consider Array {1,2,3,4,123456}
> >> and you want sum 6.
>
> >> @prashant: Is it O(n)?
>
> >> I guess after converting to array and removing all entries > sum, we
> >> should start with the smallest element
> >> and scan the elements from last till we get some value x which together
> >> with the smallest value sums to < sum. Call this position POS1.
> >> If we get required sum somewhere in the process, cool !
> >> Else take drop the elements after POS1 and also the smallest element.
> >> Recurse on the remaining.
>
> >> --
> >> Rohit Saraf
> >> Second Year Undergraduate,
> >> Dept. of Computer Science and Engineering
> >> IIT Bombay
> >>http://www.cse.iitb.ac.in/~rohitfeb14
>
> >> On Fri, May 14, 2010 at 3:51 PM, Prashant K 
> >> wrote:
>
> >>> i think it can done like this,
> >>> assume we have to find 'x' and 'y'  wer s='x'+'y'
>
> >>> 1) select ith node from tree (from beginning to end)
> >>> 2) y= s - " ith number (node)"
> >>> 3) now search for 'y' in BST if we found then there is node such that s=
> >>> x + y; otherwise no..
>
> >>> -- Prashant Kulkarni
> >>> || Lokaha Samastaha Sukhino Bhavanthu ||
> >>> || Sarve Jana Sukhino Bhavanthu ||
>
> >>> On Fri, May 14, 2010 at 2:47 AM, divya jain 
> >>> wrote:
>
>  form a sorted  array from inorder traversal of tree. now take to
>  pointers one to the beginning of array and other at the end. now check if
>  the sum of element is greater than reqd sum then increment 1st ptr. if 
>  their
>  sum is less than reqd sum then decrement 2nd ptr. if their sum is equal 
>  to
>  the reqd sum then this is the ans..
>  hope it will work..
>
>  On 13 May 2010 20:11, jalaj jaiswal  wrote:
>
> > given a bst... find two nodes whose sum is equal to a number k ... in
> > O(n) time and constant space...
>
> > --
> > 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.
>
> >>>   --
> >>> 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 

[algogeeks] Re: frequency

[Modeling Expert]

@sharad : Can you explain with same 'amazon' example for key mapping.
 if we have O(K) hash map, how would we map keys as We need to
'remember' mapping to print things back .
e.g. ASCII valueof (C1)% sizeof(string) could be equal to
valueof(C2)%sizeof(string) where strins is  "C1C2..."

@divya your solution looks OK to me , its would be O(k) for space,
time O ( KlgK) , right ?

On May 14, 8:20 am, sharad kumar  wrote:
> cant u use a hash map  of O(K) where K is distinct elements in
> string..
>
> On Thu, May 13, 2010 at 8:13 PM, jalaj jaiswal 
> wrote:
>
>
>
> > input a character array from the user and output in the following way.
> > example string is amazon.. then output should be a2m1z1o1n1
>
> > i did it taking a 26 size array... some better solution ??
>
> > --
> > 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.
>
> --
> 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 
> athttp://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: question

[Modeling Expert]

@vivek : Hi , not sure , how your solution would work . Can you
explain with this set
A = { -5, 8,  9, 2 , -1 , 0 , 1 , 5, 7 }


On May 3, 8:33 pm, vivek bijlwan  wrote:
> copy the array(A) in a different array(B) to store the index info.(space
> O(n))
> sort(A)
> take each pair's sum ( complexity  O(n^2) ) and with that do a binary search
> for the 3rd element needed.(O(log(n))).
>
> Check for the indices in B.
>
> i believe it can be done in better time somehow.
>
> On Mon, May 3, 2010 at 6:48 PM, jalaj jaiswal 
> wrote:
>
>
>
>
>
> > given an array(unsorted) may contain negative numbers too
> > find the index of three numbers whose sum is closest to zero  in  O(N2 log
> > N) time and O(N) space.
>
> > P.S -3 is more close to zero then -6 (number line ...)
> > --
> > 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 
> athttp://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.