Petya and Staircases · Interview Problem

Back to problems

Codeforces

Easy

Math

Arrays

Petya and Staircases

Count how many staircases of a given total size can be built using step sizes that divide the total evenly.

Acceptance 0%

Start Practice

Also Available On

Other platform versions and source mappings for the same problem.

Codeforces 362B

gfg

Problem Statement

Problem

Petya wants to build a staircase with a total of $n$ cubes. A staircase is formed by several steps, where each step has a positive integer height, and the step heights are strictly increasing from left to right.

A valid staircase must use exactly $n$ cubes in total. Among all possible staircases, Petya is interested in those where the greatest common divisor of all step heights is greater than 1, so that every step height is divisible by the same integer larger than 1.

Your task is to determine the largest possible number of steps in such a staircase. If no such staircase exists, output 0.

Notes

Step heights must be positive integers.
The staircase must use all $n$ cubes exactly once.
Heights are strictly increasing, so a sequence like $1,2,3 $is valid, but \$ 1,1,2$ is not.

Input Format

The first line contains one integer $n$ .
$n$ is the total number of cubes.

Output Format

Print one integer: the maximum number of steps in a valid staircase, or 0 if it is impossible.

Constraints

$1 \le n$ is an integer.
The exact official bounds are not provided in the source metadata, but the intended solution is based on checking divisors of $n$ .

Examples

Sample cases returned by the problem API.

Example 1

Input

Output

Explanation

One valid staircase is heights 2 and 4, which are strictly increasing and sum to 6. No staircase with more than 2 steps satisfies the condition.

Premium problem context

Unlock deeper context for this problem

Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.

Guided hints

Editorial and discussion links

Concept map and variants

Track your progress