Frontend School

Count Pinterest-Worthy Numbers

DSA
medium

Count Pinterest-Worthy Numbers

Medium
Math
Number Theory
Sieve

Overview

Pinterest's content recommendation engine relies on understanding the intrinsic properties of pins to surface relevant content. Beyond explicit tags, we often look for deeper mathematical characteristics that can signify "richness" or "diversity" of a pin's underlying ID or metadata. This problem explores identifying such "Pinterest-worthy" numbers based on two key number theory properties, helping us categorize and prioritize content.

What you need to do / Task

Implement a function countPinterestWorthyNumbers(N: number, K: number) that returns the total count of positive integers x such that 1 <= x <= N and x satisfies both of the following conditions:

  1. Abundant Number: The sum of its proper divisors (all positive divisors of x excluding x itself) is strictly greater than x.
  2. Diverse Prime Factors: The number of distinct prime factors of x is greater than or equal to K.

Input & output

  • Input:
    • N: A positive integer representing the upper bound (inclusive) for the numbers to check.
    • K: A positive integer representing the minimum required number of distinct prime factors.
  • Output:
    • A single integer, the total count of Pinterest-worthy numbers between 1 and N (inclusive).

Clarifications

  • The number 1 has no proper divisors, so its sum of proper divisors is 0. It has 0 distinct prime factors.
  • Prime numbers are not abundant (sum of proper divisors is 1). They have 1 distinct prime factor.
  • Perfect numbers (sum of proper divisors equals x) are NOT considered abundant by this definition (it must be strictly greater).

Examples

1

Example 1

Input:

N = 30, K = 2

Output:

5

Note:

The Pinterest-worthy numbers up to 30 with at least 2 distinct prime factors are: 12, 18, 20, 24, 30. (12: sum proper divisors=16 > 12, distinct prime factors={2,3} count=2; 18: sum proper divisors=21 > 18, distinct prime factors={2,3} count=2; 20: sum proper divisors=22 > 20, distinct prime factors={2,5} count=2; 24: sum proper divisors=36 > 24, distinct prime factors={2,3} count=2; 30: sum proper divisors=42 > 30, distinct prime factors={2,3,5} count=3).

2

Example 2

Input:

N = 100, K = 3

Output:

8

Note:

The Pinterest-worthy numbers up to 100 with at least 3 distinct prime factors are: 30, 42, 60, 66, 70, 78, 84, 90.

3

Example 3

Input:

N = 10, K = 1

Output:

0

Note:

There are no abundant numbers less than or equal to 10. The first abundant number is 12. Therefore, the count is 0.

Constraints

Constraints & assumptions

  • 1 <= N <= 10^6
  • 1 <= K <= 7 (The maximum possible distinct prime factors for N=10^6 is 7: 2357111317 = 510510)
  • The input N and K will always be valid integers within the specified ranges.

Out of scope

  • Handling negative inputs or non-integer inputs.
  • Optimizing for N beyond 10^6 (e.g., using Pollard's rho or other advanced factorization algorithms). A sieve-based approach is expected.

What interviewers evaluate

  • Algorithm Efficiency: The solution should be performant enough to handle N up to 10^6 efficiently, likely requiring a precomputation (sieve) approach.
  • Correctness: Accurately calculating the sum of proper divisors and distinct prime factors for each number.
  • Code Structure & Readability: Clear separation of concerns, well-named variables, and appropriate comments.
  • Edge Cases: Correct handling of small numbers (e.g., 1, primes) and numbers near N.

Loading editor...