FastPrepMost Ones in a Matrix With a Zero Power
Problems/Most Ones in a Matrix With a Zero Power

Most Ones in a Matrix With a Zero Power

Susquehanna International Group (SIG) logoSusquehanna International Group (SIG)● MediumNEW GRADINTERNPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Two SIG reports, both from technical phone rounds, include a puzzle about a matrix that becomes zero when it is squared. A new grad report posted in August 2020 (third round) wants the most ones such a matrix can hold when every entry is 0 or 1. An internship report posted in April 2019 (third round) puts it in terms of nonzero entries and does not limit what the entries may be.

Here, the entries are 0 or 1, as in the first report, and products use ordinary integer arithmetic, which neither report states. With any real entries every entry could be nonzero, as the editorial shows. The size n (1 to 10^6) is an input, and a power k (1 to n) extends A^2 = 0 to A^k = 0. The function returns the largest number of ones. k = 2 is the interview question, and n = 4, k = 2 is the first example.

Our version is about 80% the same as the reported questions.

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) → long

Examples

Example 1

n = 4k = 2return = 4

This 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 = 8

Split 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 = 3

With 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

Interview reports that mention this question

  • SIG Quant Research Intern Interviews: 60 Experiences
  • SIG Quant Researcher New Grad Interviews: 49 Experiences

Susquehanna International Group (SIG) interview experiences

  • SIG Quant Researcher Experienced Hire Interviews: 11 Experiences
  • SIG Quant Researcher Intern Interviews: 1 Experience
  • SIG Quant Second-Round Tech Screen: 1 Experience
All Susquehanna International Group (SIG) interview questionsSee Susquehanna International Group (SIG) hiring insights
Saved
class Solution {
    public long mostOnes(int n, int k) {
        // Write your code here.
    }
}
Checking account…