ojas - 2 months ago 15
Java Question

# Find the Maximum Step in a Staircase

I am solving a staircase problem and came up with multiple solutions in mind. It looks like below:

Question: You will be given number of stairs say N. What is the maximum step you can make?

For N = 5, The maximum step you can make is 2 because

5 = 1 + 2 + 2

Similarly for 8, its, 8 = 1 + 2 + 3 + 2, maximum step is 3

Similarly for 16, its, 16 = 1 + 2 + 3 + 4 + 5 + 1, maximum step is 5.

When the next number is less than previous then the series will stop.

Clearly, The maximum step is maximum number in the series.

Solution 1:

I came up with a simple solution. It works fine but not optimized.
Below is the following code:

public static long stairCase(long N) {
long i = 1;
long curr = N;
while (i < N) {
curr = curr - i;
if (i >= curr) {
return i;
}
i = i + 1;
}
return i;
}

Solution 2:

Then i figured out that its n(n+1) / 2. So, if i put n(n+1)/2 = no. of
Stairs.I cant get the solution by calculating its roots and taking
highest of the roots. My Code looks like below but it doesn't works
for N = 16 and many other cases.

int b = 1;
int var = (1) - (4 * -c);
double temp1 = Math.sqrt(var);

double root1 = (-b + temp1) / (2 * a);
double root2 = (-b - temp1) / (2 * a);
double root1Abs = Math.abs(root1);
double root2Abs = Math.abs(root2);
return (long) (root1Abs > root2Abs ? Math.floor(root1Abs) : Math
.floor(root2Abs));

Solution 3:

I came up with another solution but still its not working for N = 4
and many other cases. Below is my code:

double answer = Math.sqrt(c * 2);

Does Anyone have the optimized solutions(preferably in constant time) because the input is too big(long).

m = number of stair

n = result

The equation is

n * (n+1) < 2m

The solution is

n < (sqrt(8*m+1)-1)/2

We try to find maximum integer so

n = floor((sqrt(8*m+1)-1)/2)

The Java Code:

import java.io.*;

public class Solution {

public static int staircase(int m){
return (int) Math.floor((Math.sqrt(8*(double)m+1)-1)/2);
}

public static void main(String[] args){
System.out.println("Result:"+staircase(16));
}
}
Source (Stackoverflow)