Saturday, 23 Oct 2021

# Sum of numbers obtained by the count of set and non-set bits in diagonal matrix elements

Sum of numbers obtained by the count of set and non-set bits in diagonal matrix elements
Given a square matrix mat[][] of dimension N*N, convert the elements present in both the diagonals to their respective binary representations and perform the following operations:
For every position of bits, count the number of set bits and non-set bits in those binary representations.
If count of set bits exceeds that of non-set bits, place 0 at that position for a new number. Otherwise, place 1 at that position.
Finally, print the sum of the two generated numbers.
Examples:

Input: mat[][] = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]Output: 8Explanation:For the primary diagonal, the binary representation of each element is:1 = (0001)25 = (0101)29 = (1001)2At bit position 0, number of set bits(=3)>number of non-set bits(=0)At bit position 1, number of set bits(=0)number of non-set bits(=1)Therefore, after processing the primary diagonal, the number generated is (111)2 = 7.Hence, the required sum = 1 + 7 = 8.
Input: mat[][] = [[2, 3], [3, 9]]Output: 3

Naive Approach: The simplest approach is to traverse the matrix and store the primary diagonal elements in an array and the secondary diagonal elements in another array. Then find the sum of the numbers generated by iterating over the set bits of the elements in both the arrays.Time Complexity: O(N2)Auxiliary Space: O(1) Efficient Approach: The above approach can be optimized by finding the diagonal elements using a single loop. Follow the steps below to solve the problem:
For Principal Diagonal elements: Iterate a loop until N, where N is the number of columns, and store mat[i][i] where i is the index variable.
For Secondary Diagonal elements: Iterate a loop until N, where N is the number of columns and store mat[i][k], where i is the index variable and K = N – 1. Decrease K until i < N. For finding the numbers for each set of diagonal elements, perform the following steps: Initialize a variable, say ans as 0, to store the resultant number. Iterate over the range [0, 31] using variable i and perform the following: Initialize S and NS as 0, to store the number of set and non-set bits respectively at position i. Traverse the diagonal elements using variable j and if arr[j] is set at position i, increment S by 1, else increment NS by 1. If the value of S is greater than NS, set the bit at position i of ans. After completing the above steps, the value of ans is the number generated for each set of diagonal elements. Repeat the above steps for the other sets of diagonal elements, and print the sum of the two numbers generated. Below is the implementation of the above approach: Python3    def processDiagonal(arr):           ans = 0        getBit = 1           for i in range(32):                      S = 0     NS = 0                 for j in arr:                              if getBit&j:         S += 1                         else:         NS += 1                           if S > NS:
ans += 2**i
getBit