Frontend School

Sum of Exclusive Prime Multiples

DSA
medium

Sum of Exclusive Prime Multiples

Medium
Math
Number Theory
Inclusion-Exclusion

Overview

In financial systems, analyzing numbers based on their divisibility properties is a common task, crucial for areas like transaction categorization, fraud detection, or specialized reporting. This problem explores a specific divisibility pattern: identifying and summing numbers whose prime factors are exclusively from a given set of 'special' primes.

What you need to do / Task

Given an integer N and a list of distinct prime numbers primes, your task is to find the sum of all positive integers x such that 1 <= x <= N and x is divisible by exactly one prime from the primes list.

Input & output

  • N: An integer representing the upper bound (inclusive) for numbers to consider.
  • primes: An array of distinct prime numbers.
  • Returns: A single integer, the sum of all x satisfying the condition.

Clarifications

  • The primes array will only contain distinct prime numbers.
  • N can be a large number, so an efficient solution is required.
  • If no such numbers exist within the range 1 to N, return 0.

Examples

1

Example 1

Input:

N = 10, primes = [2, 3]

Output:

36

Note:

Numbers up to 10:

  • 2 (divisible by 2 only)
  • 3 (divisible by 3 only)
  • 4 (divisible by 2 only)
  • 5 (not divisible by 2 or 3)
  • 6 (divisible by both 2 and 3 - excluded)
  • 7 (not divisible by 2 or 3)
  • 8 (divisible by 2 only)
  • 9 (divisible by 3 only)
  • 10 (divisible by 2 only) Sum of numbers divisible by exactly one of [2, 3]: 2 + 3 + 4 + 8 + 9 + 10 = 36.
2

Example 2

Input:

N = 20, primes = [2, 5]

Output:

100

Note:

Numbers up to 20 divisible by exactly one of [2, 5]:

  • Only by 2: 2, 4, 6, 8, 12, 14, 16, 18. (Sum = 80)
  • Only by 5: 5, 15. (Sum = 20) Numbers like 10, 20 are divisible by both 2 and 5, so they are excluded. Total sum = 80 + 20 = 100.
3

Example 3

Input:

N = 100, primes = [7, 11, 13]

Output:

1594

Note:

For N=100, the products of any two distinct primes from [7, 11, 13] (e.g., 711=77, 713=91, 11*13=143) are either greater than N or have only one multiple within N (e.g., 77, 91). Products of three primes are always > N.

  • Numbers divisible by 7 only: Sum of multiples of 7 up to 100 that are not multiples of 11 or 13.
    • Multiples of 7: 7, 14, ..., 98. Sum = 735.
    • None of these are also multiples of 11 or 13 within N=100. So, contribution from 7 is 735.
  • Numbers divisible by 11 only: Sum of multiples of 11 up to 100 that are not multiples of 7 or 13.
    • Multiples of 11: 11, 22, ..., 99. Sum = 495.
    • None of these are also multiples of 7 or 13 within N=100. So, contribution from 11 is 495.
  • Numbers divisible by 13 only: Sum of multiples of 13 up to 100 that are not multiples of 7 or 11.
    • Multiples of 13: 13, 26, ..., 91. Sum = 364.
    • None of these are also multiples of 7 or 11 within N=100. So, contribution from 13 is 364. Total sum = 735 + 495 + 364 = 1594.

Constraints

Constraints & assumptions

  • 1 <= N <= 10^8
  • 1 <= primes.length <= 10
  • 2 <= primes[i] <= 1000
  • All elements in primes are distinct prime numbers.
  • The final sum is guaranteed to fit within a standard 64-bit integer type (e.g., JavaScript's number type).

Out of scope

  • Validating whether elements in primes are indeed prime or distinct. Assume input validity.
  • Handling negative values for N or elements in primes.

What interviewers evaluate

  • Correctness of Logic: The solution must correctly apply mathematical principles, such as the Inclusion-Exclusion Principle, to accurately sum the required numbers.
  • Algorithmic Efficiency: The approach should be optimized to handle large values of N and primes.length efficiently, avoiding brute-force iteration where unnecessary.
  • Code Quality: Clarity, organization, and maintainability of the code are important, including appropriate use of helper functions.
  • Edge Case Handling: The solution should correctly manage edge cases, such as an empty primes list or N being too small to contain any valid multiples.

Loading editor...