[algogeeks] Re: Minimal number of swaps

[icy`]

oh, nevermind, sorry ;P  you want the 1's at the beginning, not the end... 
  //friday

On Friday, April 22, 2016 at 4:07:53 PM UTC-4, icy` wrote:
>
> Hi,
> I'm not sure I understand the second example.  Shouldn't the second one 
> also produce an answer of  1 (swap the one in index 1 with the zero in the 
> last index)
> 0 *1* 0 1 1 1 *0*
>
> icy`
>
> On Tuesday, March 29, 2016 at 10:00:21 AM UTC-4, Régis Bacra wrote:
>>
>> This puzzle comes from a contribution on codingame.com (link to the 
>> puzzle <https://www.codingame.com/games/community/?puzzleId=103>). Any 
>> idea to solve it efficiently?
>>
>> Given a list of 1 and 0, you must regroup all the 1 at the begin of the 
>> list in a minimum number of steps. A step is the interchange of two 
>> elements located at different positions.
>> The expected result is the minimum number of steps required to obtain a 
>> sorted list.
>>
>> Examples:
>> 1 0 1 0 1 -> 1
>> 0 1 0 1 1 1 0 -> 2
>>
>

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

[algogeeks] Re: Minimal number of swaps

[icy`]

Hi,
I'm not sure I understand the second example.  Shouldn't the second one 
also produce an answer of  1 (swap the one in index 1 with the zero in the 
last index)
0 *1* 0 1 1 1 *0*

icy`

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

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

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

[icy`]

nice solution, Dave!

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

On Wednesday, October 3, 2012 2:08:56 AM UTC-4, Umer Farooq wrote:
>
> @Dave Thanks for pointing that out.
>
> But I still can't get what if elem is on first element or it is not 
> present in the array? How is your code going to handle that situation?
>
> @Atul, Well yes, In the given question, the number of iterations were 2n. 
> Which I have reduced to n+n/2.
>
>
>
>
>
> On Tue, Oct 2, 2012 at 11:13 PM, atul anand 
> > wrote:
>
>> @umer : how no. of comparison are reduced to half by moving both
>> sidesyou have 2 if condition inside, so you are making 2
>> comparisons at each iteration + n/2 comparison for while loop so
>> number of comparisons are n+n/2
>>
>> On 10/2/12, Umer Farooq > wrote:
>> > why don't we try it from both ends ... something like this:
>> >
>> > int i = 0; j = size-1;
>> >
>> > while (i != j)
>> > {
>> > if (arr[i] == elem)
>> >   return arr[i];
>> > if (arr[j] == elem)
>> >return arr[j];
>> > }
>> >
>> > this way, we have eliminated half of the comparisons in for loop? What 
>> do
>> > you guys say?
>> >
>> > On Tue, Oct 2, 2012 at 12:18 PM, rafi > 
>> wrote:
>> >
>> >> Vikas is right!
>> >> while (n) is equal to (while n!=0)
>> >> you have 2n compares!
>> >>
>> >> בתאריך יום שני, 1 באוקטובר 2012 12:12:21 UTC+2, מאת vikas:
>> >>
>> >>> still there is no improvement, compiler will generate the code to
>> >>> compare
>> >>> with zero here. what you have accomplished is , hide it from human 
>> eyes
>> >>>
>> >>> On Monday, 1 October 2012 15:25:09 UTC+5:30, Navin Kumar wrote:
>> 
>>  @atul:
>>  still it won't compare 0 th element. Slight modification in your 
>> code:
>> 
>>  n=*sizeof(arr)*;
>>  do
>>  {
>>   if(elem==arr[*--n*])
>>   print found;
>> 
>>  }while(n);
>> 
>>  On Mon, Oct 1, 2012 at 9:50 AM, atul anand  
>> wrote:
>> 
>> > yes, but there no need of checking outside the loop
>> >
>> > n=sizeof(arr)-1;
>> > do
>> > {
>> >  if(elem==arr[n])
>> >  print found;
>> > n--;
>> >
>> > }while(n);
>> >
>> >
>> >
>> > On Mon, Oct 1, 2012 at 9:33 AM, Navin Kumar
>> > wrote:
>> >
>> >> @atul: keep one more checking outside loop for element at 0 th 
>> index.
>> >> Because when n = 0  the your loop come out from the loop without
>> >> comparing
>> >> it.
>> >>
>> >>
>> >> On Mon, Oct 1, 2012 at 8:55 AM, atul anand
>> >> wrote:
>> >>
>> >>> n=sizeof(arr);
>> >>> n--;
>> >>>
>> >>> while(n)
>> >>> {
>> >>>  if(elem=arr[n])
>> >>>   print found;
>> >>>
>> >>> n--;
>> >>>
>> >>> }
>> >>>
>> >>> On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר 
>> >>> wrote:
>> >>>
>>  Hi
>>  i was in an interview and was given a simple function
>>  int arrExsits(int* arr,int size,int elem){
>>  for (int i=0;i>  if(elem==arr[i])
>> return i;
>>  return -1;
>>  }
>>  this function does 2n compares
>>  n- the if statment
>>  n-check that i is smaller then size
>>  i was suppose to give an optimal (less compares) solution so i 
>> gave
>> 
>>  int arrExsits(int* arr,int size,int elem){
>>  if (arr[size-1]==elem)
>>  return size-1;
>>  arr[size-1]=elem]
>>  for (int i=0;;++i)
>>  if(elem==arr[i]){
>>  if (i!=size-1)
>>  return i;
>>  return -1;
>>  }
>>  this solution works and it has n+2 compares the first one 
>> another n
>>  and the second inner if.
>>  they told me it's good (and I've passed) but they told just for 
>> my
>>  knowledge that there is a better N compare solution.
>>  I've searched the web but couldn't find it.
>>  anybody knows?
>>  Thanks
>> 
>>  --
>>  You received this message because you are subscribed to the 
>> Google
>>  Groups "Algorithm Geeks" group.
>>  To post to this group, send email to algo...@googlegroups.com.
>>  To unsubscribe from this group, send email to
>>  algogeeks+...@googlegroups.com**.
>>  For more options, visit this group at 
>> http://groups.google.com/**
>>  group/algogeeks?hl=en<
>> http://groups.google.com/group/algogeeks?hl=en>
>>  .
>> 
>> >>>
>> >>>  --
>> >>> You received this message because you are subscribed to the Google
>> >>> Groups "Algorithm Geeks" group.
>> >>> To post to this group, send email to algo...@googlegro

[algogeeks] Re: Missing Number Problem

[icy`]

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

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

[image: Inline image 1]

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

<>

[algogeeks] Re: Facebook question!

[icy`]

At first I found this tricky, as the number of strings in the array is
unknown, and it can be hard to iterate over unknown items of unknown
length.  Since repeated combinations are included, we know the total number
of combinations (lengths of all strings multiplied).  In my Ruby example
below, I used strings "abcde", "123", and "YZ" .   My method was to set up
a resulting array of empty strings of length 30 (5*3*2).Then I examined
the kind of combinations we will make:
a1Y  a1Z  a2Y  a2Z  a3Y  a3Z ,  b1Y  etc.

Notice if we generate combinations in this order, a will repeat six times
in a row, and this is because the remaining elements are three and two
letters long (3*2).   Similarly, the numbers in "123" will be repeated
twice in a row, because the remaining (last) word has only two characters.
 This amount of repetition is assigned to variable *repeats* below. And
each element of  "YZ" repeats once in a row since there are no more
elements after.  If there is more room in the total combinations, then the
word will repeat again from the beginning; e.g. for "123"  the middle
characters of the answers will be 1,1, 2,2,3,3,1,1,2,2,3,3  until 30 is
reached.

The strings of the res array are slowly built in this way.   Ruby helps
deal with some of the other minor issues.  Pic below.

icy`

[image: Inline image 1]

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

<>

Re: [algogeeks] spoj problem EASYMATH

[icy`]

why not just brute force this?  one little array contains [a, (a+d),
(a+2d), (a+3d), (a+4d) ], which is then filtered so that none of those are
multiples of another.

