Given an integer N which is a multiple of 4, the task is to find an N x N grid for which the bitwise xor of every row and column is the same.
Examples:
Input: N = 4
Output:
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
Input: N = 8
Output:
0 1 2 3 16 17 18 19
4 5 6 7 20 21 22 23
8 9 10 11 24 25 26 27
12 13 14 15 28 29 30 31
32 33 34 35 48 49 50 51
36 37 38 39 52 53 54 55
40 41 42 43 56 57 58 59
44 45 46 47 60 61 62 63
Approach: To solve this problem let’s fix the xor of every row and column to 0 since xor of 4 consecutive numbers starting from 0 is 0. Here is an example of a 4 x 4 matrix:
0 ^ 1 ^ 2 ^ 3 = 0
4 ^ 5 ^ 6 ^ 7 = 0
8 ^ 9 ^ 10 ^ 11 = 0
12 ^ 13 ^ 14 ^ 15 = 0
and so on.
If you notice in the above example, the xor of every row and column is 0. Now we need to place the numbers in such a way that the xor of each row and column is 0. So we can divide our N x N matrix into smaller 4 x 4 matrices with N / 4 rows and columns and fill the cells in a way that the xor of every row and column is 0.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to find the n x n matrix// that satisfies the given conditionvoid findGrid(int n){ int arr[n][n]; // Initialize x to 0 int x = 0; // Divide the n x n matrix into n / 4 matrices // for each of the n / 4 rows where // each matrix is of size 4 x 4 for (int i = 0; i < n / 4; i++) { for (int j = 0; j < n / 4; j++) { for (int k = 0; k < 4; k++) { for (int l = 0; l < 4; l++) { arr[i * 4 + k][j * 4 + l] = x; x++; } } } } // Print the generated matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { cout << arr[i][j] << " "; } cout << "\n"; }}// Driver codeint main(){ int n = 4; findGrid(n); return 0;} |
Java
// Java implementation of the approachimport java.io.*;class GFG { // Function to find the n x n matrix// that satisfies the given conditionstatic void findGrid(int n){ int [][]arr = new int[n][n]; // Initialize x to 0 int x = 0; // Divide the n x n matrix into n / 4 matrices // for each of the n / 4 rows where // each matrix is of size 4 x 4 for (int i = 0; i < n / 4; i++) { for (int j = 0; j < n / 4; j++) { for (int k = 0; k < 4; k++) { for (int l = 0; l < 4; l++) { arr[i * 4 + k][j * 4 + l] = x; x++; } } } } // Print the generated matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { System.out.print(arr[i][j] + " "); } System.out.println(" "); }}// Driver codepublic static void main (String[] args){ int n = 4; findGrid(n);}}// This code is contributed by ajit. |
Python3
# Python3 implementation of the approach # Function to find the n x n matrix # that satisfies the given condition def findGrid(n): arr = [[0 for k in range(n)] for l in range(n)] # Initialize x to 0 x = 0 # Divide the n x n matrix into n / 4 matrices # for each of the n / 4 rows where # each matrix is of size 4 x 4 for i in range(n // 4): for j in range(n // 4): for k in range(4): for l in range(4): arr[i * 4 + k][j * 4 + l] = x x += 1 # Print the generated matrix for i in range(n): for j in range(n): print(arr[i][j], end = " ") print()# Driver code n = 4findGrid(n) # This code is contributed by divyamohan123 |
C#
// C# implementation of the approachusing System; class GFG { // Function to find the n x n matrix// that satisfies the given conditionstatic void findGrid(int n){ int [,]arr = new int[n, n]; // Initialize x to 0 int x = 0; // Divide the n x n matrix into n / 4 matrices // for each of the n / 4 rows where // each matrix is of size 4 x 4 for (int i = 0; i < n / 4; i++) { for (int j = 0; j < n / 4; j++) { for (int k = 0; k < 4; k++) { for (int l = 0; l < 4; l++) { arr[i * 4 + k, j * 4 + l] = x; x++; } } } } // Print the generated matrix for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { Console.Write(arr[i, j] + " "); } Console.WriteLine(" "); }}// Driver codepublic static void Main (String[] args){ int n = 4; findGrid(n);}}// This code is contributed by PrinciRaj1992 |
Javascript
<script>// Javascript implementation of the approach// Function to find the n x n matrix// that satisfies the given conditionfunction findGrid(n){ let arr = new Array(n); for (let i = 0; i < n; i++) arr[i] = new Array(n); // Initialize x to 0 let x = 0; // Divide the n x n matrix into n / 4 matrices // for each of the n / 4 rows where // each matrix is of size 4 x 4 for (let i = 0; i < parseInt(n / 4); i++) { for (let j = 0; j < parseInt(n / 4); j++) { for (let k = 0; k < 4; k++) { for (let l = 0; l < 4; l++) { arr[i * 4 + k][j * 4 + l] = x; x++; } } } } // Print the generated matrix for (let i = 0; i < n; i++) { for (let j = 0; j < n; j++) { document.write(arr[i][j] + " "); } document.write("<br>"); }}// Driver code let n = 4; findGrid(n);</script> |
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Time Complexity: O(N2)
Auxiliary Space: O(N2)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
