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