Then set a count variable to m-n+1.  Check all numbers in range against
your little array, decrementing count and breaking out if a divisible num
is found.  In Ruby, screenshot so that syntax highlighting remains.
 (comments start with #  )

[image: Inline image 1]

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

[icy`]

hm, very strange set of numbers.  If the first number was 38 I *might*
see the hints of a pattern, but since it is just 3,  I have no idea.

[if the first number was ]   38(now +1, or 1 squared)
39 , 41, 43, 45(+4, or 2 squared)
49, 51, 53, 55(+9, or 3 squared)
64, __  __  __   (I would then guess  66, 68, 70, and 86)

icy`


On Feb 28, 7:44 am, srikanth reddy malipatel 
wrote:
> {39,41,43,45}    incremented by 2
> {49,51,53,55}    incremented by 2
> {64,?,?,?}
>
> first number in each set is considered as base number.
> 3 is for the number of numbers in each set other than base number.
> so in final set base number is 64 and other 3 numbers are incremented by 2.
>
>
>
>
>
>
>
>
>
> On Tue, Feb 28, 2012 at 1:48 PM, payal gupta  wrote:
> > one option cud be reverse the digits...i.e
> > (bt the first n d last do not satisfy d pattern howeva)
> > 93 , 14,34,54,94,15,35,35,55
> > an increment is applied to the last 4th no each tme...
> > not very sure if its crckt...
>
> > Regards,
> > PAYAL GUPTA
>
> > On Tue, Feb 28, 2012 at 12:48 PM, Kartik Sachan 
> > wrote:
>
> >> I think logic is the difference is
> >> 2 2 4 2 2 2 8 so next will be 2 2  2 2 2 16
>
> >> so ans will be 66 68 70
>
> >> but first number 3 making some problem
>
> >> --
> >> 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.
>
> --
> Srikanth Reddy M
> (M.Sc Tech.) Information Systems
> BITS-PILANI

-- 
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: Programming Question

[icy`]

I dont know Pascal too well, but to me it looks like nested "if"
statements.

If x>y   ,  all the rest of it happens

Since x is not greater than y, nothing happens.   So x and y should
remain the same (10,20)

On Nov 17, 6:09 am, Vijay Khandar  wrote:
> In the following Pascal Program segment what is the value of X after
> the execution of the program segment?
>
> X:=10; Y:=20;
> If X>Y,then if X<0 then X:=abs(X) else X:=2*X;
>
> Plz anyone explain

-- 
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: Minimize bins

[icy`]

yea, i'd go with greedy also.   Fill bin with biggest size s1 as much
as possible (and same for other bins),  then try to squeeze in next
biggest size s2, etc.

On Oct 29, 7:17 am, teja bala  wrote:
> Greedy knapsack algorithm will work fine in this case as in each bin
>
> n1s1+n2s2+..nrsr<=C gives the optimal solution...
>
>
>
>
>
>
>
> On Sat, Oct 29, 2011 at 4:34 AM, SAMMM  wrote:
> > Suppose u have n1 items of size s1,
> > n2 items of size s2 and n3 items of size s3. You'd like to pack
> > all of these items into bins each of capacity C, such that the
> > total number of bins used is minimized.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: Intersection of arrays

[icy`]

you didnt mention if duplicate elements should appear in the
intersection or not.  If no duplicates necessary, then your language
may already have intersection between arrays built in.  Or you should
write an intersection operator/method between arrays  (in ruby it is
just the "&"  operator).   My example output:

arrays: 6
elements in each array: 20
range: 1 to 5
array #1: [4, 5, 5, 1, 4, 3, 4, 3, 2, 5, 2, 5, 1, 3, 3, 1, 2, 3, 1, 5]
array #2: [2, 2, 3, 5, 2, 5, 1, 1, 2, 3, 1, 1, 2, 5, 3, 2, 3, 3, 2, 2]
array #3: [1, 3, 2, 5, 4, 3, 1, 1, 2, 1, 5, 4, 4, 4, 2, 2, 5, 1, 2, 2]
array #4: [3, 5, 4, 5, 1, 2, 3, 4, 3, 2, 1, 1, 2, 2, 4, 1, 2, 3, 2, 3]
array #5: [2, 1, 5, 2, 1, 4, 3, 2, 3, 1, 2, 4, 4, 2, 4, 5, 5, 3, 5, 5]
array #6: [4, 4, 2, 5, 3, 2, 5, 3, 5, 3, 2, 4, 4, 2, 5, 5, 4, 3, 1, 1]
intersection: [2, 1, 3]

my intersection here is simply  ar1 & ar2 & ar3 & ar4 & ar5 & ar6  ,
no duplicates show up.

On Oct 28, 3:09 am, kumar raja  wrote:
> How is it possible to create a hash map using elements as keys and their
> counts as values .If we give some key the value is automatically computed by
> hash function .If u are given an element/key its index/value is calculated
> by hash function.am i corrct??
>
> On 27 October 2011 22:36, Nitin Garg  wrote:
>
>
>
>
>
>
>
>
>
> > The hashing solution is similar to the 1st answer 
> > here
>
> > A sorting solution will take O(k.n.logn)  time
>
> > On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage  wrote:
>
> >> Don,
> >> As you said, the intersection set, won't really be in sorted order as it
> >> depends on the elements of the second array, which are unsorted. Still,
> >> sorting them wouldn't be much different as it'd be worst case O(n logn).. [
> >> Array 2 == Array 1 ]
> >> But sorting the First Array has already cost O(n logn)
>
> >> So I guess the worse case complexity has to be O(n logn) anyway..
>
> >> On Thu, Oct 27, 2011 at 10:54 PM, Dan  wrote:
>
> >>> Hashing all of the K arrays seems like a bit much.   How about this?
>
> >>> You have  K  seperate arrays to start with,  each array having N
> >>> elements (is that correct?).
>
> >>> 1)  Sort the first array.
>
> >>> 2)  Step through the 2nd array, 1 element at a time  say
> >>> Array(2).element(i)
> >>>     Check to see if the value of  Array(2).element(i) is in the first
> >>> sorted array.
> >>>     If it is,  add this numeric value to your list of  "intersection
> >>> elements".
>
> >>>     As you pass through all elements of the 2nd array,  the values
> >>> found which
> >>>     are intersecting need to be saved  ( maybe in the 1st arrays
> >>> space to save
> >>>      memory).   Ideally, these should be saved in sorted order as
> >>> they are found.
>
> >>>     ( how you store the sorted array will affect speed of this check
> >>> of course.
> >>>       I'd keep it simple on the 1st round, then optimize the code
> >>> once everything
> >>>       appears to be working well, ie with buckets or pointers or
> >>> whatever.  How
> >>>       you determine if an element in array 2 intersects with an
> >>> element of array
> >>>       1 will depend on how you store your sorted array.  You might do
> >>> a linear
> >>>       search or a binary search or a bucket search of some sort ).
>
> >>> 3)  Now...  step through the 3rd array,  1 element at a time,  looking
> >>> to see if each
> >>>    value is in the  just created  list  of   "intersection elements"
>
> >>> 4)  Do the save thing now with each of the remaining original K
> >>> arrays.
>
> >>> Dan    :-)
>
> >>> On Oct 24, 10:17 pm, kumar raja  wrote:
> >>> >  Find intersection of K unsorted array of N elements each. Intersection
> >>> > consists of elements that appear in all the K arrays.
>
> >>> > what data structure is useful here??
>
> >>> > --
> >>> > Regards
> >>> > Kumar Raja
> >>> > M.Tech(SIT)
> >>> > IIT Kharagpur,
> >>> > 10it60...@iitkgp.ac.in
>
> >>> --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> Anup Ghatage
>
> >>  --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > Nitin Garg
>
> > "Personality can open doors, but only Character can keep them open"
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to

[algogeeks] Re: Intersection of arrays

[icy`]

sorry, i made a slight coding mistake in my last post (invisible 7th
array) , but the logic remains the same...corrected sample output:

arrays: 6
elements in each array: 20
range: 1 to 5
array #1: [3, 4, 3, 4, 5, 3, 2, 2, 1, 4, 2, 3, 4, 4, 3, 1, 3, 2, 4, 4]
array #2: [1, 4, 5, 2, 1, 5, 1, 4, 3, 1, 3, 2, 5, 4, 4, 1, 3, 4, 5, 3]
array #3: [4, 3, 4, 3, 3, 5, 2, 5, 4, 5, 2, 2, 1, 5, 5, 4, 4, 1, 2, 2]
array #4: [4, 2, 5, 1, 1, 1, 1, 1, 5, 5, 1, 3, 4, 1, 5, 4, 3, 5, 2, 5]
array #5: [3, 4, 2, 5, 1, 4, 1, 5, 5, 5, 3, 5, 2, 1, 4, 1, 1, 5, 2, 5]
array #6: [5, 5, 2, 4, 3, 5, 5, 4, 1, 4, 2, 3, 1, 1, 5, 2, 5, 1, 3, 4]
intersection: [3, 4, 5, 2, 1]


On Oct 28, 3:09 am, kumar raja  wrote:
> How is it possible to create a hash map using elements as keys and their
> counts as values .If we give some key the value is automatically computed by
> hash function .If u are given an element/key its index/value is calculated
> by hash function.am i corrct??
>
> On 27 October 2011 22:36, Nitin Garg  wrote:
>
>
>
>
>
>
>
>
>
> > The hashing solution is similar to the 1st answer 
> > here
>
> > A sorting solution will take O(k.n.logn)  time
>
> > On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage  wrote:
>
> >> Don,
> >> As you said, the intersection set, won't really be in sorted order as it
> >> depends on the elements of the second array, which are unsorted. Still,
> >> sorting them wouldn't be much different as it'd be worst case O(n logn).. [
> >> Array 2 == Array 1 ]
> >> But sorting the First Array has already cost O(n logn)
>
> >> So I guess the worse case complexity has to be O(n logn) anyway..
>
> >> On Thu, Oct 27, 2011 at 10:54 PM, Dan  wrote:
>
> >>> Hashing all of the K arrays seems like a bit much.   How about this?
>
> >>> You have  K  seperate arrays to start with,  each array having N
> >>> elements (is that correct?).
>
> >>> 1)  Sort the first array.
>
> >>> 2)  Step through the 2nd array, 1 element at a time  say
> >>> Array(2).element(i)
> >>>     Check to see if the value of  Array(2).element(i) is in the first
> >>> sorted array.
> >>>     If it is,  add this numeric value to your list of  "intersection
> >>> elements".
>
> >>>     As you pass through all elements of the 2nd array,  the values
> >>> found which
> >>>     are intersecting need to be saved  ( maybe in the 1st arrays
> >>> space to save
> >>>      memory).   Ideally, these should be saved in sorted order as
> >>> they are found.
>
> >>>     ( how you store the sorted array will affect speed of this check
> >>> of course.
> >>>       I'd keep it simple on the 1st round, then optimize the code
> >>> once everything
> >>>       appears to be working well, ie with buckets or pointers or
> >>> whatever.  How
> >>>       you determine if an element in array 2 intersects with an
> >>> element of array
> >>>       1 will depend on how you store your sorted array.  You might do
> >>> a linear
> >>>       search or a binary search or a bucket search of some sort ).
>
> >>> 3)  Now...  step through the 3rd array,  1 element at a time,  looking
> >>> to see if each
> >>>    value is in the  just created  list  of   "intersection elements"
>
> >>> 4)  Do the save thing now with each of the remaining original K
> >>> arrays.
>
> >>> Dan    :-)
>
> >>> On Oct 24, 10:17 pm, kumar raja  wrote:
> >>> >  Find intersection of K unsorted array of N elements each. Intersection
> >>> > consists of elements that appear in all the K arrays.
>
> >>> > what data structure is useful here??
>
> >>> > --
> >>> > Regards
> >>> > Kumar Raja
> >>> > M.Tech(SIT)
> >>> > IIT Kharagpur,
> >>> > 10it60...@iitkgp.ac.in
>
> >>> --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> Anup Ghatage
>
> >>  --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > Nitin Garg
>
> > "Personality can open doors, but only Character can keep them open"
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Regards
> Kumar Raja
> M.Tech(SIT)
> IIT

