Dada una array cuadrada mat[][] de dimensión N*N , convierta los elementos presentes en ambas diagonales a sus respectivas representaciones binarias y realice las siguientes operaciones:
- Para cada posición de bits, cuente el número de bits establecidos y no establecidos en esas representaciones binarias .
- Si el conteo de bits establecidos excede el de bits no establecidos, coloque 0 en esa posición para un nuevo número. De lo contrario, coloque 1 en esa posición.
- Finalmente, imprima la suma de los dos números generados.
Ejemplos:
Entrada: mat[][] = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
Salida: 8
Explicación:
Para la diagonal primaria, la representación binaria de cada elemento es :
1 = (0001) 2
5 = (0101) 2
9 = (1001) 2
En la posición de bit 0, número de bits establecidos (=3)>número de bits no establecidos (=0)
En la posición de bit 1, número de bits establecidos (= 0) <número de bits no establecidos (= 3)
En la posición de bit 2, número de bits establecidos (= 1) <número de bits no establecidos (= 2)
En la posición de bit 3, número de bits establecidos (=1)<número de bits no establecidos(=2)
Por lo tanto, después de procesar la diagonal primaria, el número generado es (0001) 2 = 1.
Para la diagonal secundaria, la representación binaria de cada elemento es:
3 = (011) 2
5 = (101) 2
7 = (111) 2
En la posición de bit 0, número de bits establecidos (= 3)>número de bits no establecidos bits (= 0)
En la posición de bit 1, número de bits establecidos (= 2)> número de bits no establecidos (= 1)
En la posición de bit 2, número de bits establecidos (= 2)> número de bits no establecidos ( =1)
Por lo tanto, después de procesar la diagonal principal, el número generado es (111) 2 = 7.
Por lo tanto, la suma requerida = 1 + 7 = 8.Entrada: mat[][] = [[2, 3], [3, 9]]
Salida: 3
Enfoque ingenuo: el enfoque más simple es atravesar la array y almacenar los elementos diagonales primarios en una array y los elementos diagonales secundarios en otra array. Luego encuentre la suma de los números generados al iterar sobre los bits establecidos de los elementos en ambas arrays.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar encontrando los elementos diagonales usando un solo bucle . Siga los pasos a continuación para resolver el problema:
- Para los elementos de la Diagonal Principal: Itere un bucle hasta N , donde N es el número de columnas, y almacene mat[i][i] donde i es la variable de índice.
- Para elementos diagonales secundarios: itere un ciclo hasta N , donde N es el número de columnas y almacene mat[i][k] , donde i es la variable de índice y K = N – 1 . Disminuir K hasta i < N .
Para encontrar los números para cada conjunto de elementos diagonales, realice los siguientes pasos:
- Inicialice una variable, digamos ans como 0 , para almacenar el número resultante.
- Itere sobre el rango [0, 31] usando la variable i y realice lo siguiente:
- Inicialice S y NS como 0 , para almacenar el número de bits establecidos y no establecidos, respectivamente, en la posición i .
- Atraviese los elementos diagonales usando la variable j y si arr[j] se establece en la posición i , incremente S en 1 , de lo contrario incremente NS en 1 .
- Si el valor de S es mayor que NS , establezca el bit en la posición i de ans .
- Después de completar los pasos anteriores, el valor de ans es el número generado para cada conjunto de elementos diagonales.
- Repita los pasos anteriores para los otros conjuntos de elementos diagonales e imprima la suma de los dos números generados.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to find the number after
// processing the diagonal elements
int processDiagonal(vector<int>arr)
{
// Store the required number
int ans = 0;
int getBit = 1;
// Checking for each position
for (int i = 0; i < 32; i++)
{
// Store the number of set bits
// & non-set bits at position i
int S = 0;
int NS = 0;
// Traverse the diagonal elements
for(auto j: arr)
{
// Update count of S if current
// element is set at position i
if (getBit&j)
S += 1;
// Else update NS
else
NS += 1;
}
// If number of set bits is >
// number of non-set bits, add
// set bits value to the ans
if(S > NS)
ans += pow(2,i);
getBit <<= 1;
}
// Return the answer
return ans;
}
// Function to find the sum of the
// numbers generated after processing
// both the diagonals of the matrix
int findSum(vector<vector<int>>mat)
{
int i = 0;
int j = 0;
// Store the primary diagonal elements
vector<int> priDiag;
while(i<mat.size()){
priDiag.push_back(mat[i][j]);
i += 1;
j += 1;
}
i = 0;
j = mat.size()-1;
// Store the secondary diagonal elements
vector<int> secDiag;
while(i<mat.size()){
secDiag.push_back(mat[i][j]);
i += 1;
j -= 1;
}
// Function Call to get the required
// numbers and return their sum
return processDiagonal(priDiag) + processDiagonal(secDiag);
}
// Driver Code
int main(){
vector<vector<int>>mat{{1, 2, 3},{4, 5, 6},{7, 8, 9}};
// Function Call
cout<<findSum(mat)<<endl;
}
// This code is contributed by bgangwar59.
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Functino to find the number after
// processing the diagonal elements
static int processDiagonal(ArrayList<Integer> arr)
{
// Store the required number
int ans = 0;
int getBit = 1;
// Checking for each position
for (int i = 0; i < 32; i++)
{
// Store the number of set bits
// & non-set bits at position i
int S = 0;
int NS = 0;
// Traverse the diagonal elements
for(int j: arr)
{
// Update count of S if current
// element is set at position i
if ((getBit&j) != 0)
S += 1;
// Else update NS
else
NS += 1;
}
// If number of set bits is >
// number of non-set bits, add
// set bits value to the ans
if(S > NS)
ans += Math.pow(2,i);
getBit <<= 1;
}
// Return the answer
return ans;
}
// Function to find the sum of the
// numbers generated after processing
// both the diagonals of the matrix
static int findSum(int[][] mat)
{
int i = 0;
int j = 0;
// Store the primary diagonal elements
ArrayList<Integer> priDiag
= new ArrayList<Integer>();
while(i<mat.length){
priDiag.add(mat[i][j]);
i += 1;
j += 1;
}
i = 0;
j = mat.length - 1;
// Store the secondary diagonal elements
ArrayList<Integer> secDiag
= new ArrayList<Integer>();
while(i<mat.length){
secDiag.add(mat[i][j]);
i += 1;
j -= 1;
}
// Function Call to get the required
// numbers and return their sum
return (processDiagonal(priDiag) + processDiagonal(secDiag));
}
// Driver Code
public static void main(String[] args)
{
int[][] mat= {{1, 2, 3},{4, 5, 6},{7, 8, 9}};
// Function Call
System.out.print(findSum(mat));
}
}
// This code is contributed by splevel62.
Python3
# Python program for the above approach # Functino to find the number after # processing the diagonal elements def processDiagonal(arr): # Store the required number ans = 0 getBit = 1 # Checking for each position for i in range(32): # Store the number of set bits # & non-set bits at position i S = 0 NS = 0 # Traverse the diagonal elements for j in arr: # Update count of S if current # element is set at position i if getBit&j: S += 1 # Else update NS else: NS += 1 # If number of set bits is > # number of non-set bits, add # set bits value to the ans if S > NS: ans += 2**i getBit <<= 1 # Return the answer return ans # Function to find the sum of the # numbers generated after processing # both the diagonals of the matrix def findSum(mat): i = 0 j = 0 # Store the primary diagonal elements priDiag = [] while i<len(mat): priDiag.append(mat[i][j]) i += 1 j += 1 i = 0 j = len(mat)-1 # Store the secondary diagonal elements secDiag = [] while i<len(mat): secDiag.append(mat[i][j]) i += 1 j -= 1 # Function Call to get the required # numbers and return their sum return processDiagonal(priDiag) + processDiagonal(secDiag) # Driver Code mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] # Function Call print(findSum(mat))
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Functino to find the number after
// processing the diagonal elements
static int processDiagonal(List<int> arr)
{
// Store the required number
int ans = 0;
int getBit = 1;
// Checking for each position
for (int i = 0; i < 32; i++) {
// Store the number of set bits
// & non-set bits at position i
int S = 0;
int NS = 0;
// Traverse the diagonal elements
foreach(int j in arr)
{
// Update count of S if current
// element is set at position i
if ((getBit & j) != 0)
S += 1;
// Else update NS
else
NS += 1;
}
// If number of set bits is >
// number of non-set bits, add
// set bits value to the ans
if (S > NS)
ans += (int)Math.Pow(2, i);
getBit <<= 1;
}
// Return the answer
return ans;
}
// Function to find the sum of the
// numbers generated after processing
// both the diagonals of the matrix
static int findSum(int[, ] mat)
{
int i = 0;
int j = 0;
// Store the primary diagonal elements
List<int> priDiag = new List<int>();
while (i < mat.GetLength(0)) {
priDiag.Add(mat[i, j]);
i += 1;
j += 1;
}
i = 0;
j = mat.GetLength(0) - 1;
// Store the secondary diagonal elements
List<int> secDiag = new List<int>();
while (i < mat.GetLength(0)) {
secDiag.Add(mat[i, j]);
i += 1;
j -= 1;
}
// Function Call to get the required
// numbers and return their sum
return (processDiagonal(priDiag)
+ processDiagonal(secDiag));
}
// Driver Code
public static void Main(string[] args)
{
int[, ] mat
= { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
// Function Call
Console.Write(findSum(mat));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Functino to find the number after
// processing the diagonal elements
function processDiagonal(arr)
{
// Store the required number
let ans = 0;
let getBit = 1;
// Checking for each position
for (let i = 0; i < 32; i++)
{
// Store the number of set bits
// & non-set bits at position i
let S = 0;
let NS = 0;
// Traverse the diagonal elements
for(let j = 0; j < arr.length; j++)
{
// Update count of S if current
// element is set at position i
if (getBit & arr[j])
S += 1;
// Else update NS
else
NS += 1;
}
// If number of set bits is >
// number of non-set bits, add
// set bits value to the ans
if(S > NS)
ans += Math.pow(2,i);
getBit <<= 1;
}
// Return the answer
return ans;
}
// Function to find the sum of the
// numbers generated after processing
// both the diagonals of the matrix
function findSum(mat)
{
let i = 0;
let j = 0;
// Store the primary diagonal elements
let priDiag = [];
while(i<mat.length){
priDiag.push(mat[i][j]);
i += 1;
j += 1;
}
i = 0;
j = mat.length - 1;
// Store the secondary diagonal elements
let secDiag = [];
while(i<mat.length){
secDiag.push(mat[i][j]);
i += 1;
j -= 1;
}
// Function Call to get the required
// numbers and return their sum
return processDiagonal(priDiag) + processDiagonal(secDiag);
}
// Driver Code
let mat = [[1, 2, 3],[4, 5, 6],[7, 8, 9]];
// Function Call
document.write(findSum(mat));
</script>
8
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA