Question

java

Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array. Here are the constraints. 1. You must use only arrays. 2. You are not allowed to make copies of the array (use only the one that is passed). 3. Your algorithm running time must be at most O(n 2 ). i.e. You can have only one loop within another. Ideally, you should be able to find a linear running time algorithm. i.e. you can even solve this problem using a single loop. Note: Sequence a0, a1, . . . an is considered to be a strictly increasing if a0 < a1 < . . . < an. Sequence containing only one element is also considered to be strictly increasing. Assuming your method is almostIncreasingSequence, following main method could be used to test your code.

public static void main(String[] args) { int[] a1 = {1, 3, 2, 1}; // false int[] a2 = {1, 3, 2}; // true int[] a3 = {1, 2, 1, 2}; // false int[] a4 = {3, 6, 5, 8, 10, 20, 15}; // false int[] a5 = {1, 1, 2, 3, 4, 4}; // false int[] a6 = {1, 4, 10, 4, 2}; // false int[] a7 = {10, 1, 2, 3, 4, 5}; // true int[] a8 = {1, 1, 1, 2, 3}; // false int[] a9 = {0, -2, 5, 6}; // true int[] a10 = {1, 2, 3, 4, 5, 3, 5, 6}; // false int[] a11 = {40, 50, 60, 10, 20, 30}; // false int[] a12 = {1, 1}; // true int[] a13 = {1, 2, 5, 3, 5}; // true int[] a14 = {1, 2, 5, 5, 5}; // false int[] a15 = {10, 1, 2, 3, 4, 5, 6, 1}; // false int[] a16 = {1, 2, 3, 4, 3, 6}; // true int[] a17 = {1, 2, 3, 4, 99, 5, 6}; // true int[] a18 = {123, -17, -5, 1, 2, 3, 12, 43, 45}; // true int[] a19 = {3, 5, 67, 98, 3}; // true int[] a20 = {1, 1, 1}; // false System.out.println(Arrays.toString(a1) + ": " + (almostIncreasingSequence(a1) == false)); System.out.println(Arrays.toString(a2) + ": " + (almostIncreasingSequence(a2) == true)); System.out.println(Arrays.toString(a3) + ": " + (almostIncreasingSequence(a3) == false)); System.out.println(Arrays.toString(a4) + ": " + (almostIncreasingSequence(a4) == false)); System.out.println(Arrays.toString(a5) + ": " + (almostIncreasingSequence(a5) == false)); System.out.println(Arrays.toString(a6) + ": " + (almostIncreasingSequence(a6) == false)); System.out.println(Arrays.toString(a7) + ": " + (almostIncreasingSequence(a7) == true)); System.out.println(Arrays.toString(a8) + ": " + (almostIncreasingSequence(a8) == false)); System.out.println(Arrays.toString(a9) + ": " + (almostIncreasingSequence(a9) == true)); System.out.println(Arrays.toString(a10) + ": " + 2 (almostIncreasingSequence(a10) == false)); System.out.println(Arrays.toString(a11) + ": " + (almostIncreasingSequence(a11) == false)); System.out.println(Arrays.toString(a12) + ": " + (almostIncreasingSequence(a12) == true)); System.out.println(Arrays.toString(a13) + ": " + (almostIncreasingSequence(a13) == true)); System.out.println(Arrays.toString(a14) + ": " + (almostIncreasingSequence(a14) == false)); System.out.println(Arrays.toString(a15) + ": " + (almostIncreasingSequence(a15) == false)); System.out.println(Arrays.toString(a16) + ": " + (almostIncreasingSequence(a16) == true)); System.out.println(Arrays.toString(a17) + ": " + (almostIncreasingSequence(a17) == true)); System.out.println(Arrays.toString(a18) + ": " + (almostIncreasingSequence(a18) == true)); System.out.println(Arrays.toString(a19) + ": " + (almostIncreasingSequence(a19) == true)); System.out.println(Arrays.toString(a20) + ": " + (almostIncreasingSequence(a20) == false)); }

Output should be the following (Please carefully look at why it prints all true before asking questions). [1, 3, 2, 1]: true [1, 3, 2]: true [1, 2, 1, 2]: true [3, 6, 5, 8, 10, 20, 15]: true [1, 1, 2, 3, 4, 4]: true [1, 4, 10, 4, 2]: true [10, 1, 2, 3, 4, 5]: true [1, 1, 1, 2, 3]: true [0, -2, 5, 6]: true [1, 2, 3, 4, 5, 3, 5, 6]: true [40, 50, 60, 10, 20, 30]: true [1, 1]: true [1, 2, 5, 3, 5]: true [1, 2, 5, 5, 5]: true [10, 1, 2, 3, 4, 5, 6, 1]: true [1, 2, 3, 4, 3, 6]: true [1, 2, 3, 4, 99, 5, 6]: true [123, -17, -5, 1, 2, 3, 12, 43, 45]: true [3, 5, 67, 98, 3]: true [1, 1, 1]: true

Answer 1

Below is the code for the given problem with comments to explain the code as is.

Code passes all the given test cases

import java.util.Scanner;
import java.util.Arrays;

public class Main
{
   public static void main(String[] args) {
int[] a1 = {1, 3, 2, 1};
int[] a2 = {1, 3, 2}; // true
int[] a3 = {1, 2, 1, 2}; // false
int[] a4 = {3, 6, 5, 8, 10, 20, 15}; // false
int[] a5 = {1, 1, 2, 3, 4,4}; // false
int[] a6 = {1, 4, 10, 4, 2}; // false
int[] a7 = {10, 1, 2,3, 4, 5}; // true
int[] a8 = {1, 1, 1, 2, 3}; // false
int[] a9 = {0,-2, 5, 6}; // true
int[] a10 = {1, 2, 3, 4, 5, 3, 5, 6}; // false
int[] a11 = {40, 50, 60, 10, 20, 30}; // false
int[] a12 = {1, 1}; // true
int[] a13 = {1, 2, 5, 3, 5}; // true
int[] a14 = {1, 2, 5, 5, 5}; //
int[] a15 = {10, 1, 2, 3, 4, 5, 6, 1}; // false
int[] a16 = {1, 2,3, 4, 3, 6}; // true
int[] a17 = {1, 2, 3, 4, 99, 5, 6}; // true
int[] a18 = {123, -17, -5, 1, 2, 3, 12, 43, 45}; // true
int[] a19 = {3, 5,67, 98, 3}; // true
int[] a20 = {1, 1, 1}; // false
  
System.out.println(Arrays.toString(a1) + ": " +
(almostIncreasingSequence(a1) == false));
System.out.println(Arrays.toString(a2) + ": " +
(almostIncreasingSequence(a2) == true));
System.out.println(Arrays.toString(a3) + ": " +
(almostIncreasingSequence(a3) == false));
System.out.println(Arrays.toString(a4) + ": " +
(almostIncreasingSequence(a4) == false));
System.out.println(Arrays.toString(a5) + ": " +
(almostIncreasingSequence(a5) == false));
System.out.println(Arrays.toString(a6) + ": " +
(almostIncreasingSequence(a6) == false));
System.out.println(Arrays.toString(a7) + ": " +
(almostIncreasingSequence(a7) == true));
System.out.println(Arrays.toString(a8) + ": " +
(almostIncreasingSequence(a8) == false));
System.out.println(Arrays.toString(a9) + ": " +
(almostIncreasingSequence(a9) == true));
System.out.println(Arrays.toString(a10) + ": " +
(almostIncreasingSequence(a10) == false));
System.out.println(Arrays.toString(a11) + ": " +
(almostIncreasingSequence(a11) == false));
System.out.println(Arrays.toString(a12) + ": " +
(almostIncreasingSequence(a12) == true));
System.out.println(Arrays.toString(a13) + ": " +
(almostIncreasingSequence(a13) == true));
System.out.println(Arrays.toString(a14) + ": " +
(almostIncreasingSequence(a14) == false));
System.out.println(Arrays.toString(a15) + ": " +
(almostIncreasingSequence(a15) == false));
System.out.println(Arrays.toString(a16) + ": " +
(almostIncreasingSequence(a16) == true));
System.out.println(Arrays.toString(a17) + ": " +
(almostIncreasingSequence(a17) == true));
System.out.println(Arrays.toString(a18) + ": " +
(almostIncreasingSequence(a18) == true));
System.out.println(Arrays.toString(a19) + ": " +
(almostIncreasingSequence(a19) == true));
System.out.println(Arrays.toString(a20) + ": " +
(almostIncreasingSequence(a20) == false));
}
  
   //function to find if it is possible to obtain increasing Sequence by removing
   //an integer
   public static boolean almostIncreasingSequence(int[] array){
   int flag = 0; // flag to keep track of number of integers removed from sequence
  
   // Loop for the array
   // if flag is more than two, our codition fails
   for(int i=0; i<=array.length-3 && flag<3; i++){
   int first = array[i];
   int second = array[i+1];
   int third = array[i+2];
  
   // If first element is greater than second, it is not increasing sequence
   // so it has to be removed
   if(first>=second){
   flag++;
   array[i] = second-1;
   }
  
   // Similarly if second is greater than third, it violates the increasing
   // sequence and has to be removed
   if(second>=third){
   flag++;
   if(first==third){
   array[i+2] = second+1;
   } else {
   array[i+1] = first;
   }
   }
   }
   // If flag is more than one -> we have to remove more than one element
   // to make it increasing sequence
   return flag<=1;
   }
}