[algogeeks] FACEBOOK ONLINE CODING ROUND

[icy`]

small typo..  in part 2)   it should say   13-(1+4+6)=2.   Basically
when the position becomes smaller than the element, you stop subtracting.

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

[algogeeks] Re: FACEBOOK ONLINE CODING ROUND

[icy`]

is this contest still going? if so, where ?  i have a solution that
does
(100, 1267650600228229401496703205376 )(just one hundred 1's)
in 0.03 seconds in an older ruby on an older pc

I'd like to submit ;P


On Oct 21, 10:48 pm, sunny agrawal  wrote:
> yea i know 1st Approach is much better and is Only O(N^2) for
> precomputing all the values for nck and then O(k) for finding no of
> bits set in The Kth number and another loop of O(k) to find the
> required number
>
> i posted 2nd approach in the context to vandana's tree approach of
> sorting 2^N numbers, rather simply sort the numbers in the array...
> and this approach is O(N*2^N)
>
> On 10/21/11, sravanreddy001  wrote:
>
>
>
>
>
>
>
>
>
> > @Sunny.. why do we need an O(2^N) complexity?
>
> > for a value of N=40-50, the solution is not useful..
>
> > but, your 1st approach is lot better and i have got it too..
>
> > 1. O(N) complexity to search the k. (k bits in the numbers)  x- (sigma 1->k
> > (n C i))
> > 2. again, keep substracting (k-i) for i= 0->k-1  so.. O(k) here
> > and recursively performing step 2. (worst case complexity is O(T))
> > where T = nCk
>
> > O(N) + O(T) ==> O(T) as it dominates the given number. unless it doesn't
> > fall in the range.. or   equivalently -->  max( O(T), O(N) )
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To view this discussion on the web visit
> >https://groups.google.com/d/msg/algogeeks/-/NJR9l-UB7c8J.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Sunny Aggrawal
> B.Tech. V year,CSI
> Indian Institute Of Technology,Roorkee

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

[algogeeks] Re: remove duplicate words from a string

[icy`]

a)
1. could split the string using a regexp (into an array) in which you
define a "word"  --  is  "hi."  the same as "hi,"  and "hi"  ?
2. then perform a "unique" operation on the array (some languages have
this built in) to remove duplicates
3. recombine array elements into string by joining with a space, for
example, depending on how you split it in the first step

b) Perhaps another way, in-place, could be to check the string, one
"word" (again define this) at a time, storing each word in a hash.  If
the hash already contains the word, replace this occurrence with
spaces or null bytes.  Finally compact the string (remove all null
bytes, or turn all extra spaces into one space, etc).

icy`

On Oct 10, 3:08 pm, sunny agrawal  wrote:
> Trie will take too much space..
> Balanced Binary tree can be Better ...??
>
>
>
>
>
>
>
>
>
> On Tue, Oct 11, 2011 at 12:16 AM, Ankur Garg  wrote:
> > I think this can be done through tries
>
> > Any better solution ?
>
> > On Mon, Oct 10, 2011 at 10:59 PM, sachin goyal wrote:
>
> >> remove duplicate words from a string with min. complexityy.
>
> >> --
> >> 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.
>
> --
> Sunny Aggrawal
> B.Tech. V year,CSI
> Indian Institute Of Technology,Roorkee

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

[algogeeks] i cannot solve this written test question

[icy`]

one possible solution in ruby  (sry if this is double-posted -- i did not
see it come up the first time)

[image: digsum_output.png]

-- 
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] i cannot solve this written test question

[icy`]

one possible ruby solution/pic  attached

-- 
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: character count in array

[icy`]

Just use a hash to count frequency of something;  e.g. in ruby:
ar= %w(a a b c a b b c d e a d e f)
freq=Hash.new(0)
ar.each {|c| freq[c]+=1}
p freq

#output
#{"a"=>4, "b"=>3, "c"=>2, "d"=>2, "e"=>2, "f"=>1}

you could only do it in place in O(1) only if your input array is
already  2*(number of all possible characters) size, but you didnt
mention size of input array.  For example, what if input was just
[a,b,c,d,e]  ?  The size is 5.You cant just convert the input
into  [a,1,b,1,c,1,d,1,e,1] without increasing the size to 10.   So
hash is the better method.

On Sep 3, 11:04 am, Ankuj Gupta  wrote:
> if for all inputs you array remains of same size we can take it as
> constant space
>
> On Sep 3, 7:49 pm, rajul jain  wrote:
>
>
>
>
>
>
>
> > @ankuj  just want to clarify that in hashing method we require array of
> > fixed size let say arr[26] , so is it considered as constant space or not?
>
> > On Sat, Sep 3, 2011 at 8:02 PM, siddharam suresh 
> > wrote:
>
> > > sol already posted please search old thread
> > > Thank you,
> > > Sid.
>
> > > On Sat, Sep 3, 2011 at 8:01 PM, Ankuj Gupta  wrote:
>
> > >> If we take our input to be characters a-z ans A-Z then we require
> > >> fixed space which can be treated as O(1).
> > >> On Sep 3, 7:10 pm, teja bala  wrote:
> > >> > this 'll work if u i/p the string in dis manner
> > >> > aaabbcc(consecutive same)
> > >> > a3b2c2
>
> > >> > #include
> > >> > #include
> > >> > main()
> > >> > {
> > >> > int x=1,i=0;
> > >> > char a[100];
> > >> > gets(a);
> > >> > while(a[i]!='\0')
> > >> > {
> > >> >  while(a[i]==a[i+1])
> > >> >  {
> > >> >     x++;
> > >> >     i++;
> > >> >  }
> > >> >  printf("%c%d",a[i],x);
> > >> >  x=1;
> > >> >  i++;
> > >> >  }
> > >> > getchar();
>
> > >> > }
>
> > >> --
> > >> 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: Find the Max from each sub-array of size k Options

[icy`]

I apologize to the group; i meant to post as reply to "Find the Max
from each sub-array of size k"  but I accidentally selected the word
"Options" as well.  Sorry.

On Sep 2, 3:42 pm, "icy`"  wrote:
> comparison/benchmarks of the
> 1) naive method, which just calls max with every new index, up to size of
> array - k
> 2) my method , which only makes a call to max if the old max is out of range
> or the newest/very rightmost element is greater than max
>
> ruby code:
> [image: max_subarray_text.png]
>
> benchmark output:
> [image: max_subarray_output.png]
>
> To test this, I had shuffled an array of size 1000 with k=25.    I also
> called each method 1000 times, which shows  5x improvement over naive method
>
> icy`
>
>  max_subarray_output.png
> 3KViewDownload
>
>  max_subarray_text.png
> 26KViewDownload

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

[algogeeks] Find the Max from each sub-array of size k Options

[icy`]

comparison/benchmarks of the
1) naive method, which just calls max with every new index, up to size of
array - k
2) my method , which only makes a call to max if the old max is out of range
or the newest/very rightmost element is greater than max

ruby code:
[image: max_subarray_text.png]

benchmark output:
[image: max_subarray_output.png]


