Frontend School

Divisor Sum Parity Check

DSA
easy

Divisor Sum Parity Check

Easy
Math
Number Theory
Divisors

Overview

In various data analytics and system monitoring scenarios at LinkedIn, understanding the inherent properties of numbers can be crucial for anomaly detection or data classification. For instance, patterns related to a number's divisors might indicate specific characteristics of user activity or system load. This problem explores a fundamental number theory concept: the parity of the sum of a number's proper divisors.

What you need to do / Task

You are tasked with implementing a function that determines whether the sum of the proper divisors of a given positive integer n is even or odd. A proper divisor of n is any positive divisor of n other than n itself.

Input & output

  • Input:
    • n: An integer representing the number for which to check the sum of proper divisors.
  • Output:
    • boolean: Return true if the sum of n's proper divisors is even, and false otherwise.

Clarifications

  • What are proper divisors? Proper divisors are all positive divisors of n excluding n itself. For example, for n=6, proper divisors are 1, 2, 3.
  • What if n=1? The number 1 has no proper divisors. In such cases, the sum of proper divisors is considered 0. 0 is an even number.

Examples

1

Example 1

Input:

n = 6

Output:

true

Note:

Proper divisors of 6 are 1, 2, 3. Their sum is 1 + 2 + 3 = 6. Since 6 is even, the function returns true.

2

Example 2

Input:

n = 7

Output:

false

Note:

Proper divisors of 7 are 1. Their sum is 1. Since 1 is odd, the function returns false.

3

Example 3

Input:

n = 12

Output:

true

Note:

Proper divisors of 12 are 1, 2, 3, 4, 6. Their sum is 1 + 2 + 3 + 4 + 6 = 16. Since 16 is even, the function returns true.

4

Example 4

Input:

n = 1

Output:

true

Note:

The number 1 has no proper divisors. The sum of proper divisors is considered 0. Since 0 is even, the function returns true.

Constraints

Constraints & assumptions

  • 1 <= n <= 10^5
  • n is always a positive integer.

Out of scope

  • Optimizations for n values significantly larger than 10^5 (e.g., n up to 10^12).
  • Complex prime factorization algorithms like Pollard's rho or Miller-Rabin primality test.

What interviewers evaluate

  • Ability to correctly identify and sum proper divisors.
  • Correct handling of edge cases, particularly n=1.
  • Efficiency of the algorithm for finding divisors (e.g., O(sqrt(n)) approach).
  • Code clarity, readability, and logical structure.

Loading editor...