0
$\begingroup$

I need to test a cell on a 2D grid/matrix to see if it's diagonal numbers have a power of 2 in them.

Example:

    C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 R0: 00 01 02 03 04 05 06 07 08 09 R1: 10 11 12 13 14 15 16 17 18 19 R2: 20 21 22 23 24 25 26 27 28 29 R3: 30 31 32 33 34 35 36 37 38 39 R4: 40 41 42 43 44 45 46 47 48 49 R5: 50 51 52 53 54 55 56 57 58 59 

The size of the grid is known. The values in each cell are simply ((R*W)+C) where:

  • R=Row Number
  • W=Width of Grid
  • C=Column Number

Now let's pick two random cells:

  • C3R4 = 43. Has diagonal values of (10, 21, 32, 54) & (07, 16, 25, 34, 52) out of which 16 and 32 are powers of 2.
  • C8R1 = 18. Has no diagonal values that are powers of 2.

Required Result: f(x, y) = True or False.

Question:

  • Is there a way to detect the above without looping?
  • If this is not possible in a linear way, what would be the most efficient way to loop?
  • 1
    In the first line, you ask about $x^2$, but in the rest of the question, you ask about powers of 2. They are not the same thing. Which do you really mean? Can you edit the question accordingly, please.2012-07-26
  • 0
    How would your grid look if $C\geq 10$?2012-07-26
  • 0
    A simple way, without thinking would be to generate a list of squares or powers or etc, find their coordinates using $C = n \mod W$ and $R = \lfloor n/W \rfloor$ and then check if they are in the same diagonal. If they are, $|x_1 - x_2| = |y_1 - y_2|$. For a faster method, you'll have to clarify the question.2012-07-26
  • 0
    You probably wanted 'constant' instead of 'linear'. The most brute search of the diagonals would be 'linear'.2012-07-26
  • 0
    @KarolisJuodelė: Please excuse my lack of exposure to notation. How could I express the above as a function or algorithm?2012-07-26
  • 0
    That would be **for(int p = 1; p < N; p *= 2) if(abs(x - p mod W) == abs(y - p div W)) return true;**. Here N is the number of elements in the table and x, y are the arguments. Notice that this method has $\log_2(N)$ operations while the one draks suggested has $2W$, so you may have to think about which is faster for you.2012-07-27

1 Answers 1

0

If you assume $y$ to be even and $x\leq y$. Start at $(x,y)=10x+y$, the following values lie on

  • the antidiagonal $S_a=\{-x\leq z\leq y\; :\; 10(x+z)+(y-z)\}$ and
  • the diagonal $S_d=\{x\leq z\leq y\; :\; 10(x-z)+(y-z)\}$.

So there are $|S_d|+|S_a|-1=(y+x+1)+(x-y+1)=2x+2-1=2x+1\;$ values at all, which is linear ($\pm 1$'s because you count the value itself twice). Convert your values in binary form to see if it's a power of $2$.

  • 0
    Please excuse my lack of exposure to notation. The equations are greek to me. Could you explain the same as a function or algorithm please?2012-07-26
  • 0
    @RaheelKhan Pick your example $18=10*1+8$ (since I assumed $x\leq y$). So $x=1, y=8$. For the set of entries on antidiagonal $S_a$, you have the following entries: 1. $z=-x=\color{red}{-1}$, so $10(1+\color{red}{(-1)})+(8-\color{red}{(-1)})=10(0)+9=07$ 2. $z=0$, that $18$ again 3. $z=1$ gives $10(1+1)+(8-1)=27$ and so forth till $z=y=8$, which gives $10(1+8)+(8-8)=90$. Here I extended your grid in the row dimension. This is how you get the first set.2012-07-26
  • 0
    Thanks. Does your equation assume a square grid? I also did not understand `2x+1` since it does not take into account the height of the grid. I used Pythagoras to figure out the number of diagonal cells.2012-07-26