To test this, I had shuffled an array of size 1000 with k=25.I also
called each method 1000 times, which shows  5x improvement over naive method

icy`

-- 
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 Max Sum Value Pairs

[icy`]

@Dave  thanks for clarifying that  (4,3) is different from (3,4)

But let's suppose, for example, n is 3
so A is of size n, and B is of size n, as required
e.g.  A = [1 1 2]   , B = [1 2 2]

S = { (1,1) (1,2) (1,2) (1,1) (1,2) (1,2) (2,1) (2,2) (2,2) }

but now you see there are repeated points that are also in the same
order.  These are duplicates and should be removed, if S is truly a
set.  Pruned version:

S = { (1,1) (1,2) (2,1) (2,2) }

size of set is not n^2, or 9, but rather
(size of unique(A) )  *  (size of unique(B) )  = 4

With this in mind, I would first eliminate or ignore duplicates as you
are iterating through A, B


On Sep 1, 5:50 pm, Dave  wrote:
> @Icy: You left off the pairs (3,4), (2,4), (2,3), (1,4), (1,3), and
> (1,2). These are different than the pairs you listed, because they are
> ordered: the first element is from set A and the second element is
> from set B. This was masked because of your choice of A = B. But you
> wouldn't have made that mistake if you had chosen A = [1 2 3 4] and B
> = [5 6 7 8].
>
> There is no restriction in the original problem statement that the
> numbers in each array are distinct. One application I have seen of
> this problem is with the travel reservation web sites, where they will
> show you some number of the cheapest round trip flight combinations.
> In that case, there is more to the data items than just the price,
> including at least airline and flight time. Several different flights
> might have the same price, so arrays like A = [1 1 2 3 3 3 3] and B =
> [1 2 2 2 3 3 4 4 4 4] (with duplicate prices) are possible. In that
> case, the first 2 (cheapest) round trips will have score 2. Then
> follows 7 round trips with score 3. Etc.
>
> Dave
>
> On Sep 1, 4:12 pm, "icy`"  wrote:
>
>
>
>
>
>
>
> > actually this makes me think about the question requirements a bit..
> > in math, arent sets supposed to have *unique* elements?
>
> > so  if  A= [ 1 2 3 4]   ,   B= [ 1 2 3 4],  then shouldnt
> > S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
> > (1,1) }   ??
>
> > since A is equal to B, the size of S is  (4 choose 2) plus the four
> > mirror pairs, so 6+4 = 10
>
> > and the question implies mathematical sets with that notation, so why
> > are there necessarily  n squared elements in S ...?
>
> > On Sep 1, 2:01 pm, rajul jain  wrote:
>
> > > @bharat  I think pair of your example would be (4,4) , (4,3) ,(3,4),
> > > (3,3)
> > > correct me if am wrong..
>
> > > On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana <
>
> > > bagana.bharatku...@gmail.com> wrote:
> > > > @Mac: It gives us the first largest pair but need not all n pairs ..
> > > > ex:
> > > > A=1 1 3 4
> > > > B=1 2 3 4
> > > > pairs : (4,4),(4,3),(3,3),(2,4) .
>
> > > > On Thu, Sep 1, 2011 at 4:57 AM, MAC  wrote:
>
> > > >> since its sorted , cant we just take last (largest if assedning) 
> > > >> elements
> > > >> of each and  return o(1) .. (since +ve we can do so i guess)
>
> > > >> On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta 
> > > >> wrote:
>
> > > >>> Given two sorted positive integer arrays A(n) and B(n), we define a
> > > >>> set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
> > > >>> in S. The value of such a pair is defined as Val(a,b) = a + b. Now we
> > > >>> want to get the n pairs from S with largest values. need an O(n)
> > > >>> algorithm.
>
> > > >>> --
> > > >>> Regards,
> > > >>> Navneet
>
> > > >>> --
> > > >>> You received this message because you are subscribed to the Google 
> > > >>> Groups
> > > >>> "Algorithm Geeks" group.
> > > >>> To post to this group, send email to algogeeks@googlegroups.com.
> > > >>> To unsubscribe from this group, send email to
> > > >>> algogeeks+unsubscr...@googlegroups.com.
> > > >>> For more options, visit this group at
> > > >>>http://groups.google.com/group/algogeeks?hl=en.
>
> > > >> --
> > > >> thanks
> > > >> --mac
>
> > > >>  --
> > > >> You received this message because you are subscribed to the Google 
> > > >> Groups
> > > >> "Algorithm Geeks" group.
> > > >> To post to this group, send email to algogeeks@googlegroups.com.
> > > >> To unsu

[algogeeks] Re: Find Max Sum Value Pairs

[icy`]

i kinda just ate my own words there ;P  if a set has unique
elements,   {4,4} isnt possible.. it would just be {4}
i'm not sure how to deal with ( ) instead of { }

On Sep 1, 5:12 pm, "icy`"  wrote:
> actually this makes me think about the question requirements a bit..
> in math, arent sets supposed to have *unique* elements?
>
> so  if  A= [ 1 2 3 4]   ,   B= [ 1 2 3 4],  then shouldnt
> S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
> (1,1) }   ??
>
> since A is equal to B, the size of S is  (4 choose 2) plus the four
> mirror pairs, so 6+4 = 10
>
> and the question implies mathematical sets with that notation, so why
> are there necessarily  n squared elements in S ...?
>
> On Sep 1, 2:01 pm, rajul jain  wrote:
>
>
>
>
>
>
>
> > @bharat  I think pair of your example would be (4,4) , (4,3) ,(3,4),
> > (3,3)
> > correct me if am wrong..
>
> > On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana <
>
> > bagana.bharatku...@gmail.com> wrote:
> > > @Mac: It gives us the first largest pair but need not all n pairs ..
> > > ex:
> > > A=1 1 3 4
> > > B=1 2 3 4
> > > pairs : (4,4),(4,3),(3,3),(2,4) .
>
> > > On Thu, Sep 1, 2011 at 4:57 AM, MAC  wrote:
>
> > >> since its sorted , cant we just take last (largest if assedning) elements
> > >> of each and  return o(1) .. (since +ve we can do so i guess)
>
> > >> On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta 
> > >> wrote:
>
> > >>> Given two sorted positive integer arrays A(n) and B(n), we define a
> > >>> set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
> > >>> in S. The value of such a pair is defined as Val(a,b) = a + b. Now we
> > >>> want to get the n pairs from S with largest values. need an O(n)
> > >>> algorithm.
>
> > >>> --
> > >>> Regards,
> > >>> Navneet
>
> > >>> --
> > >>> You received this message because you are subscribed to the Google 
> > >>> Groups
> > >>> "Algorithm Geeks" group.
> > >>> To post to this group, send email to algogeeks@googlegroups.com.
> > >>> To unsubscribe from this group, send email to
> > >>> algogeeks+unsubscr...@googlegroups.com.
> > >>> For more options, visit this group at
> > >>>http://groups.google.com/group/algogeeks?hl=en.
>
> > >> --
> > >> thanks
> > >> --mac
>
> > >>  --
> > >> You received this message because you are subscribed to the Google Groups
> > >> "Algorithm Geeks" group.
> > >> To post to this group, send email to algogeeks@googlegroups.com.
> > >> To unsubscribe from this group, send email to
> > >> algogeeks+unsubscr...@googlegroups.com.
> > >> For more options, visit this group at
> > >>http://groups.google.com/group/algogeeks?hl=en.
>
> > > --
>
> > > **Please do not print this e-mail until urgent requirement. Go Green!!
> > > Save Papers <=> Save Trees
> > > *BharatKumar Bagana*
> > > **http://www.google.com/profiles/bagana.bharatkumar<http://www.google.com/profiles/bagana.bharatkumar>
> > > *
> > > Mobile +91 8056127652*
> > > 
>
> > >  --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.

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

[algogeeks] Re: Find Max Sum Value Pairs

