Divisible and Non-divisible Sums Difference

Easy

Amazon

6 views

Topics:

ArraysGreedy AlgorithmsBit Manipulation

You are given positive integers n and m.

Define two integers as follows:

num1: The sum of all integers in the range [1, n] (both inclusive) that are not divisible by m.
num2: The sum of all integers in the range [1, n] (both inclusive) that are divisible by m.

Return the integer num1 - num2.

Example 1:

Input: n = 10, m = 3 Output: 19 Explanation: In the given example:

Integers in the range [1, 10] that are not divisible by 3 are [1,2,4,5,7,8,10], num1 is the sum of those integers = 37.
Integers in the range [1, 10] that are divisible by 3 are [3,6,9], num2 is the sum of those integers = 18. We return 37 - 18 = 19 as the answer.

Example 2:

Input: n = 5, m = 6 Output: 15 Explanation: In the given example:

Integers in the range [1, 5] that are not divisible by 6 are [1,2,3,4,5], num1 is the sum of those integers = 15.
Integers in the range [1, 5] that are divisible by 6 are [], num2 is the sum of those integers = 0. We return 15 - 0 = 15 as the answer.

Write a function to solve this problem efficiently.

Divisible and Non-divisible Sums Difference

Easy

Amazon

6 views

Topics:

ArraysGreedy AlgorithmsBit Manipulation

You are given positive integers n and m.

Define two integers as follows:

num1: The sum of all integers in the range [1, n] (both inclusive) that are not divisible by m.
num2: The sum of all integers in the range [1, n] (both inclusive) that are divisible by m.

Return the integer num1 - num2.

Example 1:

Input: n = 10, m = 3 Output: 19 Explanation: In the given example:

Integers in the range [1, 10] that are not divisible by 3 are [1,2,4,5,7,8,10], num1 is the sum of those integers = 37.
Integers in the range [1, 10] that are divisible by 3 are [3,6,9], num2 is the sum of those integers = 18. We return 37 - 18 = 19 as the answer.

Example 2:

Input: n = 5, m = 6 Output: 15 Explanation: In the given example:

Integers in the range [1, 5] that are not divisible by 6 are [1,2,3,4,5], num1 is the sum of those integers = 15.
Integers in the range [1, 5] that are divisible by 6 are [], num2 is the sum of those integers = 0. We return 15 - 0 = 15 as the answer.

Write a function to solve this problem efficiently.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the integer `n` and the divisor `m`? What is the expected data type and range for both?
Can the input array contain negative numbers, zeros, or duplicate values?
If the sum of numbers divisible by `m` and the sum of numbers not divisible by `m` are equal, what should I return?
Is `n` guaranteed to be greater than or equal to 1, and that the array will always contain `n` elements?
Could you provide a few examples of inputs and their expected outputs to ensure my understanding of the problem is correct?

Brute Force Solution

Approach

The brute force approach for this problem involves checking every single number within the given range and then calculating a sum based on whether it's divisible by a certain number. We then calculate another sum for the numbers that are not divisible and find the difference.

Here's how the algorithm would work step-by-step:

Go through each number, one by one, starting from 1 and continuing up to the given limit.
For each number, check if it can be divided evenly by the provided divisor (with no remainder).
If the number is divisible, add it to a running total, which we can call the 'divisible sum'.
If the number is not divisible, add it to a different running total, which we can call the 'non-divisible sum'.
Once you have checked every number up to the limit, subtract the 'non-divisible sum' from the 'divisible sum'.
The result of this subtraction is your final answer.

Code Implementation

def divisible_and_non_divisible_sums_difference(limit, divisor):
    divisible_sum = 0
    non_divisible_sum = 0

    for number in range(1, limit + 1):
        # Check if the number is divisible by the divisor.
        if number % divisor == 0:

            divisible_sum += number

        # If it's not divisible, accumulate to non_divisible_sum.
        else:

            non_divisible_sum += number

    # The problem asks us to subtract non_divisible_sum from divisible_sum
    return divisible_sum - non_divisible_sum

Big(O) Analysis

Time Complexity

O(n) – The provided solution iterates through each number from 1 to n, where n is the given limit. Inside the loop, a divisibility check (a constant-time operation) is performed for each number. Therefore, the number of operations grows linearly with the input size n, resulting in a time complexity of O(n).

Space Complexity

O(1) – The plain English explanation describes calculating two running sums: the divisible sum and the non-divisible sum. These sums are stored in two variables. Since we only use a fixed number of variables (two in this case) irrespective of the input limit N, the space required remains constant. Therefore, the space complexity is O(1).

Optimal Solution

Approach

The optimal approach involves calculating two sums and finding their difference directly. We calculate the sum of numbers divisible by a given number and the sum of numbers that are not, within a specified range. Then, we subtract the second sum from the first to find the final difference.

Here's how the algorithm would work step-by-step:

Calculate the sum of all numbers from 1 to the upper limit that are divisible by the specified divisor.
Calculate the sum of all numbers from 1 to the upper limit that are NOT divisible by the specified divisor.
Subtract the sum of the non-divisible numbers from the sum of the divisible numbers. The result is the answer.

Code Implementation

def divisible_and_non_divisible_sums_difference(upper_limit, divisor):
    divisible_sum = 0
    non_divisible_sum = 0

    # Sum all numbers divisible by divisor.
    for number in range(1, upper_limit + 1):
        if number % divisor == 0:
            divisible_sum += number

    # Sum all numbers NOT divisible by divisor.
    for number in range(1, upper_limit + 1):
        if number % divisor != 0:
            non_divisible_sum += number

    # Calculate the difference.
    sums_difference = divisible_sum - non_divisible_sum

    return sums_difference

Big(O) Analysis

Time Complexity

O(n) – The solution iterates through the numbers from 1 to n (the upper bound) to calculate the sum of divisible numbers and the sum of non-divisible numbers. Calculating each of these sums involves a single loop that runs up to n times. Therefore, the time complexity is directly proportional to the input size n, making it O(n).

Space Complexity

O(1) – The provided approach calculates two sums by iterating through the numbers from 1 to the upper limit without using any auxiliary data structures that scale with the input size. It only requires a few variables to store the running sums of divisible and non-divisible numbers. Thus, the extra memory used remains constant regardless of the input size N (the upper limit), leading to a space complexity of O(1).

Edge Cases

Case	How to Handle
n is zero or negative	Return 0 immediately, as the problem specifies positive n.
n is very large, leading to potential integer overflow in sums	Use 64-bit integers (long) to store sums to avoid overflow.
num1 or num2 is zero	Handle division by zero by adding conditional checks.
num1 and num2 are both 1	The condition i % num1 == 0 and i % num2 == 0 reduces to i % 1 == 0, which is always true, potentially affecting performance.
num1 and num2 are equal	The calculations will still be correct but should be tested.
All numbers from 1 to n are divisible by num1 or num2	This results in nonDivisibleSum being 0 and checks for potential unexpected behaviors.
n is close to the maximum integer value	Check for potential integer overflow when calculating sums and use long if needed.
num1 and num2 are both larger than n	divisibleSum will be 0 as there are no numbers from 1 to n divisible by num1 or num2.