ojas 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);
return (long) (Math.floor(answer));


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

Answer

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));
    }
}
Comments