[icy`]

actually this makes me think about the question requirements a bit..
in math, arent sets supposed to have *unique* elements?

so  if  A= [ 1 2 3 4]   ,   B= [ 1 2 3 4],  then shouldnt
S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
(1,1) }   ??

since A is equal to B, the size of S is  (4 choose 2) plus the four
mirror pairs, so 6+4 = 10

and the question implies mathematical sets with that notation, so why
are there necessarily  n squared elements in S ...?

On Sep 1, 2:01 pm, rajul jain  wrote:
> @bharat  I think pair of your example would be (4,4) , (4,3) ,(3,4),
> (3,3)
> correct me if am wrong..
>
> On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana <
>
>
>
>
>
>
>
> bagana.bharatku...@gmail.com> wrote:
> > @Mac: It gives us the first largest pair but need not all n pairs ..
> > ex:
> > A=1 1 3 4
> > B=1 2 3 4
> > pairs : (4,4),(4,3),(3,3),(2,4) .
>
> > On Thu, Sep 1, 2011 at 4:57 AM, MAC  wrote:
>
> >> since its sorted , cant we just take last (largest if assedning) elements
> >> of each and  return o(1) .. (since +ve we can do so i guess)
>
> >> On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta wrote:
>
> >>> Given two sorted positive integer arrays A(n) and B(n), we define a
> >>> set S = {(a,b) | a in A and b in B}. Obviously there are n2 elements
> >>> in S. The value of such a pair is defined as Val(a,b) = a + b. Now we
> >>> want to get the n pairs from S with largest values. need an O(n)
> >>> algorithm.
>
> >>> --
> >>> Regards,
> >>> Navneet
>
> >>> --
> >>> You received this message because you are subscribed to the Google Groups
> >>> "Algorithm Geeks" group.
> >>> To post to this group, send email to algogeeks@googlegroups.com.
> >>> To unsubscribe from this group, send email to
> >>> algogeeks+unsubscr...@googlegroups.com.
> >>> For more options, visit this group at
> >>>http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> thanks
> >> --mac
>
> >>  --
> >> You received this message because you are subscribed to the Google Groups
> >> "Algorithm Geeks" group.
> >> To post to this group, send email to algogeeks@googlegroups.com.
> >> To unsubscribe from this group, send email to
> >> algogeeks+unsubscr...@googlegroups.com.
> >> For more options, visit this group at
> >>http://groups.google.com/group/algogeeks?hl=en.
>
> > --
>
> > **Please do not print this e-mail until urgent requirement. Go Green!!
> > Save Papers <=> Save Trees
> > *BharatKumar Bagana*
> > **http://www.google.com/profiles/bagana.bharatkumar
> > *
> > Mobile +91 8056127652*
> > 
>
> >  --
> > 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: Fwd: 8 queens problem

[icy`]

interesting because just the other day I wrote something to get all 92
solutions for 8x8  "n queens"  problem  in a little under 3 sec.  I
also used to play chess seriously, and my coach once gave me this
exercise to find a few working configurations.

I would advise against blindly placing all queens and then checking if
"secure" -- way too many combinations to go through.  Your problem
here might be that it is possible to place 7 queens, and the 8th one
might have no place to go.  At this point in your algorithm, doesnt
"count" become 8 anyway, and tries to return true?

I went with the algorithm to place the rooks on the board, 8!
permutations, one on each row, and then check all diagonals.  This can
be limited to even fewer iterations, but it was fast enough for me.

hope this helps,
icy`

On Sep 1, 3:30 pm, mc2 verma  wrote:
> hey guys ,
>
> I am trying to solve 8-queens problem using backtracking. Here is my algo.
> Could someone please tell me what is wrong in this code??
>
> bool queen(int p,int count , int position[][])
> {
>   if(count == 8)  return true;
>
>   for(int i=p,i<8;i++)
>     for(int j=0;j<8;j++)
>         if(marked(i,j) == false )   // finding secure position on board
>          {
>             markboard(i,j);            // if found any secure position then
> mark all board positions which are in range of queen.
>             position[count][count]={i,j};   //save position for final answer
>             count++;
>             if(queen(p+1,count,position[][]) == true)
>               return true;
>          }
>
>
>
>
>
>
>
> }

-- 
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: microsoft interview

[icy`]

Dave has a nice idea but I cant get it to work =/
[[1, 0, 0, 1], [0, 0, 1, 0], [0, 0, 0, 0]]   original matrix

[[1, 0, 1, 1], [1, 1, 1, 1], [0, 0, 1, 1]]   dave's
[[1, 1, 1, 1], [1, 1, 1, 1], [1, 0, 1, 1]]   expected

Maybe I converted it wrong.   My method was basically the same as
Anup's --
1st pass fill rows and convert 1's to 2's.
2nd pass check for 2's and fill those columns.

But complexity seems to be n*m*m  + n*m*n =  nm^2 + mn^2
which is about   O(n^2 m^2) ?=/

I would like to get Dave's to work =P

On Aug 31, 1:47 pm, siva viknesh  wrote:
> @dave...additionally u ve to do this...checking the 1st row nd 1st
> column...
>
>  if(a[0][0])
>    set both first row and first column;
> else
>    for(i=1;i       if(a[0][i])
>           set first row;
>       else
>           set first column;
>
> On Aug 31, 10:34 pm, siva viknesh  wrote:
>
>
>
>
>
>
>
> > dave s algo is nice :)
>
> > On Aug 31, 10:09 pm, Dave  wrote:
>
> > > @Ashima: Scan all but the first row and the first column. If there is
> > > a 1 in a row, set the first element of that row to 1. If there is a 1
> > > in a column, set the first element of that column to zero. Now, set
> > > any element in all but the first row and the first column of the
> > > matrix that has a 1 it the first element of its row or a 1 in its
> > > first element of its colunn to 1.
>
> > > Dave
>
> > > On Aug 31, 12:02 pm, "Ashima ."  wrote:
>
> > > > @dave wats d logic behind ur code
>
> > > > Ashima
> > > > M.Sc.(Tech)Information Systems
> > > > 4th year
> > > > BITS Pilani
> > > > Rajasthan
>
> > > > On Wed, Aug 31, 2011 at 9:05 AM, Dave  wrote:
> > > > > @Manish:
>
> > > > > for( i = 1 ; i < n ; ++i )
> > > > >    for( j = 1 ; j < m ; ++j )
> > > > >        if( a[i][j] != 0 )
> > > > >            a[i][0] = a[0][j] = 1;
> > > > > for( i = 1 ; i < n ; ++i )
> > > > >    for( j = 1 ; j < m ; ++j )
> > > > >        if( a[i][0] + a[0][j] != 0 )
> > > > >            a[i][j] = 1;
>
> > > > > Dave
>
> > > > > On Aug 31, 8:40 am, manish kapur  wrote:
> > > > > > Input is a matrix of size n x m of 0s and 1s.
>
> > > > > > eg:
> > > > > > 1 0 0 1
> > > > > > 0 0 1 0
> > > > > > 0 0 0 0
>
> > > > > > If a location has 1; make all the elements of that row and column = 
> > > > > > 1. eg
>
> > > > > > 1 1 1 1
> > > > > > 1 1 1 1
> > > > > > 1 0 1 1
>
> > > > > > Solution should be with Time complexity = O(n*m) and O(1) extra 
> > > > > > space
>
> > > > > --
> > > > > You received this message because you are subscribed to the Google 
> > > > > Groups
> > > > > "Algorithm Geeks" group.
> > > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > > To unsubscribe from this group, send email to
> > > > > algogeeks+unsubscr...@googlegroups.com.
> > > > > For more options, visit this group at
> > > > >http://groups.google.com/group/algogeeks?hl=en.-Hidequotedtext -
>
> > > > - 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: convert a string into another in minimum number of steps

[icy`]

Yea, I hope the intermediate words are dictionary words; it's  more
fun that way.   I played such a game before, where you and a friend
try to convert some 4-letter word into another, using legal words.

BIKE ->  LAZY

BIKE
BAKE
RAKE
RAZE
LAZE
LAZY


On Aug 30, 2:25 am, kARTHIK R  wrote:
> So the intermediate words need not be dictionary words?
>
> Karthik R,
> R&D Engineer,
> Tejas Networks.
>
> On Tue, Aug 30, 2011 at 11:50 AM, PRATEEK VERMA wrote:
>
>
>
>
>
>
>
> > edit distance 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: solving a simple equation

[icy`]

well if the answer is more than 3, I would be surprised.  There are
probably some integer rules to justify really small limits, but here
is how I justified it to myself:

I.  Treat every variable like it is a.2a^2  <=  4a , or   a^2 <=
2a   .   This only works for a=1, a=2.  So likely  a cannot be more
than 2.

a)  suppose a=1 and treat d as a c.
b+c^2 = 1+b+2c
c^2 = 1+2c
c^2 - 2c - 1 = 0
c^2 - 2c +1 = 2
(c-1)^2   = 2
c = 1+- sqrt(2)
hmm.. so c doesnt even reach 3

b) suppose a=2 and treat d as a c.
2b + c^2 = 2 + b + 2c
b =  -c^2 - 2c + 2
with values of c>=3 ,  the right side is negative.

II. conclusions?   a is at most 2, and c is at most 2.   So yea,
basically what Don said.

1, 1, 2, 3
1, 2, 2, 3
2, 2, 2, 2

On Aug 30, 5:05 pm, Don  wrote:
> There are three solutions, with d never exceeding 3.
> Don
>
> On Aug 30, 3:08 pm, him  wrote:
>
>
>
>
>
>
>
> > finding number of integral solution of the equation
>
> > ab+cd=a+d+b+c (1<=a<=b<=c<=d)   (any efficient method )

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

[algogeeks] Re: APTITUDE QUESTIONS

