Re: [algogeeks] Re: Algo for Search in a 2D Matrix

[sunny agrawal]

@Anshu
pushing adjacent element will cause duplicate entries in the heap

try the following example:
1 2 3 4 5 6 7
2 3 4 5 6 7 8
3 4 5 6 7 8 9
4 5 6 7 8 9 10

so we also need to maintain a data structure that can efficiently tell that
which cell has been pushed into the heap already.

On Thu, Oct 13, 2011 at 11:35 AM, anshu mishra wrote:

> push the two adjacent element that is one right and below
>
> --
> 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.

Re: [algogeeks] Re: Algo for Search in a 2D Matrix

[anshu mishra]

push the two adjacent element that is one right and below

-- 
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] Re: Algo for Search in a 2D Matrix

[anshu mishra]

If O(k*logk) solution is acceptable then it is very simple.

maintain a min heap.
push a[0][0],
i = 0;
while ( i < k)
{
pop an element. ---> O(log(i)) --> coz number of elements in heap is i;
push the two adjacent element that is one right and right below. --->
O(log(i));
i++;
}
last element popped will be answer.

size of heap at every iteration will increase by one coz we are inserting
two elements and removing one element at every iteration.

If anyone has doubt on correctness of this solution can ask.

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

[Abhishek Khanna]

@Ankur
In a trie u first insert the first word ..take the second word..If its
not
present in the trie u insert it else remove it from original string:
removing the word requires left shifting the entire string

Alternatively u store the elements in a trie in the initial string and
terminate it with '\0' and return it:
how do we reconstruct the string after creating the trie as we do not
know the sequence of words
and also some words will contain other words as prefixes.

On Oct 11, 2:14 am, Ankur Garg  wrote:
> @Sunny..How do u intend to store them in a Tree ? Can you explain ?
>
> In a trie u first insert the first word ..take the second word..If its not
> present in the trie u insert it else remove it from original string
> .Alternatively u store the elements in a trie in the initial string and
> terminate it with '\0' and return it . In the worst case trie will take O(n)
> space where n is the no of letters in the string . and Traversal  and
> creation and search too will take O(n).
>
> How abt Balanced Binary Tree ?
>
> On Tue, Oct 11, 2011 at 12:38 AM, 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.

-- 
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] Re: Find the later version

[Amol Sharma]

scan the numbers as string
if both strings dont have equal numbers of dots then add trailing 0's with
dots to the string with less number of dots

now divide both the string into 2 equal halves compare the left half .if
unequal then divide recursively and again compare left of the divided
string.if equal the compare the right half and divide and
compare it recursivelythis will reduce the complexity to logn.


--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad
 






On Thu, Oct 13, 2011 at 2:21 AM, sravanreddy001 wrote:

> it is expected that the version is given as string, in that case, atoi()
> has be used to convert string to int

-- 
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] Stone Game

[sunny agrawal]

your solution seems to be the right one... testcases may be faulty

try submitting here  both the
codes


On Thu, Oct 13, 2011 at 5:44 AM, Hatta  wrote:

> being accepted doesn't imply in being correct
> maybe I'm wrong but given this Test Case I think BOB wins:
>
> 3
> 1 3 2
>
> didn't he (bob!)?
>
>
>
> On Wed, Oct 12, 2011 at 6:53 PM, Wladimir Tavares 
> wrote:
> > In the problem Stone Game , I did the following algorithm that was
> accepted
> > by spoj:
> >
> > #include
> > int main(){
> >
> >   int n,t,i,j,cont;
> >
> >   scanf("%d",&t);
> >
> >   while(t--){
> > scanf("%d",&n);
> > cont=0;
> > for(i=1;i<=n;i++)
> > {
> >   scanf("%d",&j);
> >   if(j>=i){
> > cont+=j/i;
> >   }
> > }
> >
> >   if(cont%2==0)
> > printf("BOB\n");
> >   else
> >  printf("ALICE\n");
> >
> > }
> > return 0;
> > }
> >
> > A friend of mine made the following code, which was also accepted by
> spoj:
> >
> > #include 
> > #include 
> > #include 
> > #include 
> > #include 
> > #include 
> >
> > using namespace std;
> >
> >
> >
> > int main(){
> >   int n;
> >   cin >> n;
> >   while(n--)
> >   cout << "ALICE" << endl;
> >   return 0;
> > }
> >
> >
> >
> > I could not prove because Alice always wins. Does anyone know how to
> prove
> > this fact?
> >
> >
> >
> > Wladimir Araujo Tavares
> > Federal University of Ceará
> > Homepage | Maratona |
> >
> >
> >
> >
> > --
> > 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.
> >
>
>
>
> --
> Hatta
>
> --
> 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.

