Рубрики

Найдите N x N сетку, у которой xor каждой строки и столбца равен

Для заданного целого числа N , кратного 4 , задача состоит в том, чтобы найти сетку N x N, для которой поразрядное значение xor каждой строки и столбца одинаково.

Примеры:

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

Подход: чтобы решить эту проблему, давайте установим xor каждой строки и столбца в 0, поскольку xor 4 последовательных чисел, начиная с 0, равно 0. Вот пример матрицы 4 x 4:

0 ^ 1 ^ 2 ^ 3 = 0
4 ^ 5 ^ 6 ^ 7 = 0
8 ^ 9 ^ 10 ^ 11 = 0
12 ^ 13 ^ 14 ^ 15 = 0
and so on.

Если вы заметили в вышеприведенном примере, xor каждой строки и столбца равно 0. Теперь нам нужно разместить числа таким образом, чтобы xor каждой строки и столбца было равно 0. Поэтому мы можем разделить нашу матрицу N x N на меньшие матрицы 4 x 4 с N / 4 строками и столбцами и заполняющие ячейки таким образом, что xor каждой строки и столбца равно 0.

Ниже приведена реализация вышеуказанного подхода:

C ++

// C ++ реализация подхода
#include <bits/stdc++.h>

using namespace std;

  
// Функция для поиска матрицы nxn
// который удовлетворяет данному условию

void findGrid(int n)

{

    int arr[n][n];

  

    // Инициализируем x в 0

    int x = 0;

  

    // Делим матрицу nxn на n / 4 матрицы

    // для каждой из n / 4 строк, где

    // каждая матрица имеет размер 4 х 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++;

                }

            }

        }

    }

  

    // Распечатать сгенерированную матрицу

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < n; j++) {

            cout << arr[i][j] << " ";

        }

        cout << "\n";

    }

}

  
// Код драйвера

int main()

{

    int n = 4;

  

    findGrid(n);

  

    return 0;

}

Джава

// Java реализация подхода

import java.io.*;

  

class GFG 

{

      
// Функция для поиска матрицы nxn
// который удовлетворяет данному условию

static void findGrid(int n)

{

    int [][]arr = new int[n][n];

  

    // Инициализируем x в 0

    int x = 0;

  

    // Делим матрицу nxn на n / 4 матрицы

    // для каждой из n / 4 строк, где

    // каждая матрица имеет размер 4 х 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++;

                }

            }

        }

    }

  

    // Распечатать сгенерированную матрицу

    for (int i = 0; i < n; i++) 

    {

        for (int j = 0; j < n; j++) 

        {

            System.out.print(arr[i][j] + " ");

        }

        System.out.println(" ");

    }

}

  
// Код драйвера

public static void main (String[] args)

{

    int n = 4;

      

    findGrid(n);

}
}

  
// Этот код предоставлен ajit.

python3

# Python3 реализация подхода

  
# Функция для поиска матрицы nxn
# которое удовлетворяет данному условию

def findGrid(n): 

  

    arr = [[0 for k in range(n)] 

              for l in range(n)] 

  

    # Инициализировать х в 0

    x = 0

  

    # Разделить матрицу nxn на n / 4 матрицы

    # для каждой из n / 4 строк, где

    # каждая матрица имеет размер 4 х 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 += 1

  

    # Распечатать сгенерированную матрицу

    for i in range(n): 

        for j in range(n): 

            print(arr[i][j], end = " ")

        print()

  
# Код драйвера

n = 4

findGrid(n) 

  
# Этот код предоставлен divyamohan123

C #

// C # реализация подхода

using System;

      

class GFG 

{

      
// Функция для поиска матрицы nxn
// который удовлетворяет данному условию

static void findGrid(int n)

{

    int [,]arr = new int[n, n];

  

    // Инициализируем x в 0

    int x = 0;

  

    // Делим матрицу nxn на n / 4 матрицы

    // для каждой из n / 4 строк, где

    // каждая матрица имеет размер 4 х 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++;

                }

            }

        }

    }

  

    // Распечатать сгенерированную матрицу

    for (int i = 0; i < n; i++) 

    {

        for (int j = 0; j < n; j++) 

        {

            Console.Write(arr[i, j] + " ");

        }

        Console.WriteLine(" ");

    }

}

  
// Код драйвера

public static void Main (String[] args)

{

    int n = 4;

      

    findGrid(n);

}
}

  
// Этот код предоставлен PrinciRaj1992

Выход:

0 1 2 3 
4 5 6 7 
8 9 10 11 
12 13 14 15

Сложность времени: O (N 2 )

Рекомендуемые посты:

Найдите N x N сетку, у которой xor каждой строки и столбца равен

0.00 (0%) 0 votes