[icy`]

For the third one by hand, I was just trying to keep track of 1-2 of
the first digits for each section.

I broke into sections as follows  (^ to mean power here):

9! = (I just did this by hand, 1728x210=362880) ,  so we take  36.
10! to 19! =  approx 1^10 = 1
20! to 29! = approx 2^10 = 1024 = 10
30! to 39! = approx 3^10 =  3, 6, 9, 27, 81, 243, 72.., 216.., 63...,
189..  =  1
40! to 49! = 4^10 = 4, 16, 64, 25.., 10.., 4..  = this looked like a
pattern, the tenth one should be 1.. again   = 1
50! to 59! = 5^10 = 5, 25, 125, 60.. , 30.., 150.., 75..,  37.., 18..,
90  =  9
60! to 67! = 6^8 = 6, 36, 216, 126.. , 72..., 43.., 25..,  15..  = 1

so actually to correct what I had above, I was really looking to do
9*36  , (not 9*3=27), which gives  about 324,  or 3 for the first
digit.  This is just an approximation but it seems to work.

On Aug 30, 4:06 pm, kartik sachan  wrote:
> for 1st question ans will be a,b,e as (125)^1/3 is 5 sum is 8
> for 2nd question we see pattern in 7 power i.e 7,9,3,1 and this pattern
> reapeats for inerval of 4
> and second term of of any power of 7>=2 is 4
> so diff is 5
> ans will be 5
>
> how to find the ans of third question??

-- 
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: APTITUDE QUESTIONS

[icy`]

1. b2. c  3. a

I think ;P  I tried to do all by hand with some shortcuts, but i got 2
for the third one, so it' s a bit of a guess

On Aug 30, 10:27 am, abhishek  wrote:
> 1. Teacher asked the students to find the cube root of a natural
> number but she did not mention the base. Students assumed the base
> found the cube root. Each student got an integer. Find the sum of
> digits of that number.
> A. 0
> B. 1
> C. 6
> D. 7
> E. 8
>
> 2. What is the difference of last two digits of N where N=7^2010
>
> a.1
> b.3
> c.5
> d.7
> e.9
>
> 3.Find the first non Zero digit in 67!(Factorial)
>
> a.3
> b.4
> c.5
> d.6
> e.7

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

[icy`]

Other than making little loops and risking the fall on the first trip
down, I dont think the rope question has an answer.   NVIDIA just
wanted to see if you were suicidal  =D

On Aug 26, 3:36 pm, Piyush Grover  wrote:
> Cut the rope in 50mtrs and 100mtrs length.
>
> Make a small loop(of negligible length at one end of the 50 mtrs rope)
>
> Tie the other end of the rope at the top and from the loop end side pass the
> 100mtrs rope
> such that you have both the ends of 100mtrs rope in your end.
>
> now get down at 100mtrs peg point(~50 + 50 = 100 mtrs).
>
> Pull the 100 mtrs rope and tie it at the peg at 100mtrs height.
>
> Get down to the bottom.
>
> On Fri, Aug 26, 2011 at 7:29 PM, Himanshu Srivastava <
>
>
>
>
>
>
>
> himanshusri...@gmail.com> wrote:
> > lol :P
>
> > On Wed, Aug 10, 2011 at 11:35 PM, $hr! k@nth  wrote:
>
> >> Tie the rope at the top of the tower
> >> Climb down with the help of the rope up to 100 mt peg possItion
> >> Tie the rope to that peg, Climb up to the top of the tower with that rope.
> >> Now release the rope at the top and hold it. It ll take you down.:P
>
> >> On Wed, Aug 10, 2011 at 7:49 PM, varun pahwa 
> >> wrote:
>
> >>> make two ropes 50m and 100 meter. make a loop kind of thing with that now
> >>> you have two 50 mtr ropes so get down to 100 mtr point and tie loop rope 
> >>> in
> >>> downward now cut the loop at 100 mtr you have 100 mtr rope then move down
> >>> with the help of that. i hope i am clear.
>
> >>> On Mon, Aug 8, 2011 at 1:52 PM, Shachindra A C 
> >>> wrote:
>
>  tie the rope to the peg and hold the rope at a little less than 100m
>  point. Then jump.
>
>  On Mon, Aug 8, 2011 at 1:19 PM, Himanshu Srivastava <
>  himanshusri...@gmail.com> wrote:
>
> > @Dave oh i thought some logical concept willl be applied in that
> > case...it is ok!!!
> > thanks:)
>
> > On Fri, Aug 5, 2011 at 1:47 AM, Dave  wrote:
>
> >> @Himanshu: That is easy for any boy scout. :-) Tie the rope at the top
> >> of the tower. Then tie a sheepshank knot of a comfortable length in
> >> the rope and cut the middle strand inside the knot. Climb down the
> >> rope to the peg and tie the other end of the rope onto the peg. Then,
> >> while standing on or hanging from the peg, shake the upper rope to
> >> release the sheepshank knot. The upper end will fall down and you can
> >> climb the rest of the way down.
>
> >> Dave
>
> >> On Aug 4, 1:50 pm, Himanshu Srivastava 
> >> wrote:
> >> > suppose u tie the rope at 200mt height and now climb down to 100m
> >> > heightthen u tie the rope at that point then how will you open
> >> the rope
> >> > at point above 200mt where u have tied it earlier
>
> >> > On Thu, Aug 4, 2011 at 11:15 PM, mohit verma 
> >> wrote:
> >> > > can't we tie the rope where we are standing (at height of 200
> >> meter)?
>
> >> > > On Thu, Aug 4, 2011 at 10:26 PM, neeraja marathe <
> >> > > neeraja.marath...@gmail.com> wrote:
>
> >> > >> this was the puzzle asked to me in NVIDIA interview:
> >> > >> you are standing on top of a tower of ht 200 mt. .At 100 mt. ht .
> >> from
> >> > >> bottom of tower there is a peg where u can tie a rope. You have a
> >> rope
> >> > >> of length 150 mt. with you and using this rope you have to get
> >> down
> >> > >> the tower. you can not jump or there is nobody to help you. how
> >> will u
> >> > >> get down the tower??
>
> >> > >> --
> >> > >> 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.
>
> >> > > --
> >> > > 
> >> > > *MOHIT VERMA*
>
> >> > >  --
> >> > > 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: puzzle

[icy`]

I hope you dont mind that I respond to the original question about the
6x6 matrix.  As I understand it, all elements have to be either 1 or
-1, and product of *every* row and *every* column is 1  => how many
arrangements?

Now a bunch of you seem to think(nxn)  => 2^((n-1)^2)   gives the
answer, so I'm trying to give it a chance, but already I'm kinda
skeptical that the answer is over 33million .   I wrote a brute force
which I'm trying to test for small case  3x3.  Using the formula you
guys gave,   2^(2^2) == 2^(4) == 16.   My program outputs, for n=3:

[[-1, -1, nil], [-1, -1, nil], [nil, nil, nil]]
[[-1, nil, -1], [-1, nil, -1], [nil, nil, nil]]
[[nil, -1, -1], [nil, -1, -1], [nil, nil, nil]]
[[-1, -1, nil], [nil, nil, nil], [-1, -1, nil]]
[[-1, nil, -1], [nil, nil, nil], [-1, nil, -1]]
[[nil, -1, -1], [nil, nil, nil], [nil, -1, -1]]
[[nil, nil, nil], [-1, -1, nil], [-1, -1, nil]]
[[nil, nil, nil], [-1, nil, -1], [-1, nil, -1]]
[[nil, nil, nil], [nil, -1, -1], [nil, -1, -1]]
10

The nil is just a null value;  imagine it is the 1 in the problem.
The program gives 9 cases, and implied is the "empty set" case, which
would be all nil's, or in our case, contains no  -1's, but instead has
all 1's.  So together it gives 10.   I even drew up the cases so that
it would be easier to see -->  http://i56.tinypic.com/24b5kiq.png

So first I will ask, where are the missing 6 cases?

For each row, we choose 0, 2, 4, ...n-1's  to fill it with. If
we fill, for example, matrix[0][0]  and matrix[0][1] with  -1 , to
satisfy the first row requirement, this actually determines the
columns, do not forget.If we use this example for the simple 3x3
case, it is clearly seen that the first two columns must have
*exactly* one more -1  to fulfill the even requirement  (my output
shows this in case #1 and  case #4).

I think the formula does not cut enough of these intersections off.
I'm getting 962  for  n=6  , so    lol

icy`

On Aug 26, 10:34 am, Naren s  wrote:
> varun: can u explain it little further..
>
> On Wed, Aug 10, 2011 at 7:49 PM, varun pahwa wrote:
>
>
>
>
>
>
>
>
>
> > make two ropes 50m and 100 meter. make a loop kind of thing with that now
> > you have two 50 mtr ropes so get down to 100 mtr point and tie loop rope in
> > downward now cut the loop at 100 mtr you have 100 mtr rope then move down
> > with the help of that. i hope i am clear.
>
> > On Mon, Aug 8, 2011 at 1:52 PM, Shachindra A C wrote:
>
> >> tie the rope to the peg and hold the rope at a little less than 100m
> >> point. Then jump.
>
> >> On Mon, Aug 8, 2011 at 1:19 PM, Himanshu Srivastava <
> >> himanshusri...@gmail.com> wrote:
>
> >>> @Dave oh i thought some logical concept willl be applied in that
> >>> case...it is ok!!!
> >>> thanks:)
>
> >>> On Fri, Aug 5, 2011 at 1:47 AM, Dave  wrote:
>
> >>>> @Himanshu: That is easy for any boy scout. :-) Tie the rope at the top
> >>>> of the tower. Then tie a sheepshank knot of a comfortable length in
> >>>> the rope and cut the middle strand inside the knot. Climb down the
> >>>> rope to the peg and tie the other end of the rope onto the peg. Then,
> >>>> while standing on or hanging from the peg, shake the upper rope to
> >>>> release the sheepshank knot. The upper end will fall down and you can
> >>>> climb the rest of the way down.
>
> >>>> Dave
>
> >>>> On Aug 4, 1:50 pm, Himanshu Srivastava 
> >>>> wrote:
> >>>> > suppose u tie the rope at 200mt height and now climb down to 100m
> >>>> > heightthen u tie the rope at that point then how will you open the
> >>>> rope
> >>>> > at point above 200mt where u have tied it earlier
>
> >>>> > On Thu, Aug 4, 2011 at 11:15 PM, mohit verma 
> >>>> wrote:
> >>>> > > can't we tie the rope where we are standing (at height of 200
> >>>> meter)?
>
> >>>> > > On Thu, Aug 4, 2011 at 10:26 PM, neeraja marathe <
> >>>> > > neeraja.marath...@gmail.com> wrote:
>
> >>>> > >> this was the puzzle asked to me in NVIDIA interview:
> >>>> > >> you are standing on top of a tower of ht 200 mt. .At 100 mt. ht .
> >>>> from
> >>>> > >> bottom of tower there is a peg where u can tie a rope. You have a
> >>>> rope
> >>>> > >> of length 150 mt. with you and using this rope you have to get down
> >>>> > >> the tower. you can not jump 

[algogeeks] Re: find the complexity

[icy`]