Re: [algogeeks] Stone Game

[Hatta]

being accepted doesn't imply in being correct
maybe I'm wrong but given this Test Case I think BOB wins:

3
1 3 2

didn't he (bob!)?



On Wed, Oct 12, 2011 at 6:53 PM, Wladimir Tavares  wrote:
> In the problem Stone Game , I did the following algorithm that was accepted
> by spoj:
>
> #include
> int main(){
>
>   int n,t,i,j,cont;
>
>   scanf("%d",&t);
>
>   while(t--){
> scanf("%d",&n);
> cont=0;
> for(i=1;i<=n;i++)
> {
>   scanf("%d",&j);
>   if(j>=i){
> cont+=j/i;
>   }
> }
>
>   if(cont%2==0)
> printf("BOB\n");
>   else
>  printf("ALICE\n");
>
> }
> return 0;
> }
>
> A friend of mine made the following code, which was also accepted by spoj:
>
> #include 
> #include 
> #include 
> #include 
> #include 
> #include 
>
> using namespace std;
>
>
>
> int main(){
>   int n;
>   cin >> n;
>   while(n--)
>   cout << "ALICE" << endl;
>   return 0;
> }
>
>
>
> I could not prove because Alice always wins. Does anyone know how to prove
> this fact?
>
>
>
> Wladimir Araujo Tavares
> Federal University of Ceará
> Homepage | Maratona |
>
>
>
>
> --
> 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.
>



-- 
Hatta

-- 
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] Stone Game

[Wladimir Tavares]

In the problem Stone Game  , I did the
following algorithm that was accepted by spoj:

#include
int main(){

  int n,t,i,j,cont;

  scanf("%d",&t);

  while(t--){
scanf("%d",&n);
cont=0;
for(i=1;i<=n;i++)
{
  scanf("%d",&j);
  if(j>=i){
cont+=j/i;
  }
}

  if(cont%2==0)
printf("BOB\n");
  else
 printf("ALICE\n");

}
return 0;
}


A friend of mine made ​​the following code, which was also accepted by spoj:

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;



int main(){
int n;
cin >> n;
while(n--)
cout << "ALICE" << endl;
return 0;
}



I could not prove because Alice always wins. Does anyone know how to prove
this fact?





Wladimir Araujo Tavares
*Federal University of Ceará 
Homepage  |
Maratona|
*

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

[Gene]

This is true when memoization is being used to merely improve
asymptotic efficiency of a single computation. (As you say, it's a
nice technique for DP, when you can often just remember one or a few
previous rows of results.)

However this is not the only use.  General memoization maintains
values persistently.  In this case memoized fib(n) will cost O(n) for
the first call.  Afterward any call for fib(i), i <= n will run in
constant time.  If there are many similar-valued calls to fib, this is
a big deal.

On Oct 11, 7:15 pm, Vandana Bachani  wrote:
> Hi Arvind,
> For the fibonacci series, we need to memoize only the the last 2 fibonacci
> numbers.
> We can even avoid recursion... So our regular fibonacci algorithm is the
> simplest example of a dynamic programming algorithm with memoization.
>
> To find nth fibonacci number:
>
> int p = 0, q = 1, f;
> for (int i  = 1; i <= n; i++)
> {
>   f = p + q;
>   p = q;
>   q = f;
>
> }
>
> But as gene mentioned, in complex programs involving dynamic programming we
> might need to access more than 1 or 2 previously obtained values. To reduce
> the burden of recalculating old values, we preserve them in a
> hash/table/array, as the case might be and access them directly from there.
> One of the most important properties of dynamic programming is that the
> solutions to sub-problems are reused, which can be achieved with
> memoization.
>
> -Vandana
>
>
>
> On Tue, Oct 11, 2011 at 3:17 AM, arvind kumar  wrote:
> > ya ya,realy sorry..typo!its MEMOIZATION.
>
> > On Mon, Oct 10, 2011 at 10:56 PM, Ankur Garg  wrote:
>
> >> Memoization ?
>
> >> On Mon, Oct 10, 2011 at 6:34 PM, arvind kumar wrote:
>
> >>> Can anyone tell me how to go about with the memorization technique to
> >>> retrieve values from already stored values,in case of eveluating
> >>> sequences(fibonacci series,etc).?
>
> >>> --
> >>> 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.- Hide quoted text -
>
> - Show quoted text -

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

[algogeeks] Re: Find the later version

[sravanreddy001]

it is expected that the version is given as string, in that case, atoi() has 
be used to convert string to int.

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

[algogeeks] Re: How to Solve This

[Gene]

First note:

0 * 3 = 0
7 * 3 = 21
4 * 3 = 12
1 * 3 = 3
8 * 3 = 24
5 * 3 = 15
2 * 3 = 6
9 * 3 = 27
6 * 3 = 18
3 * 3 = 9

Important is that the final digits of each line count 0 to 9.

Now you can build an answer right to left.

Example: 123.

Check the table to get the rightmost 1.
7 * 123 =  861

Now you need to add ...50 to make the 10's digit a 1.  So

50 * 123 = 6150 + 861 = 7011

And now add 100 to get the third 1...
700 * 123 = 86,100 + 7011 = 93,111

Following this pattern:
6000 * 123 = 738,000 + 93,111 = 831,111
6 * 123 =   7,380,000 + 831,111 = 8,211,111
30 * 123 = 36,900,000 + 8,211,111 = 45,111,111

Okay.  That's enough.  We stop when the carry digits finally turn out
to be all 1's.

In a program once we've arranged for a rightmost 1 we can shift it out
of the calculation by dividing everything by 10.  At the same time we
can shift out the trailing zeros in the multiplicands.

So here's a quick implementation. Sorry in advance for mistakes, but
it seems to be working okay:

#include 

// If x is all 1's (including zero of them), return
// how many there are.  Otherwise return ~0u.
unsigned all_ones(unsigned x)
{
  unsigned n = 0;
  while (x) {
if (x % 10 != 1)
  return ~0u;
x /= 10;
++n;
  }
  return n;
}

// A table s.t. (x + 3 * mul[x % 10]) ends in 1.
unsigned mul[] = {7,0,3,6,9,2,5,8,1,4};

// Return n s.t. x divides sum_{i=0 to n-1} 10^i .
// x must be congruent to 3 mod 10.
unsigned ones(unsigned x)
{
  unsigned n, carry = x;
  for (n = 0; all_ones(carry) == ~0u; n++) {
carry = (carry + mul[carry % 10] * x) / 10;
// printf("%d\n", carry);
  }
  return n + all_ones(carry);
}

int main(void)
{
  unsigned x;
  if (scanf("%u", &x) == 1 && x % 10 == 3)
printf("%u divides %u 1's\n", x, ones(x));
  return 0;
}

On Oct 10, 9:20 am, VIHARRI  wrote:
> For every number that has 3 in its units place has one multiple which
> has all one's i.e. 111 is
> such multiple and 13 has a multiple 11. Write a program to find
> such multiple for any
> number that has 3 at its units place.

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

[Gene]

As others have said, you have not completely specified the problem.
If you always have exactly 4 base 10 numbers separated by dots, and
you are working in C or C++ then you can use sscanf to get the numbers
and compare them:

// Return:
//  positive if version s1 is an earlier version than s2,
//  negative if s2 is earlier than s1
//  zero if they're the same version
#define VERSION_CMP_ERROR INT_MAX
int version_cmp(char *s1, char *s2)
{
  int i, v1[4], v2[4];
  if (sscanf(s1, "%u.%u.%u.%u", v1+0, v1+1, v1+2, v1+3) != 4 ||
  sscanf(s2, "%u.%u.%u.%u", v2+0, v2+1, v2+2, v2+3) != 4)
   return VERSION_CMP_ERROR;
  for (i = 0; i < 4; i++)
if (v1[i] != v2[i])
  return v2[i] - v1[i];
  return 0;
}

On Oct 11, 4:52 am, "bagaria.ka...@gmail.com"
 wrote:
> Given two strings describing the version of a particular software need to
> find the later version.
>
> For eg.
> 1st string = "1.2.4.5"
> 2nd string="1.2.3.5"
>
> 1st string is the later one.
>
> Can be done using traversing the string and comparing each character one
> after the another. Looking for a better solution with lesser complexity.
>
> --
> Thanks and Regards
>
> *Karan Bagaria*
> *MCA Final Year*
> Training and Placement Representative
> *NIT Durgapur*

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

[algogeeks] Re: How to Solve This

[vikas]

well , I tried to solve it from Maths

though half way through only :(

N = number required i.e. (10^k -1)/9
given n = 10x + 3

by eq

(10x + 3) * m = N= (10^k - 1)/9

implies

k = 2log 3 + log m + log(10x + 3)
i.e.
k > 1 + log n

This gives the lowerbound on minimum number of 1 to be start with, but
seeing the logarithmic eq, this simply seems not to add much value.

can any one figure out for upper bound ?



On Oct 12, 5:18 pm, anshu mishra  wrote:
> @amol
> I was not sure that for every number that has 3 in its unit place has one
> multiple which has all one. So I used that is if the remainder is coming
> that already appeared stop there coz it will make stuck in a loop.
> for ex. remainders are
> 1 3 19 23 37 1 3 19  that will repeat.
>
> but it in this case u can remove the set. Code will look more simpler.
>
> string all1Multiple(int x)
> {
> string s;
> int r=1;
> do
> {
> s += '1';
> r = r % x;
> r = r * 10 + 1;
>
> } while(r != 1);
> return s;
> }

-- 
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] Re: Algo for Search in a 2D Matrix

[ravindra patel]

Here is a solution based on the fact that the matrix is quiet similar to a
min heap. each cell is smaller than its down and right neighbor.

Note :- This solution modifies the original matrix.

Algo -
repeat k-1 times
set a[0][0] = INFINITY
minHeapify the Matrix (see implementation below). This will create
holes in the matrix that can be filled with INFINITY.
return a[0][0];

- Complexity O(k*(m+n))  for a m x n matrix.
- Here is a java implementation of the same.

public static int kthSmallest(int[][] a, int k)
{
final int INF = Integer.MAX_VALUE;

int rows = a.length;
int cols = a[0].length;

if (k > rows*cols)
{
System.out.println("Matrix has less than " + k + " elements.");
return INF;
}

while(--k > 0)
{
a[0][0] = INF; int i=0, j=0;

// MinHeapify the matrix again.

while(true)
{
int down = INF; int right = INF;

if(i < rows-1)   down = a[i+1][j];
if(j < cols-1)right = a[i][j+1];

if((down == INF) &&(right == INF))
break;

if(down < right)
{
int temp = a[i][j];
a[i][j] = down;
a[i+1][j] = temp;
i++;
}
else
{
int temp = a[i][j];
a[i][j] = right;
a[i][j+1] = temp;
j++;
}
}
}
return a[0][0];
}


Feedback welcome :-)
- Ravindra


On Wed, Oct 12, 2011 at 8:18 PM, sunny agrawal wrote:

