I've been trying to make a simple function which checks if an array is the same as another array reversed.

For instance, comparing [0, 1, 2] and [2, 1, 0] would return true, but comparing [0, 1, 2] and [2, 1, 1] would return false.

I am also trying to use the divide and conquer method, using function recursively.

This is what I have coded, but it doesn't work as intended, returning false when it should return true:

public class ReverseCheck {

    // Check if an array is the reverse of another array
    // Use divide and conquer
    public static boolean isReverse(int[] a, int[] b) {
        if (a.length != b.length) {
            return false;
        }
        return isReverse(a, b, 0, a.length - 1);
    }

    private static boolean isReverse(int[] a, int[] b, int start, int end) {
        if (start == end) {
            return a[start] == b[end];
        }
        int mid = (start   end) / 2;
        return isReverse(a, b, start, mid) && isReverse(a, b, mid   1, end);
    }

    public static void main (String[] args) {
        int[] a = {1, 2, 3, 4, 5, 6};
        int[] b = {6, 5, 4, 3, 2, 1};
        int[] c = {1, 2, 3, 4, 5, 6, 7};
        int[] d = {6, 5, 5, 3, 2, 1};
        System.out.println(isReverse(a, b)); // Should return true, returns false
        System.out.println(isReverse(a, c)); // Should return false, returns false
        System.out.println(isReverse(a, d)); // Should return false, returns false
    }

}

CodePudding user response：

There's a couple of issues in your solution:

• Termination condition isn't sufficient. If values at the current indices aren't equal, there's no need for subsequent recursive calls. The method should return false. I.e. the base case is incorrect.
• The next issue derives from the previous. You are checking only the actual values only when condition start == end evaluated to true. Let's consider these two array a = [1, 2, 3] and b = [3, 2, 1]. We have to check whether a[0] == b[2], a[1] == b[1] and a[2] == b[0]. As you can see the indices will be equal only ones. And arrays will be of even length, there will no case when indices are equal at all.
• For this problem, we have to check all pairs of values. The divide and conquer approach is fruitless here because we can't reduce the amount of operations, in the worst case every pair of values needs to be compared.

I suggest addressing this problem with backtracking by simply moving the indices of both arrays, without utilizing the divide and conquer because we can't benefit from it.

First, let's fix the base case of recursion.

As I've said, recursion should terminate if values that correspond to the current indices are not equal, i.e.:

if (a[start] != b[end]) return false;

And your initial condition might be changed to:

if (start == a.length - 1) return a[start] == b[end];

or

if (start == a.length - 1) return true;

The meaning of both is almost the same - we've managed to compare all the pair of values (or the last pair is being compared). The first version is slightly better, it'll spare one method call.

In the recursive case, we are simply calling the method by passing the start incremented by 1 and the end decremented by 1.

private static boolean isReverse(int[] a, int[] b, int start, int end) {
    if (start == a.length - 1) {
        return a[start] == b[end];
    }
    if (a[start] != b[end]) {
        return false;
    }

    return isReverse(a, b, start   1, end - 1);
}

main()

public static void main(String[] args) {
    int[] a = {1, 2, 3, 4, 5, 6};
    int[] b = {6, 5, 4, 3, 2, 1};
    int[] c = {1, 2, 3, 4, 5, 6, 7};
    int[] d = {6, 5, 5, 3, 2, 1};
    System.out.println(isReverse(a, b)); // Should return true, returns false
    System.out.println(isReverse(a, c)); // Should return false, returns false
    System.out.println(isReverse(a, d)); // Should return false, returns false
}

Output

true
false
false

Update

Seems like I'manage to get your divide and conquer version working.

As I've said, the problem resides in the base case. Instead of comparing elements like that a[start] == b[end] (when start equals to end it will not make sense), we need to adjust the end index:

    if (start == end) {
        return a[start] == b[(b.length - 1) - end];
    }

That's the only change you need to make.