How should I practice Minimum Row Deletions to Prevent a Target OR?

Start by reading the full statement, solve the visible examples, then compare the pattern against related InMobi onsite interview problems in FastPrep.

Is Minimum Row Deletions to Prevent a Target OR associated with InMobi?

FastPrep tags this as a InMobi onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Array

Minimum Row Deletions to Prevent a Target OR

Learn this problem

● Hard

InMobiFULLTIMEONSITE INTERVIEW

Problem statement

You are given a non-empty rectangular binary matrix rows. Each row represents a non-negative integer in binary, with the leftmost column as the most significant bit. You are also given a positive integer target representable with the same number of bits.

The target is formable if the bitwise OR of one or more remaining rows equals target.

You may delete any rows. Return the minimum number of rows that must be deleted so that target is no longer formable. If the target is not formable initially, return 0.

Function

minimumRowsToDeleteForTargetOr(rows: int[][], target: int) → int

Examples

Example 1

rows = [[0,0,0,0,1],[0,0,1,0,0],[0,1,0,1,0],[0,0,1,1,0],[0,0,1,1,1]]target = 14return = 1

The target is 01110. It can be formed by the rows 00100 | 01010 or 01010 | 00110. Deleting the single row 01010 prevents every valid formation.

Example 2

rows = [[0,1],[1,0]]target = 3return = 1

Both rows are needed to form 11. Deleting either one prevents the target.

Example 3

rows = [[0,0,1],[1,0,0]]target = 7return = 0

No row contains the middle bit, so 111 is not formable even before any deletion.

Constraints

1 ≤ rows.length ≤ 100,000
1 ≤ rows[i].length ≤ 30
All rows have the same length.
rows[i][j] is either 0 or 1.
1 ≤ target < 2^rows[i].length