Given a Number N Sum 1 to N-1 | Dataford Interview Questions

During QA validation of large totals in the Coupa Supplier Portal, you need to compute the sum of every integer from 1 through N - 1. Because N may contain hundreds of thousands of digits, you must not iterate through the range or convert the entire value to a native integer.

Return the result modulo mod.

Formal Specification

Implement sum_before_mod(n, mod), where:

n is a decimal string representing an integer N >= 1.
mod is a positive integer.
The output is an integer equal to (1 + 2 + ... + (N - 1)) % mod.

Use the identity N * (N - 1) / 2, but divide one factor by 2 before applying the modulo so the method works even when mod is even.

Constraints

1 <= len(n) <= 100000
n represents an integer N >= 1
1 <= mod <= 10^18
n contains only decimal digits
The algorithm must not enumerate the range from 1 through N - 1
The algorithm must not use floating-point arithmetic

Function Signature

def sum_before_mod(n, mod):

Your question is Given a Number N Sum 1 to N-1. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem