All challenges
Medium 0 solved 0% acceptance

Highly Divisible Triangular Number

Find the first triangular number that has at least d divisors.

What you'll learn

  • Count divisors from a prime factorization
  • Use the formula for triangular numbers
  • Split a product of coprime factors

Problem

Triangular numbers count the dots in a triangle of rows 1, 2, 3, ...: T(1) = 1, T(2) = 3, T(3) = 6, and T(k) = k(k + 1) / 2. Walk through them in order and stop at the first one with at least d positive divisors (1 and the number itself count).

Implement highly_divisible_triangular(d).

Counting divisors one by one is too slow for the larger cases. Factor the number instead: if n = p^a × q^b × ..., it has (a + 1)(b + 1)... divisors. Since k and k + 1 share no factor, you can factor them separately.

Input

d: The number of divisors needed.

Output

Return the first triangular number with at least d divisors.

Constraints

1 ≤ d ≤ 300

Examples

Example 1
Input:
d = 4

Expected output:
expected = 6
Input:
long long d = 4;

Expected output:
long long expected = 6;
Input:
long d = 4;

Expected output:
long expected = 6;

Explanation

1 has one divisor and 3 has two, but 6 has four (1, 2, 3, 6), so the answer is 6.

Example 2
Input:
d = 9

Expected output:
expected = 36
Input:
long long d = 9;

Expected output:
long long expected = 36;
Input:
long d = 9;

Expected output:
long expected = 36;

Explanation

28 has six divisors and 36 = 2² × 3² has 3 × 3 = 9 (1, 2, 3, 4, 6, 9, 12, 18, 36), so the answer is 36.

How to approach it

Try on your own first, then open one hint at a time.

Hint 1

T(k) = k(k + 1) / 2, and k and k + 1 have no common factor.

Hint 2

Halve whichever of k and k + 1 is even, then count the divisors of each part.

Hint 3

The divisor count of a product of coprime numbers is the product of their counts.

Expected complexity

O(K √K) time for K triangular numbers tried, O(1) extra space

References

This challenge is adapted for CodeUtility. Follow the statement and constraints above.

The best passing solution of each coder. Faster, smaller and better-reviewed solutions rank higher.

No passing solutions yet. Solve it to take first place.

Learn from others

Community solutions

No published solutions yet. Solve this challenge to share the first one.