/* Recursion-Ex14.cpp - check two arrays for similar elements */
#include <iostream>
using namespace std;
 
bool haveSameElems(int Arr1[], int Arr2[], int size);
 
const int SIZE = 5;
 
int main () {
        int Arr1[SIZE] = {2, 5, 6, 2, 1};
        int Arr2[SIZE] = {1, 2, 6, 5, 2};
 
        cout << (haveSameElems(Arr1, Arr2, SIZE*2) ? "yey" : "ney");
       
    return 0;
} /* Output: yey */
 
/* assume both arrays are the same size, otherwise if one is bigger then always false */
bool haveSameElems(int Arr1[], int Arr2[], int size) {
        int i, j, len = size/2-1; // get the size psyical of each array
        bool boom = false;
       
        if (size == 0)
                return true; // two empty sets have the same elements
        else {
                i = 0;
                while (!boom && i <= len) {
                        if (Arr1[len] == Arr2[i]) { // If we find two equal elements
                                for (j = i; j <= len; j++) // 'pop' that element from Arr2
                                        Arr2[j] = Arr2[j+1];
                                len--; // pop it from Arr1 by truncing the length
                                boom = true; // stop looking
                        }
                        i++;
                }
                // If we found two euqal elements, keep looking for more, otherwise stop right now.
                return (boom ? haveSameElems(Arr1, Arr2, (len+1)*2) : false); // send the logical size of both arrats
        }
}