CODEWITHSUNDEEP
java
user9179677
user9179677

Reputation: 87

Searching Algorithm (better than linear)

I have to write a method which returns true if three 3s are present in an integer array(provided they are not consecutive). I have written this code here: However, it is returning true (which it should not do). Can someone point out my mistake? arr[]={{4,3,5,2,3,3};

Also, this is a linear algorithm. Can it be done better?

public static boolean consecutiveThree(int[] arr) {
        int x=0;
        for(int i=0;i<arr.length-1;i++) {

            if((arr[i]!=3 && arr[i+1]==3) || (arr[i]==3 && arr[i+1]!=3)) {
                x++;
                //continue;

            }

            if(x==3)
                return true;

        }
        return false;
    }

Upvotes: 0

Views: 86

Answers (3)

anoopknr
anoopknr

Reputation: 3355

Your algorithm is not checking the whether arr[i-1] is '3'. That is your algorithm's mistake.

Try this:-

public static boolean consecutiveThree(int[] arr) {
    int x = 0;
    for (int i = 0; i < arr.length; i++) {

        if (arr[i] == 3) {
            if (i == 0) { // zero 'th element do not have arr[i-1].
               if(arr[i + 1] != 3) {
                x++;
               }
            } else if (i == arr.length - 1) { // last element do not have arr[i+1].
               if((arr[i - 1] != 3)) {
                x++;
               }
            } else if ((arr[i + 1] != 3) && (arr[i - 1] != 3)) {
                x++;
            }
        }

        if (x == 3) // may be x >= 3
            return true;

    }
    return false;
}

Upvotes: 0

Andreas
Andreas

Reputation: 159096

You said:

returns true if three 3s are present in an integer array(provided they are not consecutive)

I interpret that as having at least three 3s, and no two 3s are adjacent.

public static boolean hasThreeNonconsecutiveThrees(int... values) {
    int count = 0, streak = 0;
    for (int value : values) {
        if (value != 3)
            streak = 0;
        else if (++streak == 2)
            return false; // Found two consecutive (adjacent) 3s
        else
            count++;
    }
    return (count >= 3);
}

Test

    System.out.println(hasThreeNonconsecutiveThrees(4,3,5,2,3,3)); // false
    System.out.println(hasThreeNonconsecutiveThrees(4,3,5,3,2,3)); // true
    System.out.println(hasThreeNonconsecutiveThrees(1,2,3,4,3));   // false
    System.out.println(hasThreeNonconsecutiveThrees(4,3,5,3,3,3)); // false

Output

false
true
false
false

Upvotes: 1

Karol Dowbecki
Karol Dowbecki

Reputation: 44952

At worst case the correct array will end with ... 3 3 X 3. Unless the array is somewhat sorted or somewhat special you will have to look at every single element to reach the last three 3s. If the array is random, you need linear complexity since you have to review every single element in the array.

Upvotes: 1

Related Questions