Total Moves For Bishop | InterviewBit | Solution Explained

Total Moves For Bishop! is an InterviewBit question under the math category. I explain the simulation based approach in detail, along with the intuitions on how to reach it. Problem Link.

0. Total Moves For Bishop: Problem Discussion

0.0. IO Format

  • input: 2 integers: A, B
  • output: an integer counting the number of moves possible a bishop placed at position (A, B)
  • constraint:
    • board size is 8*8
    • 1 <= A, B <= 8

0.1. Example

Take the case where the input is at (3, 4).

Total Moves For Bishop: example explanation
Total Moves For Bishop: example explanation

In this case, we have 11 total possibilities of where we could move next (marked in green), when we are at the black position.

1. Total Moves For Bishop: Observations & Logic

1.0. Intuitions

One way to solve this problem is to think about the mathematical constraints and create a formula to solve it. I however feel that its quite un-intuitive. What I did instead was simulation.

We know how a bishop moves – in diagonals. If we look at the change in indices, what does it come out to? We have 4 possible cases:

  • we go towards bottom right: i++, j++
  • we go towards top right: i++, j–
  • we go towards top left: i–, j–
  • we go towards bottom left: i–, j++

And that’s the entire logic!

2. Total Moves For Bishop: Optimized Implementation

2.0. Code

int Solution::solve(int A, int B) {
    int count = 0;
    for (int i = A, j = B; 1 <= i && i <= 8 && 1 <= j && j <= 8; i++, j++) count++;
    for (int i = A, j = B; 1 <= i && i <= 8 && 1 <= j && j <= 8; i++, j--) count++;
    for (int i = A, j = B; 1 <= i && i <= 8 && 1 <= j && j <= 8; i--, j--) count++;
    for (int i = A, j = B; 1 <= i && i <= 8 && 1 <= j && j <= 8; i--, j++) count++;
    return count - 4;
}

Note how we do the -4 at the end to not consider “reaching” the (A, B) state from (A, B) itself.

2.1. Complexity Analysis

  • Time: O(NM) = O(8*8) = O(1), where N, M are the dimensions of the board.
  • Space: O(1), since we only ever store temporary variables.
Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.