Given a N x N chessboard and the position of X bishops on it, the task is to calculate the count of pairs of bishops such that they attack each other. Note that while considering a pair of bishops, all the other bishops are not considered to be on the board.
Example:
Input: N = 5, bishops[][] = {{2, 1}, {3, 2}, {2, 3}}
Output: 2
Explanation: The bishops on the positions {2, 1} and {3, 2} and bishops on the positions {3, 2} and {2, 3} attack each other.Input: N = 10, bishops[][] = {{1, 1}, {1, 5}, {3, 3}, {5, 1}, {5, 5}}
Output: 6
Approach: The given problem can be solved using basic combinatorics. Since all the bishops that lie on the same diagonal will attack each other, all possible pairs of bishops that are on the same diagonal that can be formed will attack each other. Therefore, traverse the matrix for all diagonals in both left and right directions and count the number of bishops on the current diagonal in a variable cnt. Now for each diagonal, the number of attacking bishops will be cntC2.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;int board[20][20];int countPairs(int N, vector<pair<int, int> > bishops){ // Set all bits to 0 memset(board, 0, sizeof(board)); // Set all the bits // having bishop to 1 for (int i = 0; i < bishops.size(); i++) { board[bishops[i].first][bishops[i].second] = 1; } // Stores the final answer int ans = 0; // Loop to traverse the matrix // diagonally in left direction for (int s = 2; s <= 2 * N; s++) { // Stores count of bishop // in the current diagonal int cnt = 0; for (int i = 1, j = s - i; max(i, j) <= min(N, s - 1); i++, j--) { if (board[j][i - j] == 1) // Update cnt cnt++; } // Update the answer if (cnt > 1) ans += ((cnt + 1) * cnt) / 2; } // Loop to traverse the matrix // diagonally in right direction for (int s = 2; s <= 2 * N; s++) { // Stores count of bishop // in the current diagonal int cnt = 0; for (int i = 1, j = s - i; max(i, j) <= min(N, s - 1); i++, j--) { if (board[i][N - j + 1] == 1) // Update cnt cnt++; } // Update the answer if (cnt > 1) ans += ((cnt + 1) * cnt) / 2; } // Return answer return ans;}// Driver codeint main(){ int N = 10; vector<pair<int, int> > bishops = { { 1, 1 }, { 1, 5 }, { 3, 3 }, { 5, 1 }, { 5, 5 } }; cout << countPairs(N, bishops); return 0;} |
Java
import java.util.*;class GFG{ static int [][]board = new int[20][20]; static int countPairs(int N, int[][] bishops) { // Set all the bits // having bishop to 1 for (int i = 0; i < bishops.length; i++) { board[bishops[i][0]][bishops[i][1]] = 1; } // Stores the final answer int ans = 0; // Loop to traverse the matrix // diagonally in left direction for (int s = 2; s <= 2 * N; s++) { // Stores count of bishop // in the current diagonal int cnt = 0; for (int i = 1, j = s - i; Math.max(i, j) <= Math.min(N, s - 1)&&i-j>0; i++, j--) { if (board[j][i - j] == 1) // Update cnt cnt++; } // Update the answer if (cnt > 1) ans += ((cnt + 1) * cnt) / 2; } // Loop to traverse the matrix // diagonally in right direction for (int s = 2; s <= 2 * N; s++) { // Stores count of bishop // in the current diagonal int cnt = 0; for (int i = 1, j = s - i; Math.max(i, j) <= Math.min(N, s - 1); i++, j--) { if (board[i][N - j + 1] == 1) // Update cnt cnt++; } // Update the answer if (cnt > 1) ans += ((cnt + 1) * cnt) / 2; } // Return answer return ans; } // Driver code public static void main(String[] args) { int N = 10; int[][] bishops = { { 1, 1 }, { 1, 5 }, { 3, 3 }, { 5, 1 }, { 5, 5 } }; System.out.print(countPairs(N, bishops)); }}// This code is contributed by 29AjayKumar |
Python3
# Python program for above approachboard = [[0 for i in range(20)] for j in range(20)]def countPairs(N, bishops): # Set all the bits # having bishop to 1 for i in range(len(bishops)): board[bishops[i][0]][bishops[i][1]] = 1 # Stores the final answer ans = 0 # Loop to traverse the matrix # diagonally in left direction for s in range(2, (2 * N) + 1): # Stores count of bishop # in the current diagonal cnt = 0 i = 1 j = s - i while(max(i, j) <= min(N, s - 1)): if (board[j][i - j] == 1): # Update cnt cnt += 1 i += 1 j -= 1 # Update the answer if (cnt > 1): ans += ((cnt + 1) * cnt) // 2 # Loop to traverse the matrix # diagonally in right direction for s in range(2, (2 * N) + 1): # Stores count of bishop # in the current diagonal cnt = 0 i = 1 j = s - i while(max(i, j) <= min(N, s - 1)): if (board[i][N - j + 1] == 1): # Update cnt cnt += 1 i += 1 j -= 1 # Update the answer if (cnt > 1): ans += ((cnt + 1) * cnt) // 2 # Return answer return ans# Driver codeN = 10bishops = [[1, 1], [1, 5], [3, 3], [5, 1], [5, 5]]print(countPairs(N, bishops))# This code is contributed by gfgking |
C#
using System;class GFG{ static int[,] board = new int[20,20]; static int countPairs(int N, int[,] bishops) { // Set all the bits // having bishop to 1 for (int i = 0; i < bishops.GetLength(0); i++) { board[bishops[i,0], bishops[i,1]] = 1; } // Stores the final answer int ans = 0; // Loop to traverse the matrix // diagonally in left direction for (int s = 2; s <= 2 * N; s++) { // Stores count of bishop // in the current diagonal int cnt = 0; for (int i = 1, j = s - i; Math.Max(i, j) <= Math.Min(N, s - 1) && i - j > 0; i++, j--) { if (board[j,i - j] == 1) // Update cnt cnt++; } // Update the answer if (cnt > 1) ans += ((cnt + 1) * cnt) / 2; } // Loop to traverse the matrix // diagonally in right direction for (int s = 2; s <= 2 * N; s++) { // Stores count of bishop // in the current diagonal int cnt = 0; for (int i = 1, j = s - i; Math.Max(i, j) <= Math.Min(N, s - 1); i++, j--) { if (board[i,N - j + 1] == 1) // Update cnt cnt++; } // Update the answer if (cnt > 1) ans += ((cnt + 1) * cnt) / 2; } // Return answer return ans; } // Driver code public static void Main() { int N = 10; int[,] bishops = new int[5, 2]{{ 1, 1 }, { 1, 5 }, { 3, 3 }, { 5, 1 }, { 5, 5 }}; Console.Write(countPairs(N, bishops)); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script> // JavaScript program for above approach let board = new Array(20).fill(0).map(() => new Array(20).fill(0)); const countPairs = (N, bishops) => { // Set all the bits // having bishop to 1 for (let i = 0; i < bishops.length; i++) { board[bishops[i][0]][bishops[i][1]] = 1; } // Stores the final answer let ans = 0; // Loop to traverse the matrix // diagonally in left direction for (let s = 2; s <= 2 * N; s++) { // Stores count of bishop // in the current diagonal let cnt = 0; for (let i = 1, j = s - i; Math.max(i, j) <= Math.min(N, s - 1); i++, j--) { if (board[j][i - j] == 1) // Update cnt cnt++; } // Update the answer if (cnt > 1) ans += ((cnt + 1) * cnt) / 2; } // Loop to traverse the matrix // diagonally in right direction for (let s = 2; s <= 2 * N; s++) { // Stores count of bishop // in the current diagonal let cnt = 0; for (let i = 1, j = s - i; Math.max(i, j) <= Math.min(N, s - 1); i++, j--) { if (board[i][N - j + 1] == 1) // Update cnt cnt++; } // Update the answer if (cnt > 1) ans += ((cnt + 1) * cnt) / 2; } // Return answer return ans; } // Driver code let N = 10; let bishops = [ [1, 1], [1, 5], [3, 3], [5, 1], [5, 5] ]; document.write(countPairs(N, bishops));// This code is contributed by rakeshsahni</script> |
Output
6
Time Complexity: O(N * N)
Auxiliary Space: O(N * N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
