We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Divisible and Non-divisible Sums Difference

Number: 3172

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Given two positive integers n and m, calculate the difference between the sum of all integers between 1 and n that are not divisible by m (num1) and the sum of all integers that are divisible by m (num2). The answer is num1 - num2.

Key Insights

  • Recognize that the total sum of numbers from 1 to n can be computed with the formula: totalSum = n * (n + 1) / 2.
  • Compute the sum of multiples of m in the range [1, n] without iterating by finding the number of multiples p = n // m, then using the formula: num2 = m * p * (p + 1) / 2.
  • The sum of non-multiples is then: num1 = totalSum - num2.
  • Finally, the result is simply num1 - num2.

Space and Time Complexity

Time Complexity: O(1) – We compute sums directly using arithmetic formulas. Space Complexity: O(1) – Only a constant amount of extra space is used.

Solution

We leverage mathematical formulas to compute the sum quickly. First, compute the total sum of numbers from 1 to n. Then, calculate how many numbers in this range are multiples of m using integer division. With that count, derive the sum of multiples (num2) using the formula for the sum of the first 'p' natural numbers, multiplied by m. Lastly, subtract num2 from the total sum to get the sum of non-multiples (num1) and compute the final result by subtracting num2 from num1. This approach avoids an explicit iteration over the range, achieving a constant time solution.

Code Solutions

# Python solution with comments

def divisibleNonDivisibleDifference(n: int, m: int) -> int:
    # Calculate total sum of numbers from 1 to n using arithmetic series formula
    total_sum = n * (n + 1) // 2
    
    # Determine the number of multiples of m in [1, n]
    num_multiples = n // m
    
    # Calculate the sum of all multiples of m using formula for sum of first num_multiples numbers
    sum_multiples = m * num_multiples * (num_multiples + 1) // 2
    
    # The sum of numbers not divisible by m is the difference between total sum and sum of multiples
    sum_non_multiples = total_sum - sum_multiples
    
    # Return the difference between non-divisible sum and divisible sum
    return sum_non_multiples - sum_multiples

# Example usage
print(divisibleNonDivisibleDifference(10, 3))  # Expected output: 19
← Back to All Questions