////////////////////////////////////////////////////////////////// //////**************CHALLENGE:Find the pair //////****************Author: Petros Simidyan****** ////***************** #include struct HelpFlags { bool isThere = false; bool notSame = false; }; bool findPair(const int* arr, const int& len, const int& input); int main() { //testing 3 common cases int arr[] = { 1,2,3,5,6,7,8 }, arr1[] = { 2,2,3,5,6,7,8 }, arr2[] = { 8,2,3,5,6,7,8 }; std::cout << findPair(arr, 7, 4) << std::endl;//should be 1 std::cout << findPair(arr1, 7, 4) << std::endl;//should be 1 std::cout << findPair(arr2, 7, 4) << std::endl;//should be 0 (only 1 entry = 2 in arr2) return 0; } bool findPair(const int* arr, const int& len, const int& input) { HelpFlags* flagsArr = new HelpFlags[input + 1]; int x = -1; for (int i = 0; i < len; i++) { x = arr[i]; if (x <= input) { //the function sets flagsArr{x].isThere and notSame true //if there is a multiply entry equal to x in input array //if there is only one entry = x, the function sets only isThere = true if (flagsArr[x].isThere && !flagsArr[x].notSame) flagsArr[x].notSame = true; else flagsArr[x].isThere = true; } } for (int i = 0; i < len; i++) { x = arr[i]; //now the function tests, is there a entry with index (input-x) //in flagsArr. In that case the function returns true because the input //array has 2 entrys: x and input-x so that the sum of this 2 entrys is input if (x <= input &&flagsArr[input - x].isThere) //for example arr={2,3,4}, input = 4 //function returns true, because 2+2 =4 //but there is only 1 entry=2 //to avoid this problem we need the //flag notSame and this little test if (x != input - x) return true; else if (flagsArr[input - x].notSame) return true; } delete[] flagsArr; return false; }