isnt this logarithmic?regular loop  1..n   runs in  n/(1 step each
time)  -> O(n)
this loop  n/(k + k^2 each time) ->   ln(n)/ ( ln(k) + k ln(2) )  ->
ln(n-k) ->  O(ln(n))   or something like that ;P   I was going from
memory.  Please confirm, but I feel like it approaches logarithmic
speed.

On Aug 25, 1:46 pm, sachin sabbarwal  wrote:
> what will be the time complexity??
>
> sum=1
> for(k=0; k     sum=sum+sum;
> end
> print(sum);

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

[algogeeks] Re: Reverse dutch flag problem

[icy`]

not enough information, imo.   Tell me more about the given string...
is the string made up of consecutive integers/characters ?  Are there
always the same number of each character type?  And the goal is to
"braid" , like the hairstyle, as much as possible (if the previous
answer is no, all "braids" cannot be the same)?

On Aug 25, 1:50 pm, sachin sabbarwal  wrote:
> one solution might be:
> to traverse whole list counting no of zeros and 1's.
> and then make another string(or overwrite the same) with the required
> pattern,append any other characters(suppose all 0's exhausted and some 1's
> and 2's were left) left at the end.
> is there any better solution??
>
> On Sat, Aug 20, 2011 at 4:20 PM, sukran dhawan wrote:
>
>
>
>
>
>
>
> > i that .ink the soln for this problem is given in geeksforgeeks.com
>
> > On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal  wrote:
>
> >> Suppose we are given a string .
>
> >> Make it 012012012012 in O(n) time and O(1) space.
> >> Sanju
> >> :)
>
> >>  --
> >> 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: Find the non-duplicate element in sorted array in < O(n) time

[icy`]

my binary search method in Ruby is similar to Don's.   I tested with
array  [1,1,2,2,2,2,3,3,9,14,14] , to which the answer should be 9,
and now added what I call "fluff" (meaningless numbers) to either:
the left (300_000 zeroes at the head) , making it difficult for direct
approach;  the middle  (150_000 of each of the 3's and 14's  around
the 9 );  or the right  (300_000   18's added to the end).  I also had
it run each method 100 times.   I just hope the following formats
decently...

user system  totalreal
fluff on left
  direct   16.75   0.00  16.75 ( 16.753000)
  binary0.00   0.00   0.00 (  0.002000)

fluff in middle
  direct8.344000   0.00   8.344000 (  8.335000)
  binary6.844000   0.00   6.844000 (  6.846000)

fluff on right
  direct0.00   0.00   0.00 (  0.001000)
  binary0.00   0.00   0.00 (  0.003000)


As expected, the direct approach sucks when it hits a large n and the
singleton is near the end.   It actually does fairly well otherwise.

By the way, Don, I took "pairs" to mean it divides 2 evenly, and the
asker even gave an example with four 2's. (Assuming his result should
be 4, not 5,  typo ;P).  So your line about decreasing the midpoint
just once is not enough, and actually to increase binary performance,
a check should be made if  ar[mid]==ar[left] , also check  if
ar[mid]==ar[right], and if it does, like in my fluff examples , you
can save loads of time on useless checks.

@surender -- good question; I would think no, but binary search would
still return 3.   Direct approach would fail with default checks.  I
got the impression we were searching for a single[ton].

On Aug 25, 6:32 am, surender sanke  wrote:
> { 1,1,2,2,2,2,3,3,3,4,4,5,5}, here 3 is missing its pair, does this also
> comes under this problem?
>
> surender
>
>
>
>
>
>
>
> On Thu, Aug 25, 2011 at 8:12 AM, Dave  wrote:
> > @Shailesh: Sir, your response is unresponsive, because the original
> > poster specifically asked for a solution that was < O(n). Please don't
> > waste our time giving answers that so obviously do not meet the
> > problem statement.
>
> > Dave
>
> > On Aug 24, 6:33 pm, smb  wrote:
> > > XOR all the elements, the answer is the number you want.
>
> > > On Aug 24, 5:11 pm, Don  wrote:
>
> > > > I assume that "elements in pairs" means that each value occurs exactly
> > > > twice except for the one single.
> > > > This algorithm is O(log n) and is nonrecursive. Writing it recursively
> > > > would make it a couple of lines shorter, but because it is purely tail
> > > > recursion, that is not necessary.
>
> > > > // Given an array "a" of size elements in which all elements occur in
> > > > pairs except for one single item,
> > > > // find the single item and return its value.
> > > > int findSingle(int *a, int size)
> > > > {
> > > >   while(1)
> > > >   {
> > > >     // For an array of size 1, the only element is the single.
> > > >     if (size == 1) return a[0];
>
> > > >     // The logic below won't work for size three, but it is simple to
> > > > find the single.
> > > >     else if (size == 3) return (a[0] == a[1]) ? a[2] : a[0];
> > > >     else
> > > >     {
> > > >       // Pick the midpoint of the array
> > > >       int midpoint = size/2;
>
> > > >       // If we are looking at the second element of a pair, move back
> > > > to the first element
> > > >       if (a[midpoint] == a[midpoint-1]) --midpoint;
>
> > > >       // If midpoint is not a pair, that is the single.
> > > >       else if (a[midpoint] != a[midpoint+1]) return a[midpoint];
>
> > > >       // If midpoint is odd, look at left half of the array
> > > >       if (midpoint % 2) size = midpoint;
>
> > > >       else // If midpoint is even, look at the right half of the array
> > > >       {
> > > >         a += midpoint;
> > > >         size -= midpoint;
> > > >       }
> > > >     }
> > > >   }
>
> > > > }
>
> > > > On Aug 24, 4:49 am, atul purohit  wrote:
>
> > > > > Hi,
>
> > > > > A* sorted *integer array contains elements in pairs. All the pairs
> > are
> > > > > complete except one element whose pair is missing. Find that element.
>
> > > > > Ex.   { 1,1,2,2,2,2,3,3,4,5,5}
> > > > >  result = 5
>
> > > > > There is a standard solution which returns an XOR of all the
> > elements. But
> > > > > this needs O(n) time complexity. The person who asked me this
> > question said
> > > > > that this can be done in < O(n). Maybe we can eliminate some
> > elements.
> > > > > Anyone knows how to do this?
>
> > > > > Cheers,
> > > > > Atul- 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:

[algogeeks] Re: Apti

[icy`]

nice prakash.  Algorithm is definitely better than brute force.  But
here is brute force anyway, just go from 2 to square root of n ;P

I initially misread it and thought you were asking for ANY {c,d}  set
in which c,d are factors of n  (but not necessarily c*d = n)  .  That
wouldve been all of the factors  (12) ,  choose  2, unless I am
mistaken. 12 nCr 2 = 66.

#!/usr/bin/ruby -w
#how many unique sets {a,b} can be formed if a,b are factors of N and
axb=N
#  N = 24*33

n=792
#factors = [2,2,2,3,3,11]

#results
res=['1x792']
2.upto(Math.sqrt(n)) {|c|
next unless (c&1).zero? || c%3==0 || c%11==0
res< wrote:
> sorry I   wrote   them in different order:
> if (a,b) and (b,a) are considered same then answer is 12
> and if they are considered different it is 24.
>
> --
> Nikhil Gupta
> Indian Institute of Technology Roorkee,
> Roorkee, Uttarakhand,
> India , 247667
> Phone: +91 9634990161
> email:   nikgp...@iitr.ernet.in
>             nikhilg.8...@gmail.com

-- 
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: Longest palindrome

[icy`]

sorry, I meant to joke about  (0.5 * n^2)  ;P

On Aug 22, 4:46 pm, "icy`"  wrote:
> brute force...    http://codepad.org/D07BNo91    There are some
> checks to  help reduce O(n^2),  so I want to say..  O(1.5n) ?    =)
>
> #output for str = 'abaccddccefe'
> #ccddcc 6
>
> #for str = 'abraxyzarba'
> #a 1
>
> On Aug 22, 1:09 pm, uma  wrote:
>
>
>
>
>
>
>
> > can yo tell exactly , how the suffix tree is used for finding
> > palindromes?
>
> > On Aug 22, 3:58 am, WgpShashank  wrote:
>
> > > Hey Geeks I think question can be solved by many ways . some of the
> > > algorithms are i have implemented & aware of are ->
>
> > > 1st. Algo
> > >  Generate all palindromes (even & odd length ) of given string while keep
> > > tracking of their length in last just compare max (evenlength_palindrome ,
> > > oddlength_palindrome) .
> > >  Time Complexity O(N^2) where N is length of String
>
> > > 2nd . Algo. For Those Who are just saying Use DP :)
> > >   Find The LCS(Longest Common Sub-sequence of String (say s1)& reverse of
> > > String (say s2) ) It Involves  
> > >   DP to solve efficiently but guaranteed optimal solution
> > >   Time Complexity O(N^2) where N is length of String
> > >   Space  Complexity O(N^2)  for table
>
> > > 3rd. Use Suffix Tree ( Need to Work On It)  basic idea is to build the
> > > suffix tree of string & reverse string check no every node where suffix
> > > belongs to , the deepest common node will us longest palindrome in given
> > > string.
>
> > > Correct me if i missed something ?
>
> > > Thanks
> > > Shashank Mani
> > > Computer Science
> > > Birla Institute of Technology ,Mesra

