//this program creats a array and fills it with random integers
// then as the user inputs it searches the array for any two numbers that will sum to the input number
// limits of the program the highest random integer this program will produce is 2^16-1 or 65535 because that is the maximum space for a int variable
//wanted to extend this to double values but caused other errors i didn't want to deal with
#include <iostream>
#include <cstdlib>
using namespace std;
void prepareArray(int intArray[], int size);
bool findPair(int intArray[], int size,int targetNum, int &firstNum, int& secondNum); //is considerably slow after array is larger than 10000
bool SortFindPair(int sortedArray[], int size, int targetNum, int& first, int& second);
void findUnSummedSorted(int sortedArray[], int size);
void findUnSummed(int intArray[],int size);
int compare (const void * a, const void * b);
int main()
{
// initialize
const int SIZE = 10000;
int intArray[SIZE];
int sortedArray[SIZE];
int targetNumber = 0, numberOne = 0, numberTwo = 0;
char goAgain = 'y';
// fills the array
prepareArray(intArray,SIZE);
//copys and sorts the array
for(int i = 0; i < SIZE; i++)
sortedArray[i] = intArray[i];
qsort(sortedArray,SIZE,sizeof(int),compare);
while(goAgain == 'y')
{
// asks user for a number to search
cout << "What number would you like to find the sum to?" << endl;
cin >> targetNumber;
// searches for the pair and displays results
cout << "sorted" << endl;
if(SortFindPair(sortedArray,SIZE,targetNumber,numberOne,numberTwo))
cout << "Two numbers that sum to " << targetNumber << " are " << numberOne << " and " << numberTwo << "." << endl << endl;
else
cout << "Sorry but no numbers could be summed to equal " << targetNumber << endl << endl;
cout << "unsorted" << endl;
if(findPair(intArray,SIZE,targetNumber,numberOne,numberTwo))
cout << "Two numbers that sum to " << targetNumber << " are " << numberOne << " and " << numberTwo << "." << endl << endl;
else
cout << "Sorry but no numbers could be summed to equal " << targetNumber << endl << endl;
cout << "Would you like to try again?" << endl;
cin >> goAgain;
//findUnSummedSorted(sortedArray,SIZE);
//findUnSummed(intArray,SIZE); //warning this line extremely slow for SIZE values greater than 10,000
}
return(0);
}
// fills the array with random numbers
void prepareArray(int intArray[], int size)
{
for(int i = 0; i < size; i++)
if((size - i)%(i+1)==0)
intArray[i] = rand()*rand()*rand()%size;
else
intArray[i] = (rand()+rand())%size;
for(int i = 0; i < size; i++) //prevents negetive values in the array
if( intArray[i] < 0)
intArray[i] = intArray[i]*-1;
}
// searches and array of numbers and returns true and a pair of numbers whose sum is equal to the target number, or false
// if no pair of numbers exist
// this will work for any array sorted or not but takes a while for large numbers
bool findPair(int intArray[], int size,int targetNum, int& firstNum, int& secondNum)
{
// check that it's actually possible to sum to the target
if(targetNum > size*2-2 || targetNum < 0)
return(false);
// loops through all the numbers between the first and size-1
for( int first = 0; first < size - 1; first++)
{
if(intArray[first] <= targetNum) // makes sure that we arent summing numbers greater than the target number
{
// loops through all the numbers between the first and size
for(int second = first+1; second < size; second++)
{
if(intArray[second] <= targetNum) //makes sure that we aren't summing numbers greater than the target num
{
// checks to see if the sum of the first and second numbers equal the target number
if(intArray[first]+intArray[second]==targetNum)
{
// if so sets the value of firstNum and secondNum respectively and returns true
firstNum = intArray[first];
secondNum= intArray[second];
return(true);
}
}
}
// else goes to the next number
}
}
// since no pair is found return false
return(false);
}
void findUnSummed(int intArray[],int size)
{// just for fun goes through the array and finds all the numbers that can be summed by the numbers in the array
int one=0,two=0; // filling in space for the findPair function
bool result = false;
int totalUnSummable = 0;
for(int i = 0; i < size*2 - 1; i++)
{
result =findPair(intArray,size,i,one,two);
if(!result)
{
cout << i << "\t";
totalUnSummable++;
}
}
cout << "Total number that cant be summed to is " << totalUnSummable << endl;
}
void findUnSummedSorted(int sortedArray[], int size)
{// just for fun goes through the array and finds all the numbers that can be summed by the numbers in the array
int one=0,two=0; // filling in space for the findPair function
bool result = false;
int totalUnSummable = 0;
for(int i = 0; i < size*2 - 1; i++)
{
result =SortFindPair(sortedArray,size,i,one,two);
if(!result)
{
cout << i << "\t";
totalUnSummable++;
}
}
cout << "Total number that cant be summed to is " << totalUnSummable << endl;
}
int compare (const void * a, const void * b)
{
return ( *(int*)a - *(int*)b );
}
// only works for sorted arrays
bool SortFindPair(int intArray[], int size, int targetNum, int& first, int& second)
{
int halfwayIndex = 0, upperBoundIndex = 0,index = 0;
//find halfway
index= targetNum/2;
// starting at the index at half of target number
if(intArray[index] > targetNum/2)
while(intArray[index] > targetNum/2 && index >= 0)
index--;
if(intArray[index] == targetNum/2)
while(intArray[index-1] == targetNum/2)
index--;//finds first occurence of target/2
else if (intArray[index] < targetNum/2)
while(intArray[index] < targetNum/2)
index++;
halfwayIndex = index;
// if the key is equal to half the target value great
// else if the key is less than half the target increment the index until a key is found that is greater than half
// set halfway to that index -1
//find upperBound
// if the target number is greater than or equal to the size of the array set the upperbound to the size of the array
if(targetNum >= size)
upperBoundIndex = size-1;
else
for(int i = targetNum; i < size; i ++)
{
// else if the key at index targetnum is less than the value of targetNum increment the index until one is found with
// a value greater than the target number
// set the value of upperbound to the value of the index - 1
if(intArray[i] > targetNum)
{
upperBoundIndex = i;
break;
}
upperBoundIndex = i;
}
//starting at the last value of the first half of the searchable array check the sum of every value in the second half of
// the searchable array for equivalance with the target number starting with the first value in the second half of the array
for(int firstHalfIndex = halfwayIndex; firstHalfIndex >= 0; firstHalfIndex --)
{
for(int secondHalfIndex = halfwayIndex+1; secondHalfIndex <= upperBoundIndex; secondHalfIndex++)
{
if(intArray[firstHalfIndex] + intArray[secondHalfIndex] == targetNum)
{
first = intArray[firstHalfIndex];
second = intArray[secondHalfIndex];
return (true);
}
}
}
return(false);
}