Compress a matrix into a single number using given operations

0 0 6 minutes read

Given a matrix mat[][] of dimension M * N, the task is to first compress it to obtain an array and, then compress it again to obtain a single integer using following operations:

When a matrix is compressed, its value’s binary representation gets compressed.
Therefore, each bit is considered, and if a position of a bit has S set bits and NS non-set bits, then the bit is set for the position if S > NS and unset otherwise.
Each column is compressed to turn the matrix into an array, then that array is compressed further into a single number.

For example, if 5, 2, 3, and 1 gets compressed then their binary representations (101)₂, (010)₂, (011)₂, and (001)₂ gets compressed then for the 0^th and 1^st positions, S ? NS and for the 2^nd position S > NS, then the number modifies to (001)₂ = 1.

Examples:

Input: arr[][] ={{ 3, 2, 4}, {5, 6, 1}, {8, 1, 3}}
Output: 1
Explanation: The array obtained after compressing the given matrix from top is {1, 2, 1 }.Then, the obtained array is compressed to 1.

Input: arr[][] = {{ 5, 3}, {6, 7}}
Output: 0

Approach: The idea is to count the number of set bits for each position. Follow the steps below to solve the problem:

Traverse through each element of each column of a matrix and compress each column to a single number.
Count the number of set bits for each position.
Set the bit for the positions with number of set bits exceeding the number of unset bits.
Calculate the value after deciding whether to set or not to set the bit for each position.
After obtaining an array, apply the same steps to obtain the required integer.

Below is the implementation of the above approach:

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>

Output:

Time Complexity: O(N*M)
Auxiliary Space: O(N)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!