The problem statement is here. Observe that the $ (x, y) $ coordinate appears in the $ (x + y) ^{th} $ solid line. The $ n^{th} $ diagonal has $ 1 + 2 + 3 + ... + n $ elements before it, i.e. $ (x + y) ^{th} $ diagonal has $ \frac{(x+y)(x+y+1)}{2} $ elements before it. Add the $ x $ elements to it to get the point at coordinate $ (x+y) $. So the answer is $ \frac{(x+y)(x+y+1)}{2} + x $.
Monday, November 7, 2011
Friday, November 4, 2011
IIT Delhi MTech Interview Question: Find formula for coordinates
On a grid, the numbering is done as shown in the image below. Dotted lines go up and solid lines go down.
Find out the formula to describe number on grid given the standard $ (x, y) $ coordinate. Credit goes to my colleague Jignesh Parsana for the problem.
Update: I found that this is Cantor's Pairing Function as given at http://szudzik.com/ ElegantPairing.pdf
Find out the formula to describe number on grid given the standard $ (x, y) $ coordinate. Credit goes to my colleague Jignesh Parsana for the problem.
Update: I found that this is Cantor's Pairing Function as given at http://szudzik.com/
Labels:
Problem
Subscribe to:
Posts (Atom)