> i dont think k*k submatrix approach works at all
> what if k >=n size of submatrix will be n*n, which is matrix itself
> heap seems to be a good approach with a coloring scheme that helps in
> avoiding duplicates in heap ??
>
>
> On Wed, Oct 12, 2011 at 7:18 PM, vikas wrote:
>
>> @Shiva, not necessarily in upper half
>>
>> take the transpose of example put by Dave and see by yourself
>>
>> There are few observations for this question:
>>1. kth smallest will always lie in first k*k matrix
>>2. it wont be part of sqrt(k)*sqrt(k) matrix
>>  Thus rest all need to be searched recursively to find the element
>>
>> Any suggestions ?
>>
>>
>> On Oct 10, 10:55 am, "shiva@Algo"  wrote:
>> > id we see the pattern then we can easily find that the kth smallest
>> element
>> > lie on the upper half of the k*k submatrix(on the upperleft corner )
>> > we can do search on  (k*k)/2 elements to find that
>> >
>> > On Mon, Oct 10, 2011 at 10:36 AM, Dave  wrote:
>> > > @Shubham: So if the matrix is
>> > > 1 2
>> > > 3 4
>> > > and you want the 2nd smallest, are you saying that it is 4?
>> >
>> > > Dave
>> >
>> > > On Oct 9, 7:40 pm, shubham goyal  wrote:
>> > > > im assuming it be a square matrix
>> > > > then kth smallest element will be in a first k*k sub matrix.
>> > > > jst look for smallest element in the diagonal of this matrix.
>> > > > it will give the kth smallest element .
>> >
>> > > > On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg 
>> > > wrote:
>> > > > > Given a 2D matrix which is both row wise and column wise sorted.
>> > > Propose an
>> > > > > algorithm for finding the kth smallest element in it in least time
>> > > > > complexity
>> >
>> > > > > A General Max Heap can be used with k space and n+klogk complexity
>> >
>> > > > > Any other solution  or even a way by which we dont scan the whole
>> > > matrix to
>> > > > > find the solution ?
>> >
>> > > > > I
>> >
>> > > > > --
>> > > > > You received this message because you are subscribed to the Google
>> > > Groups
>> > > > > "Algorithm Geeks" group.
>> > > > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > > > To unsubscribe from this group, send email to
>> > > > > algogeeks+unsubscr...@googlegroups.com.
>> > > > > For more options, visit this group at
>> > > > >http://groups.google.com/group/algogeeks?hl=en.
>> >
>> > > --
>> > > You received this message because you are subscribed to the Google
>> Groups
>> > > "Algorithm Geeks" group.
>> > > To post to this group, send email to algogeeks@googlegroups.com.
>> > > To unsubscribe from this group, send email to
>> > > algogeeks+unsubscr...@googlegroups.com.
>> > > For more options, visit this group at
>> > >http://groups.google.com/group/algogeeks?hl=en.
>>
>> --
>> 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 subs

Re: [algogeeks] Re: Algo for Search in a 2D Matrix

[sunny agrawal]

i dont think k*k submatrix approach works at all
what if k >=n size of submatrix will be n*n, which is matrix itself
heap seems to be a good approach with a coloring scheme that helps in
avoiding duplicates in heap ??

On Wed, Oct 12, 2011 at 7:18 PM, vikas  wrote:

> @Shiva, not necessarily in upper half
>
> take the transpose of example put by Dave and see by yourself
>
> There are few observations for this question:
>1. kth smallest will always lie in first k*k matrix
>2. it wont be part of sqrt(k)*sqrt(k) matrix
>  Thus rest all need to be searched recursively to find the element
>
> Any suggestions ?
>
>
> On Oct 10, 10:55 am, "shiva@Algo"  wrote:
> > id we see the pattern then we can easily find that the kth smallest
> element
> > lie on the upper half of the k*k submatrix(on the upperleft corner )
> > we can do search on  (k*k)/2 elements to find that
> >
> > On Mon, Oct 10, 2011 at 10:36 AM, Dave  wrote:
> > > @Shubham: So if the matrix is
> > > 1 2
> > > 3 4
> > > and you want the 2nd smallest, are you saying that it is 4?
> >
> > > Dave
> >
> > > On Oct 9, 7:40 pm, shubham goyal  wrote:
> > > > im assuming it be a square matrix
> > > > then kth smallest element will be in a first k*k sub matrix.
> > > > jst look for smallest element in the diagonal of this matrix.
> > > > it will give the kth smallest element .
> >
> > > > On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg 
> > > wrote:
> > > > > Given a 2D matrix which is both row wise and column wise sorted.
> > > Propose an
> > > > > algorithm for finding the kth smallest element in it in least time
> > > > > complexity
> >
> > > > > A General Max Heap can be used with k space and n+klogk complexity
> >
> > > > > Any other solution  or even a way by which we dont scan the whole
> > > matrix to
> > > > > find the solution ?
> >
> > > > > I
> >
> > > > > --
> > > > > You received this message because you are subscribed to the Google
> > > Groups
> > > > > "Algorithm Geeks" group.
> > > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > > To unsubscribe from this group, send email to
> > > > > algogeeks+unsubscr...@googlegroups.com.
> > > > > For more options, visit this group at
> > > > >http://groups.google.com/group/algogeeks?hl=en.
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> 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] Re: Algo for Search in a 2D Matrix

