Dada una array mat[][] de dimensión M * N , la tarea es primero comprimirla para obtener una array y luego comprimirla nuevamente para obtener un solo entero usando las siguientes operaciones:
- Cuando se comprime una array, la representación binaria de su valor se comprime.
- Por lo tanto, se considera cada bit, y si una posición de un bit tiene S bits activados y NS bits no activados, entonces el bit se activa para la posición si S > NS y se desactiva en caso contrario.
- Cada columna se comprime para convertir la array en una array, luego esa array se comprime aún más en un solo número.
Por ejemplo, si 5, 2, 3 y 1 se comprimen, entonces sus representaciones binarias (101) 2 , (010) 2 , (011) 2 y (001) 2 se comprimen, entonces para las posiciones 0 y 1 , S ≤ NS y para la 2ª posición S > NS , entonces el número se modifica a (001) 2 = 1 .
Ejemplos:
Entrada: arr[][] ={{ 3, 2, 4}, {5, 6, 1}, {8, 1, 3}}
Salida: 1
Explicación: La array obtenida después de comprimir la array dada desde arriba es { 1, 2, 1 }. Luego, la array obtenida se comprime a 1.Entrada: arr[][] = {{ 5, 3}, {6, 7}}
Salida: 0
Enfoque: La idea es contar el número de bits establecidos para cada posición. Siga los pasos a continuación para resolver el problema:
- Recorra cada elemento de cada columna de una array y comprima cada columna en un solo número.
- Cuente el número de bits establecidos para cada posición.
- Establezca el bit para las posiciones con un número de bits establecidos que exceda el número de bits no establecidos.
- Calcule el valor después de decidir si establecer o no establecer el bit para cada posición.
- Después de obtener una array, aplique los mismos pasos para obtener el entero requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// c++ Program for the above approach
#include<bits/stdc++.h>
using namespace std;
// Function to compress an
// array to a single number
vector<int> append(vector<int> arr, int x)
{
// create a new ArrayList
arr.push_back(x);
return arr;
}
int compress(vector<int> arr)
{
// Stores the required integer
int ans = 0;
int getBit = 1;
// Checking for each position
for (int i = 0; i < 32; i++)
{
int S = 0;
int NS = 0;
for (int j = 0; j < arr.size(); j++)
{
// Count set and unset bit
int temp = getBit & arr[j];
if (temp == 1) {
S += 1;
}
else {
NS += 1;
}
// If count of set bits exceeds
// count of unset bits
if (S > NS) {
// Add value of set bits to ans
ans += pow(2, i);
}
getBit <<= 1;
}
}
return ans;
}
// Function to compress
// matrix to a single number
int getResult(vector<vector<int>> mat)
{
// Stores compressed array
vector<int> compressedArr;
int len = mat.size();
int len2 = mat[0].size();
for (int i = 0; i < len; i++)
{
vector<int> col;
for (int j = 0; j < len2; j++)
{
col = append(col, mat[j][i]);
}
// Compress all columns
// to a single number
compressedArr = append(compressedArr, compress(col));
}
return compress(compressedArr);
}
// Driver Code
int main()
{
vector<vector<int>> mat{{3, 2, 4 },{5, 6, 1},{8, 1, 3}};
cout<<(getResult(mat));
}
// THIS CODE IS CONTRIBUTED BY SURENDRA_GANGWAR.
Java
// Java Program for the above approach
import java.io.*;
import java.lang.*;
import java.lang.Math;
import java.util.*;
class GFG {
// Function to compress an
// array to a single number
static Integer[] append(Integer arr[], int x)
{
// create a new ArrayList
List<Integer> arrlist
= new ArrayList<Integer>(Arrays.asList(arr));
// Add the new element
arrlist.add(x);
// Convert the Arraylist to array
arr = arrlist.toArray(arr);
// return the array
return arr;
}
static int compress(Integer[] arr)
{
// Stores the required integer
int ans = 0;
int getBit = 1;
// Checking for each position
for (int i = 0; i < 32; i++) {
int S = 0;
int NS = 0;
for (int j = 0; j < arr.length; j++) {
// Count set and unset bit
int and = getBit & arr[j];
if (and == 1) {
S += 1;
}
else {
NS += 1;
}
// If count of set bits exceeds
// count of unset bits
if (S > NS) {
// Add value of set bits to ans
ans += Math.pow(2, i);
}
getBit <<= 1;
}
}
return ans;
}
// Function to compress
// matrix to a single number
static int getResult(Integer[][] mat)
{
// Stores compressed array
Integer[] compressedArr = {};
int len = mat.length;
int len2 = mat[0].length;
for (int i = 0; i < len; i++)
{
Integer[] col = {};
for (int j = 0; j < len2; j++)
{
col = append(col, mat[j][i]);
}
// Compress all columns
// to a single number
compressedArr
= append(compressedArr, compress(col));
}
return compress(compressedArr);
}
// Driver Code
public static void main(String[] args)
{
Integer[][] mat = { { 3, 2, 4 },
{ 5, 6, 1 },
{ 8, 1, 3 } };
System.out.println(getResult(mat));
}
}
// This code is contributed by rohitsingh07052.
Python3
# Python Program for the above approach # Function to compress an # array to a single number def compress(arr): # Stores the required integer ans = 0 getBit = 1 # Checking for each position for i in range(32): S = 0 NS = 0 for j in arr: # Count set and unset bits if getBit&j: S += 1 else: NS += 1 # If count of set bits exceeds # count of unset bits if S > NS: # Add value of set bits to ans ans += 2**i getBit <<= 1 return ans # Function to compress # matrix to a single number def getResult(mat): # Stores compressed array compressedArr = [] for i in range(len(mat)): col = [] for j in range(len(mat[0])): col.append(mat[j][i]) # Compress all columns # to a single number compressedArr.append(compress(col)) return compress(compressedArr) # Driver Code mat = [ [ 3, 2, 4], [5, 6, 1], [8, 1, 3] ] print( getResult(mat) )
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to compress an
// array to a single number
static int[] append(int []arr, int x)
{
// create a new List
List<int> arrlist = new List<int>(arr);
// Add the new element
arrlist.Add(x);
// Convert the Arraylist to array
arr = arrlist.ToArray();
// return the array
return arr;
}
static int compress(int[] arr)
{
// Stores the required integer
int ans = 0;
int getBit = 1;
// Checking for each position
for(int i = 0; i < 32; i++)
{
int S = 0;
int NS = 0;
for(int j = 0; j < arr.Length; j++)
{
// Count set and unset bit
int and = getBit & arr[j];
if (and == 1)
{
S += 1;
}
else
{
NS += 1;
}
// If count of set bits exceeds
// count of unset bits
if (S > NS)
{
// Add value of set bits to ans
ans += (int)Math.Pow(2, i);
}
getBit <<= 1;
}
}
return ans;
}
// Function to compress
// matrix to a single number
static int getResult(int[,] mat)
{
// Stores compressed array
int[] compressedArr = {};
int len = mat.GetLength(0);
int len2 = mat.GetLength(1);
for(int i = 0; i < len; i++)
{
int[] col = {};
for (int j = 0; j < len2; j++)
{
col = append(col, mat[j,i]);
}
// Compress all columns
// to a single number
compressedArr = append(compressedArr,
compress(col));
}
return compress(compressedArr);
}
// Driver Code
public static void Main(String[] args)
{
int[,] mat = { { 3, 2, 4 },
{ 5, 6, 1 },
{ 8, 1, 3 } };
Console.WriteLine(getResult(mat));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript Program for the above approach
// Function to compress an
// array to a single number
function append(arr, x)
{
// create a new ArrayList
arr.push(x);
return arr;
}
function compress(arr)
{
// Stores the required integer
let ans = 0;
let getBit = 1;
// Checking for each position
for (let i = 0; i < 32; i++)
{
let S = 0;
let NS = 0;
for (let j = 0; j < arr.length; j++)
{
// Count set and unset bit
let temp = getBit & arr[j];
if (temp == 1) {
S += 1;
}
else {
NS += 1;
}
// If count of set bits exceeds
// count of unset bits
if (S > NS) {
// Add value of set bits to ans
ans += Math.pow(2, i);
}
getBit <<= 1;
}
}
return ans;
}
// Function to compress
// matrix to a single number
function getResult(mat)
{
// Stores compressed array
let compressedArr = [];
let len = mat.length;
let len2 = mat[0].length;
for (let i = 0; i < len; i++)
{
let col = [];
for (let j = 0; j < len2; j++)
{
col = append(col, mat[j][i]);
}
// Compress all columns
// to a single number
compressedArr = append(compressedArr, compress(col));
}
return compress(compressedArr);
}
let mat = [[3, 2, 4 ],[5, 6, 1],[8, 1, 3]];
document.write(getResult(mat));
// This code is contributed by mukesh07.
</script>
Producción:
1
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por rohitsingh07052 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA