Most Ones in a Matrix With a Zero Power
Updated
Problem statement
A is an n × n matrix whose entries are all 0 or 1. Matrix products use ordinary integer arithmetic, and A^k is the product of k copies of A (so A^1 = A).
Return the largest possible number of entries equal to 1 in A such that A^k is the zero matrix.
Function
mostOnes(n: int, k: int) → longExamples
Example 1
n = 4k = 2return = 4This is the interview question for a 4 by 4 matrix. Put 1s in the top-right 2 by 2 block: rows 1 and 2, columns 3 and 4. Every 1 leads from row 1 or 2 into column 3 or 4, and rows 3 and 4 are all 0, so no two 1s chain together and A^2 = 0. That is 4 ones, and the editorial shows 5 is impossible.
Example 2
n = 5k = 3return = 8Split the 5 indices into groups of sizes 2, 2 and 1, and put a 1 in row i, column j whenever i's group comes before j's group. That gives 2 × 2 + 2 × 1 + 2 × 1 = 8 ones, and a chain of 1s can pass through at most 3 groups, so A^3 = 0.
Example 3
n = 3k = 3return = 3With k = n = 3, each index is its own group: all 3 entries above the diagonal can be 1. A 4th one would close a loop or sit on the diagonal, and then no power of A is ever 0.
Constraints
1 <= k <= n <= 10^6
More Susquehanna International Group (SIG) Phone Screen questions
- Dice Sum That Is a Multiple of mPHONE SCREEN · Seen Nov 2026
- Find Median from Data StreamPHONE SCREEN · Seen Nov 2026
- Painting Arcs to Nearest Neighbors on a CirclePHONE SCREEN · Seen Sep 2026
- Filter Movies by Inclusive Year RangePHONE SCREEN · Seen Jul 2026
- Best Single Reroll for Five DicePHONE SCREEN · Seen Feb 2026
- Catching the Bus to the MoviePHONE SCREEN · Seen Jan 2026
- Two Dice Summing to a TargetPHONE SCREEN · Seen Jan 2026
- Median of Uniform Draws in an IntervalPHONE SCREEN · Seen Oct 2025
- One Number Is the Average of the Other TwoPHONE SCREEN · Seen Jun 2025
- Which Coin Pattern Shows Up FirstPHONE SCREEN · Seen May 2025
Similar questions at other companies
- Apartment Housemate PreferencesGoogle · PHONE SCREENGoogle interview questions
- Reorderable Task Scheduler With CooldownWaymo · PHONE SCREENWaymo interview questions
- Minimum Operations to Make Every Array Element OneOtter.ai · PHONE SCREENOtter.ai interview questions
- Unit Conversion Across Independent FamiliesApple · PHONE SCREENApple interview questions
- Evenly Schedule Vehicle InspectionsAmazon · PHONE SCREEN
- Fair Electoral Vote ApportionmentBloomberg LP · PHONE SCREENBloomberg LP interview questions
- IP Address to CIDR BlocksOpenAI · PHONE SCREENOpenAI interview questions
- Frog Position After T SecondsInMobi · PHONE SCREENInMobi interview questions
- Minimum Full Glasses for an Exact Water VolumeMarshall Wace · PHONE SCREENMarshall Wace interview questions
- Count Pairs of Nodes That Cannot Reach Each OtherAdobe · PHONE SCREENAdobe interview questions