You are given S a sequence of n integers S = s1, s2, ..., sn. Please, compute if it is possible to split S into two parts : s1, s2, ..., si and si+1, si+2, ….., sn (1 <= i < n) in such a way that the first part is strictly decreasing while the second is strictly increasing one. First take n as input and then take n more integers, output yes or no.
This is what i tried
import java.util.Scanner;
public class Sequence {
public static int c;
public static void main(String[] args) {
int n;
int count = 0;
Scanner s = new Scanner(System.in);
n = s.nextInt();
int a[] = new int [n];
for(int i = 0; i<n; i++) // loop for taking input
{
a[i] = s.nextInt();
}
for(int i = 0; i<n-2; i++) // loop for finding the minimum point
{
if(a[i]<a[i+2])
{ c = i; // associated minimum valued index to c
for( ; i<n-2; i++) /* loop for checking whether after that the array
{ is decreasing or not*/
if(a[i+1]<a[i+2])
{
count = count+1;
}
else
{
}
}
}
if(count == n-2-c)
{
System.out.println("YES");
}
else
{
System.out.println("NO");
}
}
}
This code is not passing 1 Test Case on Hackerrank.com please suggest some solution.
One good way to do that is by binary search:
You will have three variables : lowbound,middle,upperbound and you start from the middle of your array and lowbounf=0,upperbound =n-1.
Next you will check with a linear passing of the array if s1,s2,...smiddle are strictly decreasing and smiddle,....,sn are strictly increasing .If yes then middle is your solution.
If s1,s2,...smiddle is not strictly decrasing and smiddle,....,sn is not strictly increasing you have no solution.
If s1,s2,...smiddle is not strictly decrasing and smiddle,....,sn is strictly increasing then uperbound=middle,middle=(upperbound+lowbound)/2 and try again.
If s1,s2,...smiddle is strictly decrasing and smiddle,....,sn is not strictly increasing then lowbound=middle,middle=(upperbound+lowbound)/2 and try again.
This until you find a solution ,or find that there is no solution or until lowbound=upperbound.
Example:
sequence: 7 8 5 1 2 3 4 5 6 7 8 middle=5 (the element 3),lowbound=0,upperbound=10, 7,8,5,4,1,2,3 is not strictly decreasing ,while 4,5,6,7,8 strictly increasing.
so: upperbound=5,middle=2 (the element array[middle]=2),7,8,5 are strictly decreasing ,1,2,3,4,5,6,7,8 are stricty increasing so the solution is middle = 2 .(Note middle=2 means that is the third element of array, the first is array[0] ,second is array[1] and third is array[2]=array[middle]=5 ).
The above solution is trying log n times (due to binary search) to linearly check the array (every linear check is O(n)) .So this solution is O(n log n).