Frontend School

Stripe Batch ID Parity

DSA
hard

Stripe Batch ID Parity

Hard
Math
Number Theory
Algorithms

Overview

Stripe processes an immense volume of financial transactions daily. For internal analytics, reconciliation, and load-balancing purposes, transactions are often grouped into batches, each identified by a unique integer ID. These batch IDs sometimes need to satisfy specific mathematical properties to ensure data integrity or optimize system performance. One such property relates to the parity (even or odd) of the sum of positive divisors of a batch ID. Your task is to efficiently count such batch IDs within a given large range.

What you need to do / Task

Implement a function countOddDivisorSumBatches that takes two BigInt numbers, L and R, representing a closed range [L, R]. The function should return the total count of integers N within this range (inclusive) such that the sum of positive divisors of N is odd.

Input & output

  • L: BigInt, the lower bound of the range (inclusive).
  • R: BigInt, the upper bound of the range (inclusive).
  • Returns: BigInt, the total count of numbers N in [L, R] whose sum of positive divisors is odd.

Clarifications

  • The sum of positive divisors of N (sigma(N)) includes 1 and N itself.
  • L and R can be extremely large, up to 10^18, requiring efficient algorithms that do not iterate through the range.
  • The range [L, R] is inclusive, meaning both L and R can be valid batch IDs.

Examples

1

Example 1

Input:

L = 1n, R = 10n

Output:

5n

Note:

The numbers in the range [1, 10] whose sum of positive divisors is odd are: 1 (sigma(1)=1), 2 (sigma(2)=3), 4 (sigma(4)=7), 8 (sigma(8)=15), and 9 (sigma(9)=13). There are 5 such numbers.

2

Example 2

Input:

L = 100n, R = 120n

Output:

1n

Note:

In the range [100, 120], only 100 has an odd sum of positive divisors (sigma(100) = 217). 100 is a perfect square (10^2). No other numbers in this range satisfy the condition.

3

Example 3

Input:

L = 999999999999999900n, R = 1000000000000000000n

Output:

1n

Note:

This large range contains only one number with an odd sum of positive divisors: 1,000,000,000,000,000,000 (which is 10^18, a perfect square).

Constraints

Constraints & assumptions

  • 1 <= L <= R <= 10^18
  • L and R are integers.

What interviewers evaluate

  • Mathematical Insight: The ability to correctly identify and apply the number theory property regarding the parity of the sum of divisors.
  • Algorithmic Efficiency: Developing an algorithm that efficiently counts numbers within a very large range, avoiding linear iteration.
  • Correctness and Precision: Handling large number types (BigInt in JavaScript/TypeScript) correctly to prevent overflow or precision issues, and addressing edge cases.
  • Code Quality: Writing clean, well-structured, and readable code, possibly with helper functions.

Loading editor...