CODEWITHSUNDEEP
javaarraysoptimizationrecursion
B Cronyn
B Cronyn

Reputation: 847

How to check that all values are equal in array using recursion?

I am trying to solve this algorithm recursively; I want to check that all values in the array are the same (or equal to each other). If all values are equal, return true, if they are not, return false. My code is not passing any tests.

public boolean allEqual(int[] a, int start, int end){
    if (start > end) return false;
    if (a.length==0) return false;
    if (start==end && a[start] == a[end]) return true;
    if (a[start] != a[end]){
        return false;
    }
    return allEqual(a, start++, end);
}

Upvotes: 3

Views: 5023

Answers (3)

Anindya Dutta
Anindya Dutta

Reputation: 1982

You can solve it using the classic divide and conquer method. Divide the array into halves until there are two elements, and then check if those are equal. Then conquer them and compare the values. Something like this:

class Ideone {

    static boolean checkEquals(int a[], int start, int length) {

        if (length==2)
            return a[start]==a[start+1] && a[start]==a[0];
        else
            return checkEquals(a,start+0,length/2) &&
                   checkEquals(a,start+length/2,length/2);     
    }

    public static void main (String[] args) {
        int a[]={1,1,1,1,1,1,1,1};
        System.out.println(checkEquals(a,0,8));
    }
}

Executed here.

Upvotes: 1

Matthew Wright
Matthew Wright

Reputation: 1525

It may be the easiest to simply take the first value of the array and go through until a single value is not the same.

public void allEqual(int[] arr) {
    if(arr.length==0) return false;
    for(int i=0; i<arr.length; i++)
        if(arr[0]!=arr[i]) return false;
    return true;
}

Edit: Realized this answer is for doing it with recursion and my answer doesn't do that.

Upvotes: 2

Eran
Eran

Reputation: 393846

change

return allEqual(a, start++, end);

to

return allEqual(a, start+1, end);

start++ passes the original value of start to the recursive call (that's what post increment operator returns), so your recursion will never end and you are probably getting a StackOverflowError.

Upvotes: 8

Related Questions