Maximum bishops that can be placed on N*N chessboard
Given an integer n, the task is to print the maximum number of bishops that can be placed on a n x n chessboard so that no two bishops attack each other. For example, maximum 2 bishops can be placed safely on 2 x 2 chessboard.
Examples:
Input: n = 2
Output: 2
We can place two bishop in a row.Input: n = 5
Output: 8
Approach: A bishop can travel in any of the four diagonals. Therefore we can place bishops if it is not in any diagonal of another bishop. The maximum bishops that can be placed on an n * n chessboard will be 2 * (n – 1).
- Place n bishops in first row
- Place n-2 bishops in last row. We only leave two corners of last row
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; // Function to return the maximum number of bishops // that can be placed on an n * n chessboard int numberOfBishops( int n) { if (n < 1) return 0; else if (n == 1) return 1; else return 2 * (n - 1); } // Driver code int main() { int n = 5; cout << numberOfBishops(n); return 0; } |
Java
// Java implementation of the approach class gfg { // Function to return the maximum // number of bishops that can be // placed on an n * n chessboard static int numberOfBishops( int n) { if (n < 1 ) return 0 ; else if (n == 1 ) return 1 ; else return 2 * (n - 1 ); } // Driver code public static void main(String[] args) { int n = 5 ; System.out.println(numberOfBishops(n)); } } // This code is contributed by Mukul Singh. |
Python3
# Python3 implementation of the # approach import math as mt # Function to return the maximum number # of bishops that can be placed on an # n * n chessboard def numberOfBishops(n): if (n < 1 ): return 0 elif (n = = 1 ): return 1 else : return 2 * (n - 1 ) # Driver code n = 5 print (numberOfBishops(n)) # This code is contributed by # Mohit kumar 29 |
C#
// C# implementation of the approach using System; class GFG { // Function to return the maximum number // of bishops that can be placed on an // n * n chessboard static int numberOfBishops( int n) { if (n < 1) return 0; else if (n == 1) return 1; else return 2 * (n - 1); } // Driver code public static void Main() { int n = 5; Console.Write(numberOfBishops(n)); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP implementation of the approach // Function to return the maximum number // of bishops that can be placed on an // n * n chessboard function numberOfBishops( $n ) { if ( $n < 1) return 0; else if ( $n == 1) return 1; else return 2 * ( $n - 1); } // Driver code $n = 5; echo numberOfBishops( $n ); // This code is contributed by Ryuga ?> |
Javascript
<script> // Javascript implementation of the approach // Function to return the maximum // number of bishops that can be // placed on an n * n chessboard function numberOfBishops(n) { if (n < 1) return 0; else if (n == 1) return 1; else return 2 * (n - 1); } // Driver code let n = 5; document.write(numberOfBishops(n)); // This code is contributed by patel2127 </script> |
Output
8
Time Complexity: O(1)
Space Complexity: O(1)
Below is the implementation for bigger values of n:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to return the difference of // two big numbers as string string subtract(string str1, string str2) { string res = "" ; int n1 = str1.length(); int n2 = str2.length(); // To make subtraction easy reverse(str1.begin(), str1.end()); reverse(str2.begin(), str2.end()); int carry = 0; for ( int i = 0; i < n2; i++) { // Subtract digit by bdigit int subst = ((str1[i] - '0' ) - (str2[i] - '0' ) - carry); if (subst < 0) { subst = subst + 10; carry = 1; } else carry = 0; // Change subst as character and // add it to result string res.push_back(subst + '0' ); } for ( int i = n2; i < n1; i++) { int subst = ((str1[i] - '0' ) - carry); if (subst < 0) { subst = subst + 10; carry = 1; } else carry = 0; res.push_back(subst + '0' ); } // Reverse result to make it actual number reverse(res.begin(), res.end()); return res; } string NumberOfBishops(string a) { if (a == "1" ) return a; else { // Subtract 1 from number a = subtract(a, "1" ); // Reverse the string to make calculations easier reverse(a.begin(), a.end()); int carry = 0; // Multiply by 2 for ( int i = 0; i < a.size(); i++) { int tmp = a[i] - '0' ; tmp *= 2; tmp += carry; a[i] = '0' + (tmp % 10); carry = tmp / 10; } if (carry > 0) a += ( '0' + carry); // Reverse the string to get actual result reverse(a.begin(), a.end()); // Return result return a; } } // Driver code int main() { string a = "12345678901234567890" ; cout << NumberOfBishops(a) << endl; return 0; } |
Java
// Java implementation of the approach import java.util.*; class GFG{ public static char [] reverse( char []str) { char [] temp = new char [str.length]; // Fill character array backwards with // characters of the string for ( int i = 0 ; i < str.length; i++) temp[str.length - i - 1 ] = str[i]; // Convert character array to string // and return it return temp; } // Function to return the difference of // two big numbers as String static char [] subtract( char [] str1, char [] str2) { String res = "" ; int n1 = str1.length; int n2 = str2.length; // To make subtraction easy str1 = reverse(str1); str2 = reverse(str2); int carry = 0 ; for ( int i = 0 ; i < n2; i++) { // Subtract digit by bdigit int subst = ((str1[i] - '0' ) - (str2[i] - '0' ) - carry); if (subst < 0 ) { subst = subst + 10 ; carry = 1 ; } else carry = 0 ; // Change subst as character and // add it to result String res = res + (subst); } for ( int i = n2; i < n1; i++) { int subst = ((str1[i] - '0' ) - carry); if (subst < 0 ) { subst = subst + 10 ; carry = 1 ; } else carry = 0 ; res += (subst); } // Reverse result to make it actual number char [] Res = res.toCharArray(); Res = reverse(Res); return Res; } static char [] NumberOfBishops( char [] a) { if ( new String(a) == "1" ) return a; else { // Subtract 1 from number a = subtract(a, "1" .toCharArray()); //Console.WriteLine(new String(a)); // Reverse the String to make // calculations easier a = reverse(a); int carry = 0 ; // Multiply by 2 for ( int i = 0 ; i < a.length; i++) { int tmp = a[i] - '0' ; tmp *= 2 ; tmp += carry; a[i] = ( char )( '0' + (tmp % 10 )); carry = tmp / 10 ; } String A = new String(a); if (carry > 0 ) A += ( '0' + carry); char [] a1 = A.toCharArray(); // Reverse the String to get // actual result a1 = reverse(a1); // Return result return a1; } } // Driver code public static void main(String []args) { char [] a = "12345678901234567890" .toCharArray(); System.out.println( new String(NumberOfBishops(a))); } } // This code is contributed by pratham76 |
Python3
# Python3 implementation of the approach # Function to return the difference # of two big numbers as string def subtract(str1, str2): res = "" n1 = len (str1) n2 = len (str2) # To make subtraction easy, # reverse the strings str1 = str1[:: - 1 ] str2 = str2[:: - 1 ] carry = 0 for i in range ( 0 , n2): # Subtract digit by bdigit subst = int (str1[i]) - int (str2[i]) - carry if subst < 0 : subst = subst + 10 carry = 1 else : carry = 0 # Change subst as character and # add it to result string res + = str (subst) for i in range (n2, n1): subst = int (str1[i]) - carry if subst < 0 : subst = subst + 10 carry = 1 else : carry = 0 res + = str (subst) # Reverse result to make it # actual number return res[:: - 1 ] def NumberOfBishops(a): if a = = "1" : return a else : # Subtract 1 from number a = subtract(a, "1" ) carry = 0 # Reverse the string to make # calculations easier. Convert the # string to list to manipulate it # as strings are immutable in python a = list (a[:: - 1 ]) # Multiply by 2 for i in range ( 0 , len (a)): tmp = ( int (a[i]) * 2 ) + carry a[i] = str (tmp % 10 ) carry = tmp / / 10 # Convert the list back to string a = ''.join(a) if carry > 0 : a + = str (carry) # Reverse the string to get # actual result return a[:: - 1 ] # Driver code if __name__ = = "__main__" : a = "12345678901234567890" print (NumberOfBishops(a)) # This code is contributed # by Rituraj Jain |
C#
// C# implementation of the approach using System; class GFG { // Function to return the difference of // two big numbers as string static char [] subtract( char [] str1, char [] str2) { string res = "" ; int n1 = str1.Length; int n2 = str2.Length; // To make subtraction easy Array.Reverse(str1); Array.Reverse(str2); int carry = 0; for ( int i = 0; i < n2; i++) { // Subtract digit by bdigit int subst = ((str1[i] - '0' ) - (str2[i] - '0' ) - carry); if (subst < 0) { subst = subst + 10; carry = 1; } else carry = 0; // Change subst as character and // add it to result string res = res + (subst); } for ( int i = n2; i < n1; i++) { int subst = ((str1[i] - '0' ) - carry); if (subst < 0) { subst = subst + 10; carry = 1; } else carry = 0; res += (subst); } // Reverse result to make it actual number char [] Res = res.ToCharArray(); Array.Reverse(Res); return Res; } static char [] NumberOfBishops( char [] a) { if ( new string (a) == "1" ) return a; else { // Subtract 1 from number a = subtract(a, "1" .ToCharArray()); //Console.WriteLine(new string(a)); // Reverse the string to make calculations easier Array.Reverse(a); int carry = 0; // Multiply by 2 for ( int i = 0; i < a.Length; i++) { int tmp = a[i] - '0' ; tmp *= 2; tmp += carry; a[i] = ( char )( '0' + (tmp % 10)); carry = tmp / 10; } string A = new string (a); if (carry > 0) A += ( '0' + carry); char [] a1 = A.ToCharArray(); // Reverse the string to get actual result Array.Reverse(a1); // Return result return a1; } } // Driver code static void Main() { char [] a = "12345678901234567890" .ToCharArray(); Console.WriteLine( new string (NumberOfBishops(a))); } } // This code is contributed by divyeshrabadiy07 |
Javascript
<script> // Javascript implementation of the approach function reverse(str) { let temp = new Array(str.length); // Fill character array backwards with // characters of the string for (let i = 0; i < str.length; i++) temp[str.length - i - 1] = str[i]; // Convert character array to string // and return it return temp; } // Function to return the difference of // two big numbers as String function subtract(str1,str2) { let res = "" ; let n1 = str1.length; let n2 = str2.length; // To make subtraction easy str1 = reverse(str1); str2 = reverse(str2); let carry = 0; for (let i = 0; i < n2; i++) { // Subtract digit by bdigit let subst = (parseInt(str1[i]) - parseInt(str2[i]) - carry); if (subst < 0) { subst = subst + 10; carry = 1; } else carry = 0; // Change subst as character and // add it to result String res = res + (subst).toString(); } for (let i = n2; i < n1; i++) { let subst = (parseInt(str1[i]) - carry); if (subst < 0) { subst = subst + 10; carry = 1; } else carry = 0; res += (subst).toString(); } // Reverse result to make it actual number let Res = res.split( "" ); Res = reverse(Res); return Res; } function NumberOfBishops(a) { if (a == "1" ) return a; else { // Subtract 1 from number a = subtract(a, "1" ); //Console.WriteLine(new String(a)); // Reverse the String to make // calculations easier a = reverse(a); let carry = 0; // Multiply by 2 for (let i = 0; i < a.length; i++) { let tmp = parseInt(a[i]); tmp *= 2; tmp += carry; a[i] = (tmp % 10).toString(); carry = Math.floor(tmp / 10); } let A = a.join( "" ); if (carry > 0) A += ( carry).toString(); let a1 = A.split( "" ); // Reverse the String to get // actual result a1 = reverse(a1); // Return result return a1; } } // Driver code let a = "12345678901234567890" .split( "" ); document.write(NumberOfBishops(a).join( "" )); // This code is contributed by unknown2108. </script> |
Output
24691357802469135778
Time Complexity: O(n)
Space Complexity: O(n)
Contact Us