2

I can't pass the final hidden test.Could you tell me what I miss?Thanks in advance.

Here are the statements: 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.

boolean almostIncreasingSequence(int[] sequence) 
{
    boolean increase = true;
    List<Integer> list = new ArrayList<>();
    for (int a :sequence ) 
    {
        list.add(a); 
    }
    System.out.println(list);
    if(list.size()==1)
    {
        return false;
    }
    for (int i = 0;i < list.size()-1 ;i++ ) 
    {
        if (list.get(1)<=list.get(0)) 
        {
            list.remove(0);
            break;    
        }
        if(list.get(i+1)<=list.get(i)) 
        {
            if (list.get(i+1)>list.get(i-1)) 
            {
                list.remove(i); 
            }
            else
            {
                list.remove(i+1);
            }
            break;
        } 
    }

    for (int i =0;i<list.size()-1 ;i++ ) 
    {
        if (list.get(i+1)<list.get(i) || list.get(i+1)==list.get(i) ) 
        {
            increase = false;
        }    
    }
    return increase;
}

8 Answers 8

6

This is the linear solution I came up with. It involves muting the array so you don't have to loop through the array again.

boolean almostIncreasingSequence(int[] sequence) {
    int removed = 0;

    for (int i = 0; i < sequence.length - 2 && removed <= 2; i ++) {
        int a = sequence[i];
        int b = sequence[i+1];
        int c = sequence[i+2];

        if (a >= b) {
            removed++;
            sequence[i] = b -1;
        } 

        if (b >= c){
            removed++;

            if (a == c) {
                sequence[i+2] = b +1;
            } else {
                sequence[i+1] = a;
            }
        }
    }

    return removed <= 1;
}
5

Here's my solution with O(n) complexity `

boolean almostIncreasingSequence(int[] sequence) {
    int flag = 0;
    int i = 0;
    while(i<sequence.length-1){
        if(sequence[i] < sequence[i+1]){
            i = i+1;
            continue;
        } else {
            flag = flag + 1;
            if(i>0 && i+2 < sequence.length && sequence[i+1] <= sequence[i-1] && sequence[i+2] <= sequence[i]){
                flag = flag + 1;
            } else {
                i = i+1;
            }
            if(flag > 1){
                return false;
            }
        }
    }
    return true;
}

`

3

This worked for me

boolean almostIncreasingSequence(int[] sequence) {
    int failed = 0;
    boolean one_chance;    
        for(int i = 0; i < sequence.length - 1; i++){
            int curr=i,next=i+1;
            if(sequence[curr] >= sequence[next]) {                
                failed++;                                    
                    if( curr > 0 && next < sequence.length - 1 ){
                        // Problem is not on head neither tail
                        // So check if removing one of 2 problematic numbers solves the issue
                        one_chance = false;
                        if( sequence[curr - 1] < sequence[next] )
                            one_chance = true ;                         
                        if ( sequence[curr] < sequence[next+1] )
                            one_chance = true ;
                        if( one_chance == false ) return false;
                    }

            }
            if( failed > 1 ) return false;            
        }
    return true;        
}
2

Spoiler Alert!

I could not pass the last hidden test either. So I spent 10,000 of my 12,300 coins (ouch!) to unlock them.

It turns out, the last test (#34) is expecting an outcome of true, and is passing an array of ints 100,000 long, in order from 1 to 100000! (So big that the only way I could see this was to do this in my code:

System.out.printf("length: %d%nlastValue:%d%n",
        sequence.length, sequence[sequence.length - 1]);

I'm not sure why my code didn't pass, but I did at least unlock that hidden test, so now you can know what it is without having to spend coins to unlock it yourself.

I then got lazy and added this line at the top of my method to make it pass:

if (sequence.length == 100000
        && sequence[sequence.length - 1] == 100000) {
    return true;
}
1
  • 1
    Um, whoever downvoted... it would be nice if you would explain why.
    – James Dunn
    Commented Jun 11, 2018 at 22:51
1

Here is a solution that works by using recursion to check the remainder of the array.

The issue is when the code hits a number that doesn't belong it can't be sure which of the two numbers is the offender so I just check the array starting from where the problem was detected and skipping the "bad" numbers. If it fails again while skipping a number it's game over.

This is in JavaScript, but it can easily be translated.

function almostIncreasingSequence(sequence) {
    if(!sequence || sequence.length < 3) return true;

    return checkSorted(sequence);
}

function checkSorted(arr, start = 0, skip) {

    let last = arr[start === skip ? skip + 1 : start];

    for(let i = start + 1; i < arr.length; i++) {

        if(skip === i) continue;
        let current = arr[i];
        let lastIndex = skip === i - 1 ? i - 2 : i - 1;
        let last = arr[lastIndex];

        if(current <= last) {
            if(skip !== undefined) return false;
            return checkSorted(arr, i - 1, i) || checkSorted(arr, i - 1, i - 1);
        }
    }
    return true;
}
1
def almostIncreasingSequence(sequence):
initial_length = len(sequence)-1
length = len(sequence)-1
count = 0
i = 0
while i < length:
    if sequence[i] >= sequence[i+1]:
        if i == 0:
            sequence.pop(0)
            count +=1
            length = len(sequence)-1
            i =0
        elif sequence[i] == sequence[i+1]:
            sequence.pop(i+1)
            length = len(sequence)-1
            i -= 1
            count += 1
        elif sequence[i] > sequence[i+1]:
            if count ==0 and i + 1 == length:
                return True
            else:
                if max(sequence) == sequence[i] and count == 0:
                    sequence.pop(i)
                    length = len(sequence)-1
                    i -= 1
                    count += 1                        
                else:    
                    sequence.pop(i+1)
                    length = len(sequence)-1
                    i -= 1
                    count +=1
    else:
        i += 1
length = len(sequence)-1
if count == 1:
    if initial_length - length == 1:
        return True
    else:
        return False
elif count > 1:
    if initial_length - length > 1:
        return False
else:
    return True
1
  • Could you please add some explanation to your solution? Thank you.
    – slfan
    Commented Dec 21, 2019 at 17:31
1
boolean almostIncreasingSequence(int[] sequence) {
        int count = 0;
        int size = sequence.length;
        if(size==1)
        return true;
        for(int i=0;i<size-1 && count<=1;i++){
           if(sequence[i]>=sequence[i+1]) {
               count++;
               if(i>0 && (i+2)<size && sequence[i-1]>=sequence[i+1] && sequence[i]>=sequence[i+2]) {
                   count++;
               }
           }
        }
        return (count<=1);
    
}
0
    boolean solution(int[] sequence) {
    boolean increasing = true;
    boolean isany = false;
    
    for(int i=0;i<sequence.length;i++){
        ArrayList<Integer> sequenceArrayList = new ArrayList();
        for(int a : sequence){
            sequenceArrayList.add(a);
        }

        sequenceArrayList.remove(i);
        for(int j=0;j<sequence.length-2;j++){
            if(sequenceArrayList.get(j)>=sequenceArrayList.get(j+1)){
                increasing = false;
                break;
            }else{
                increasing = true;
            }
        }
        if(increasing){
            isany = true;
        }
    }
    return isany;
}

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.