[vikas]

@Shiva, not necessarily in upper half

take the transpose of example put by Dave and see by yourself

There are few observations for this question:
1. kth smallest will always lie in first k*k matrix
2. it wont be part of sqrt(k)*sqrt(k) matrix
  Thus rest all need to be searched recursively to find the element

Any suggestions ?


On Oct 10, 10:55 am, "shiva@Algo"  wrote:
> id we see the pattern then we can easily find that the kth smallest element
> lie on the upper half of the k*k submatrix(on the upperleft corner )
> we can do search on  (k*k)/2 elements to find that
>
> On Mon, Oct 10, 2011 at 10:36 AM, Dave  wrote:
> > @Shubham: So if the matrix is
> > 1 2
> > 3 4
> > and you want the 2nd smallest, are you saying that it is 4?
>
> > Dave
>
> > On Oct 9, 7:40 pm, shubham goyal  wrote:
> > > im assuming it be a square matrix
> > > then kth smallest element will be in a first k*k sub matrix.
> > > jst look for smallest element in the diagonal of this matrix.
> > > it will give the kth smallest element .
>
> > > On Mon, Oct 10, 2011 at 4:45 AM, Ankur Garg 
> > wrote:
> > > > Given a 2D matrix which is both row wise and column wise sorted.
> > Propose an
> > > > algorithm for finding the kth smallest element in it in least time
> > > > complexity
>
> > > > A General Max Heap can be used with k space and n+klogk complexity
>
> > > > Any other solution  or even a way by which we dont scan the whole
> > matrix to
> > > > find the solution ?
>
> > > > I
>
> > > > --
> > > > You received this message because you are subscribed to the Google
> > Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to algogeeks@googlegroups.com.
> > > > To unsubscribe from this group, send email to
> > > > algogeeks+unsubscr...@googlegroups.com.
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.

-- 
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] Re: Find the later version

[mohit verma]

WE CAN USE RADIX SORT TO FIND THE MAX VERSION :TRAVERSING FROM LEFT TO RIGHT
(RADIX WILL BE NUMBERS BETWEEN THE POINTS).
It will reduce the search space too.


On Tue, Oct 11, 2011 at 1:58 AM, sumit kumar pathak
wrote:

