FIFA-2022 Career Guide Free Tutorials Go to Your University Placement Preparation 
0 like 0 dislike
295 views
in Coding Questions by Goeduhub's Expert (2.3k points)

We have a two dimensional matrix A where each value is 0 or 1.

A move consists of choosing any row or column, and toggling each value in that row or column: changing all 0s to 1s, and all 1s to 0s.

After making any number of moves, every row of this matrix is interpreted as a binary number, and the score of the matrix is the sum of these numbers.

Return the highest possible score.

 

    Example 1:

    Input: [[0,0,1,1],[1,0,1,0],[1,1,0,0]]
    Output: 39
    Explanation:
    Toggled to [[1,1,1,1],[1,0,0,1],[1,1,1,1]].
    0b1111 + 0b1001 + 0b1111 = 15 + 9 + 15 = 39

     

    Note:

    1. 1 <= A.length <= 20
    2. 1 <= A[0].length <= 20
    3. A[i][j] is 0 or 1.

    1 Answer

    0 like 0 dislike
    by Goeduhub's Expert (2.3k points)
     
    Best answer

    Assume A is M * N.

    A[i][0] is worth 1 << (N - 1) points, more than the sum of (A[i][1] + .. + A[i][N-1]).

    We need to toggle all A[i][0] to 1, here I toggle all lines for A[i][0] = 0.

    A[i][j] is worth 1 << (N - 1 - j)

    For every col, I count the current number of 1s.

    After step 1, A[i][j] becomes 1 if A[i][j] == A[i][0].

    if M - cur > cur, we can toggle this column to get more 1s.

    max(cur, M - cur) will be the maximum number of 1s that we can get.

    Complexity:

    Time O(MN)

    Space O(1)

    class Solution:

        def matrixScore(self, A: List[List[int]]) -> int:

            M, N = len(A), len(A[0])

            res = (1 << N - 1) * M

            for j in range(1, N):

                cur = sum(A[i][j] == A[i][0] for i in range(M))

                res += max(cur, M - cur) * (1 << N - 1 - j)

            return res

    eg : ans = Solution()

    ans.matrixScore( [[0,0,1,1],[1,0,1,0],[1,1,0,0]])

    Output -

    39

    Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

    Best Data Science Online Courses[Lists] on:-

    Claim your 10 Days FREE Trial for Pluralsight.

    Best Data Science Courses on Datacamp
    Best Data Science Courses on Coursera
    Best Data Science Courses on Udemy
    Best Data Science Courses on Pluralsight
    Best Data Science Courses & Microdegrees on Udacity
    Best Artificial Intelligence[AI] Courses on Coursera
    Best Machine Learning[ML] Courses on Coursera
    Best Python Programming Courses on Coursera
    Best Artificial Intelligence[AI] Courses on Udemy
    Best Python Programming Courses on Udemy

    Related questions

    0 like 0 dislike
    1 answer 340 views
    asked Sep 8, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
    0 like 0 dislike
    1 answer 674 views
    asked Sep 7, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
    0 like 0 dislike
    1 answer 3.1k views
    asked Sep 14, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
    0 like 0 dislike
    1 answer 950 views
    asked Sep 14, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)
    0 like 0 dislike
    1 answer 4.2k views
    asked Sep 11, 2020 in Coding Questions by Vaibhav98 Goeduhub's Expert (2.3k points)

     Important Lists:

    Important Lists, Exams & Cutoffs Exams after Graduation PSUs

     Goeduhub:

    About Us | Contact Us || Terms & Conditions | Privacy Policy ||  Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 

     

    Free Online Directory

    ...