LeetCode Entry

1513. Number of Substrings With Only 1s

16.11.2025 medium 2025 kotlin rust

Substrings of ones

1513. Number of Substrings With Only 1s medium blog post substack youtube

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/1175

Problem TLDR

Substrings of ones #medium #counting

Intuition

Sum the separate islands of ones. Each island length is n(n+1)/2 arithmetic sum.

Approach

• or compute the arithmetic sum on the go

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(1)\)

Code

// 21ms
    fun numSub(s: String) = s.fold(0 to 0) { (r,curr), c ->
        val curr = (c-'0')*curr + (c-'0')
        (r + curr) % 1000000007 to curr
    }.first

// 0ms
    pub fn num_sub(s: String) -> i32 {
        s.bytes().fold((0, 0), |(r, curr), c| {
            let curr = (c-b'0')as i32*curr + (c-b'0')as i32;
            ((r+curr)%1000000007, curr)
        }).0
    }