/*Problem description Given a collection of number and sums, determine whether there is a pair of numbers that sums up to the given sum Print out "True" or "False" as the result */ #include #include #include using namespace std; int main() { /*Test file name: in.txt Test file explain: n m i1 i2 i3 ... in j1 j2 j3 ... jm Where: n : number of numbers in the array m : number of "sum" we need to find ik (1 <= k <= n): elements in the array jk'(1 <= k'<= m): the sums we need to find Sample: 7 9 2 3 4 5 7 8 20 10 19 100 5 9 10 9 22 29 */ //Read from file ifstream inFile("in.txt"); int numOfItem = 0, findVal = 0, numToFind = 0; inFile >> numOfItem >> numToFind; //Read in important values vector value(numOfItem); //Create a container based on given size //Read in array values for (int indx = 0; indx < numOfItem; indx++) { inFile >> value[indx]; } for (int indx = 0; indx < numToFind; indx++) { inFile >> findVal; bool found = false; for (unsigned int lowIndx = 0, highIndx = value.size() - 1; lowIndx < highIndx;) { int curVal = value[lowIndx] + value[highIndx]; if (curVal == findVal) { //Found :D found = true; break; } if (curVal > findVal) { //Too big highIndx--; } else { //Too small lowIndx++; } } //Output appropriately cout << (found == true ? "True" : "False") << endl; } return 0; }