Рубрики

Заменить каждый матричный элемент максимальным GCD строки или столбца

Дана матрица из n строк и m столбцов. Задача состоит в том, чтобы заменить каждый элемент матрицы на Величайший общий делитель его строки или столбца, в зависимости от того, что является максимальным. То есть для каждого элемента (i, j) замените его из GCD i-й строки или GCD j-й строки, в зависимости от того, что больше.

Примеры :

Input : mat[3][4] = {1, 2, 3, 3,
                     4, 5, 6, 6
                     7, 8, 9, 9}  
Output :  1 1 3 3
          1 1 3 3
          1 1 3 3
For index (0,2), GCD of row 0 is 1, GCD of row 2 is 3.
So replace index (0,2) with 3 (3>1). 

Идея заключается в том, что мы обсуждали здесь концепцию LCM массива, чтобы найти GCD строки и столбца.

Используя грубую силу , мы можем пройти элемент матрицы, найти GCD строки и столбца, соответствующего элементу, и заменить его максимумом обоих.

Эффективным методом является создание двух массивов размера n и m для строки и столбца соответственно. И сохраните GCD каждой строки и каждого столбца. Массив размера n будет содержать GCD каждой строки, а массив размера m будет содержать GCD каждого столбца. И замените каждый элемент максимумом соответствующей ему строки GCD или столбца GCD.

Ниже приведена реализация этого подхода:

C ++

// C ++ программа для замены каждого элемента на
// максимум GCD строки или столбца.
#include<bits/stdc++.h>

using namespace std;

#define R 3
#define C 4

  
// возвращаем наибольший общий делитель двух чисел

int gcd(int a, int b)

{

    if (b == 0)

        return a;

    return gcd(b, a%b);

}

  
// Находим GCD каждой строки и столбца и заменяем
// с каждым элементом с максимумом GCD строки или
// столбец.

void replacematrix(int mat[R][C], int n, int m)

{

    int rgcd[R] = { 0 }, cgcd[C] = { 0 };

  

    // Расчет GCD каждой строки и каждого столбца в

    // O (mn) и хранить в массивах.

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

    {

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

        {

            rgcd[i] = gcd(rgcd[i], mat[i][j]);

            cgcd[j] = gcd(cgcd[j], mat[i][j]);

        }

    }

  

    // Замена матричного элемента

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

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

            mat[i][j] = max(rgcd[i], cgcd[j]);

}

  
// Управляемая программа

int main()

{

    int m[R][C] =

    {

        1, 2, 3, 3,

        4, 5, 6, 6,

        7, 8, 9, 9,

    };

  

    replacematrix(m, R, C);

  

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

    {

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

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

        cout<<endl;

    }

  

    return 0;

}

Джава

// Java-программа для замены каждого элемента
// максимум GCD строки или столбца.

import java .io.*;

  

class GFG

{

      static int R = 3;

      static int C = 4;

  

      // возвращаем наибольшее общее

      // делитель двух чисел

      static int gcd(int a, int b)

      {

         if (b == 0)

         return a;

         return gcd(b, a%b);

      }

  
// Находим GCD каждой строки и столбца и
// замена на каждый элемент с максимумом
// ГКД строки или столбца.

static void replacematrix(int [][]mat, int n, int m)

{

    int []rgcd = new int[R] ;

    int []cgcd = new int[C];

  

    // Расчет GCD каждой строки и каждого столбца в

    // O (mn) и хранить в массивах.

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

    {

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

        {

            rgcd[i] = gcd(rgcd[i], mat[i][j]);

            cgcd[j] = gcd(cgcd[j], mat[i][j]);

        }

    }

  

    // Замена матричного элемента

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

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

            mat[i][j] = Math.max(rgcd[i], cgcd[j]);

}

  
// Драйвер программы

    static public void main (String[] args){

    int [][]m =

    {

        {1, 2, 3, 3},

        {4, 5, 6, 6},

        {7, 8, 9, 9},

    };

  

    replacematrix(m, R, C);

  

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

    {

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

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

        System.out.println();

    }

    }

}

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

python3

# Python3 программа для замены каждого элемента
# с максимумом GCD строки или столбца.

  

R = 3

C = 4

  
# возвращая наибольшее общее
# делитель двух чисел

def gcd(a, b):

    if (b == 0):

        return a

    return gcd(b, a % b)

  
# Нахождение GCD каждой строки и столбца
# и заменяя на каждый элемент
# максимум GCD строки или столбца.

def replacematrix(mat, n, m):

  

    rgcd = [0] *

    cgcd = [0] * C

  

    # Расчет GCD каждой строки и каждого

    # столбец в O (mn) и хранить в массивах.

    for i in range (n):

        for j in range (m):

          

            rgcd[i] = gcd(rgcd[i], mat[i][j])

            cgcd[j] = gcd(cgcd[j], mat[i][j])

  

    # Замена матричного элемента

    for i in range (n):

        for j in range (m):

            mat[i][j] = max(rgcd[i], cgcd[j])

  
Код водителя

if __name__ == "__main__":

  

    m = [[1, 2, 3, 3],

         [4, 5, 6, 6],

         [7, 8, 9, 9]]

  

    replacematrix(m, R, C)

  

    for i in range(R):

        for j in range (C):

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

        print ()

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

C #

// C # программа для замены каждого элемента
// максимум GCD строки или столбца.

using System;

  

class GFG

{

      static int R = 3;

      static int C = 4;

    

      // возвращаем наибольшее общее

      // делитель двух чисел

      static int gcd(int a, int b)

      {

        if (b == 0)

        return a;

        return gcd(b, a%b);

      }

  
// Находим GCD каждой строки и столбца и
// замена на каждый элемент с максимумом
// ГКД строки или столбца.

static void replacematrix(int [,]mat, int n, int m)

{

    int []rgcd = new int[R] ;

    int []cgcd = new int[C];

  

    // Расчет GCD каждой строки и каждого столбца в

    // O (mn) и хранить в массивах.

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

    {

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

        {

            rgcd[i] = gcd(rgcd[i], mat[i,j]);

            cgcd[j] = gcd(cgcd[j], mat[i,j]);

        }

    }

  

    // Замена матричного элемента

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

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

            mat[i,j] = Math.Max(rgcd[i], cgcd[j]);

}

  
// Драйвер программы

    static public void Main (){

    int [,]m =

    {

        {1, 2, 3, 3},

        {4, 5, 6, 6},

        {7, 8, 9, 9},

    };

  

    replacematrix(m, R, C);

  

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

    {

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

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

        Console.WriteLine();

    }

    }

}

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

Выход:

1 1 3 3 
1 1 3 3 
1 1 3 3 

Сложность времени: O (мн).
Подмышечное пространство: O (m + n).

Эта статья предоставлена Anuj Chauahan (anuj0503) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Заменить каждый матричный элемент максимальным GCD строки или столбца

0.00 (0%) 0 votes