ojas - 2 months ago 15

Java Question

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

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

Source (Stackoverflow)

Comments