> *
> *regards
> - Sumit Kumar Pathak
> (Sumit/ Pathak/ SKP ...)
> *Smile is only good contagious thing.*
> *Spread it*!
>
>
>
> On Tue, Oct 11, 2011 at 11:22 AM, DIPANKAR DUTTA <
> dutta.dipanka...@gmail.com> wrote:
>
>> what's happen if the versions are not in same length..
>>
>> For example
>>
>> v1: 1.1.1.133.2
>> v2: 1.2
>> v3: 1.2.3.4..333
>> v4: 1.2.3.4.5554.222
>> v5: 1.3.2.2.2.2.2.2.2.2.2.2.2.2
>>
>> It implies we must be scan from left side one by one ...
>>
>> In general the we make a some sort of lexical comparison where each
>> character is a number and separated by number ..
>>
>>  the problem definition is as :
>>
>> let V1,V2,V3 ...Vn be the n version
>>
>> let S={1,2,3...n} ,index=0
>>
>> Latest[S,index]= return Vi if { Max(ALL Vi[k] where i belongs to S )}
>> is a singleton, else
>>  =  return Latest[ set of all index belongs to  { Max(ALL
>> Vi[k] where i belongs to S )}, index+1 ]
>>
>>
>>
>>
>>
>> On 10/11/11, Dave  wrote:
>> > @Karen: It is more complicated than scanning character by character.
>> > E.g., "1.10.3" is older than "1.9.7". I think
>>
>
> 
>
>> you need to parse the
>> > numbers between the dots and compare them
>>
> 
>
> simple, easier and correct way.
> points:
>   -  compare left to right (ofcourse) each version being vector of numbers
>   - for diffrent size, assume extra ones to be zero while comapring (no
> need to store trailing zeros)
>
>
>
>>  one by one. Thus, in the
>> > above example, 1 compares equal to 1, so you keep scanning. Then 10
>> > compares greater than 9 so the first string is number of the newer
>> > version. I did this many years ago in a csh install script for a unix
>> > product.
>> >
>> > Dave
>> >
>> > On Oct 10, 9:52 pm, "bagaria.ka...@gmail.com"
>> >  wrote:
>> >> Given two strings describing the version of a particular software need
>> to
>> >> find the later version.
>> >>
>> >> For eg.
>> >> 1st string = "1.2.4.5"
>> >> 2nd string="1.2.3.5"
>> >>
>> >> 1st string is the later one.
>> >>
>> >> Can be done using traversing the string and comparing each character
>> one
>> >> after the another. Looking for a better solution with lesser
>> complexity.
>> >>
>> >> --
>> >> Thanks and Regards
>> >>
>> >> *Karan Bagaria*
>> >> *MCA Final Year*
>> >> Training and Placement Representative
>> >> *NIT Durgapur*
>> >
>> > --
>> > You received this message because you are subscribed to the Google
>> Groups
>> > "Algorithm Geeks" group.
>> > To post to this group, send email to algogeeks@googlegroups.com.
>> > To unsubscribe from this group, send email to
>> > algogeeks+unsubscr...@googlegroups.com.
>> > For more options, visit this group at
>> > http://groups.google.com/group/algogeeks?hl=en.
>> >
>> >
>>
>>
>> --
>> Thanks and Regards,
>> --
>> **DIPANKAR DUTTA
>> Software Development Engineer
>> Xen Server - OpenStack Development Team (DataCenter and Cloud)
>>
>> Citrix R&D India Pvt Ltd
>> 69/3, Millers Road, Bangalore – 560052
>> Phone: +91 8147830733
>> Office: Extn: 16429
>> Email: dipankar.du...@citrix.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.
>>
>>
>  --
> 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.

Re: [algogeeks] How to Solve This

[anshu mishra]

@amol
I was not sure that for every number that has 3 in its unit place has one
multiple which has all one. So I used that is if the remainder is coming
that already appeared stop there coz it will make stuck in a loop.
for ex. remainders are
1 3 19 23 37 1 3 19  that will repeat.

but it in this case u can remove the set. Code will look more simpler.

string all1Multiple(int x)
{
string s;
int r=1;
do
{
s += '1';
r = r % x;
r = r * 10 + 1;
} while(r != 1);
return s;
}

-- 
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] How to Solve This

[Amol Sharma]

@anshu- your code works fine.but can you plz explain how you concluded
this codei mean what's the logic behind to check   myset.size() > psize
?? ...as you are assuming  that it will be increase string and check
until this condition satisfies ??
--


Amol Sharma
Third Year Student
Computer Science and Engineering
MNNIT Allahabad







On Wed, Oct 12, 2011 at 10:29 AM, shady  wrote:

> thanks a lot for replying to the post... but try posting algorithm rather
> than actual code...
>
> On Mon, Oct 10, 2011 at 2:17 PM, anshu mishra 
> wrote:
>
>> string all1Multiple(int x)
>> {
>> string s;
>> set mySet;
>> mySet.push(0);
>> int psize, r=1;
>> do
>> {
>> psize = mySet.size();
>> s += '1';
>> r = r % x;
>> mySet.push(r);
>> r = r * 10 + 1;
>> } while(mySet.size() > psize);
>>
>> if (r != 1) return "not Possible";
>> return s;
>>
>> }
>>
>> --
>> 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.