-- 
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: Longest palindrome

[icy`]

brute force...http://codepad.org/D07BNo91 There are some
checks to  help reduce O(n^2),  so I want to say..  O(1.5n) ?=)

#output for str = 'abaccddccefe'
#ccddcc 6

#for str = 'abraxyzarba'
#a 1


On Aug 22, 1:09 pm, uma  wrote:
> can yo tell exactly , how the suffix tree is used for finding
> palindromes?
>
> On Aug 22, 3:58 am, WgpShashank  wrote:
>
>
>
>
>
>
>
> > Hey Geeks I think question can be solved by many ways . some of the
> > algorithms are i have implemented & aware of are ->
>
> > 1st. Algo
> >  Generate all palindromes (even & odd length ) of given string while keep
> > tracking of their length in last just compare max (evenlength_palindrome ,
> > oddlength_palindrome) .
> >  Time Complexity O(N^2) where N is length of String
>
> > 2nd . Algo. For Those Who are just saying Use DP :)
> >   Find The LCS(Longest Common Sub-sequence of String (say s1)& reverse of
> > String (say s2) ) It Involves  
> >   DP to solve efficiently but guaranteed optimal solution
> >   Time Complexity O(N^2) where N is length of String
> >   Space  Complexity O(N^2)  for table
>
> > 3rd. Use Suffix Tree ( Need to Work On It)  basic idea is to build the
> > suffix tree of string & reverse string check no every node where suffix
> > belongs to , the deepest common node will us longest palindrome in given
> > string.
>
> > Correct me if i missed something ?
>
> > Thanks
> > Shashank Mani
> > Computer Science
> > Birla Institute of Technology ,Mesra

-- 
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] crossing a bridge; running away from zombies (logic puzzle)

[icy`]

Hey everyone,
I recently joined this group, so I thought I'd add a short interview/
logic puzzle that I remember hearing.  Hopefully it wasnt already
said.  Part of the fun is the story, so here it goes...

Four people have been running away from a pack of zombies, and are now
injured in varying degrees.  It is already nighttime, and they have
come upon a bridge.  They must cross the bridge as fast as possible
before the pack of zombies comes upon them, but the bridge is very
dark, slippery, and cannot support much weight.  There is one
flashlight.  Rules:

* the bridge must be crossed with the flashlight,  only two people at
most.  A return trip must be made (the flashlight cannot be thrown
back, etc)
* the four people cross the bridge at different speeds:  1minute, 2
minutes, 5 min, and 10min.   A trip time is determined by the slowest
person.   So if the 1min crosses together with the 5min, the trip time
is 5min.
*if a person falls off the bridge, he/she goes to /dev/null;P

So what is the fastest way for everyone to cross the bridge, and how
long does that take?

~icy

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

[icy`]

#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated

arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89]
h = Hash.new(0)

arr.each {|n|
h[n]+=1
(puts n; break) if h[n]==2
}

#output
#67

I hope this meets the requirements ;P

On Aug 18, 3:15 pm, "*$*"  wrote:
> How to find duplicate element (only one element is repeated) from an array
> of unsorted positive integers..
> time complexity .. O(n)
> space .. o(1).

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

[algogeeks] Re: Question from Google interview

[icy`]

Well no, I would think it would match "Balls"  for him, since it is
greedy --> it would try to match as much as possible that works/is in
dict.  So I have to agree with Aditya here, but I would go from the
back/right to the left. So I would first get " round",  then hopefully
" are round"  and finally "Balls are round".

Now it gets tricky if the remaining left section cannot be broken into
words.  Then we'd have to backtrack once and take the next less-greedy
match, and try again.  If that fails, take even less greedier match ,
or backtrack yet again.

On Aug 18, 1:05 pm, Dave  wrote:
> @Aditya: You probably have to be a bit more careful than that. You
> can't add the space until both the first part is a word in the
> dictionary and the rest of the string can also be broken into words in
> the dictionary. Consider "Ballsareround." Your algorithm seems to put
> a space after the second "l", but then no initial part of "sareround"
> may be in your dictionary. In that case, you have to reject that space
> and continue until you get to a division point such that both the
> first part is in the dictionary and the second part can be broken into
> words. Sounds like a good place for recursion.
>
> Dave
>
> On Aug 18, 10:52 am, aditya kumar 
> wrote:
>
>
>
>
>
>
>
> > not sure abt the algo but we can think in terms of tokeninzing . ie go for
> > greedy method . greedy looks for maximum match . extract the token and match
> > with the dictionary word . if match found then add the additional space else
> > look for next token .
> > On Thu, Aug 18, 2011 at 9:10 PM, Navneet Gupta wrote:
>
> > > Given a string containing multiple words such that spaces between words is
> > > missing. Also, you have a dictionary containing valid words.
>
> > > Ex. "Thatwouldbefantastic"
>
> > > Output a string with proper spaces inserted.
>
> > > Output - "That would be fantastic"
>
> > > The case of words like bandwidth present can be discounted.
>
> > > --
> > > Regards,
> > > Navneet
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.

-- 
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: MS BRAINTEASR

[icy`]

hmm... interesting logic, but what about, for example,   8 people and
3 hats.   Why can't one of the five without hats also be unsure and
try to go swimming on one of the nights?

I was thinking, if they somehow know how many hats there are (writing
numbers in the sand or other cheating methods), it would be "n choose
c" days at most, if they try a combination every night.   But this can
further be simplified to just "n" at most, if exactly one new person
goes by himself at night.

One cheating method:  one man is a leader.   The leader chooses all
men he sees with hats and says "let's go swimming at midnight".   If
that does not work, the next night the same people (but without the
leader) go swimming at midnight.   Two nights.

So... I'm thinking  n days, since the men do not know how many hats
there are.  And if cheating is allowed, 1-2 days.  Remember, the
question did say "the men cannot *tell* each other..."=P



On Aug 18, 7:15 am, DheerajSharma  wrote:
> Case 1:
> when one person is wearing hat.The person wearing hat will see that no
> other is wearing hat.hence he must be wearing it.So she will take it
> off.hence one day
> Case 2:
> when two persons are wearing,first will think..that only second one is
> wearing..while second will think only first one is wearing.hence no
> one will go on first day.
> on the second day..when both will see the same thing..they will come
> to know..that they are also wearing hat..and making the second one
> confused ;)  hence..they both will go and take off hat on second day.
> Case 3:
> first person sees hat on two others.(same for other two). no one will
> go on first day.
> On second day..same situation..bt this time the person is still
> unsure..wether she is wearing hat or not..bcoz case 2 can happen..
> on third day..when same situation arises...they will come to
> know..that they are also wearing hat..hence..they will take it off on
> day 3.
> so on..
> so on..
> For C hats...C dayz...
>
> On Aug 18, 4:06 pm, DheerajSharma  wrote:
>
>
>
>
>
>
>
> > it would take c days to take off all the hats
>
> > On Aug 18, 3:51 pm, "pg@manit"  wrote:
>
> > > A bunch of men are on an island. A genie comes down and gathers
> > > everyone together and places a magical hat on some people’s heads
> > > (i.e., at least one person has a hat). The hat is magical: it can be
> > > seen by other people, but not by the wearer of the hat himself. To
> > > remove the hat, those (and only those who have a hat) must dunk
> > > themselves underwater at exactly midnight. If there are n people and c
> > > hats, how long does it take the men to remove the hats? The men cannot
> > > tell each other (in any way) that they have a hat.
> > > FOLLOW UP
> > > Prove that your solution is correct.

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