Количество отсортированных троек (a, b, c), произведение которых не превосходит N

Для заданного целого числа N задача состоит в том, чтобы найти количество троек (a, b, c), таких что a <= b <= c и a * b * c <= N.

Примеры:

Input: N = 5
Output: 6
Explanation: The triplets that follow the required conditions are (1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 1, 4), (1, 1, 5) and (1, 2, 2). Hence the count of value triplets is 6. 

Input: N = 20
Output: 40

Подход: Данная проблема может быть решена на основе следующих наблюдений:

• Поскольку a <= b <=c , можно заметить, что значение a должно лежать в диапазоне [1, N ^1/3 ] .
• Точно так же для данного a значение b должно лежать в диапазоне [a, (N/a) ^1/2 ] .
• Точно так же, когда значения a и b фиксированы, значение c должно лежать в диапазоне [b, N/(a*b)] . Следовательно, количество возможных значений c равно количеству целых чисел в диапазоне [b, N/(a*b)] . Следовательно, для каждого допустимого a и b число возможных значений c равно N/(a*b) – b + 1 .

Таким образом, используя приведенные выше наблюдения, ниже приведена реализация вышеописанного подхода:

Временная сложность: O(N ^2/3 )
Вспомогательное пространство: O(1)