0

I am trying to solve a tricky problem involving a sorted array. Say I have an array of sorted integers (8, 6, 4, 1) and given the value x I need to check the array to see if any two numbers add up to x. This needs to be done in linear time. So far I have come up with this:

#include <iostream>

using namespace std;

bool sum(int arr[], int n, int k)
{
	int temp1(0), temp2(0);

	while (arr[temp1] + arr[temp1 + 1] <= k);
	{
		if (arr[temp1] + arr[temp1 + 1] == k)
		{
			return true;
		}
		
		if (arr[temp1] + arr[temp1 + 1] < k)
		{
			temp1 += 1;
		}
	}

	temp2 = temp1 + 1;

	for (temp1; temp1 > 0; --temp1)
	{
		if (arr[temp1] + arr[temp1] == k)
		{
			return true;
		}
	}

	return false;
}

int main()
{
	int list[4] = {8, 6, 4, 1};

	bool result = true;
	result = sum2(list, 4, 10);

	cout << result << endl;

	return 0;
}

It does not work and I am entirely at loss as to how I may go about getting this problem to work. I know how to do it in quadratic time using two loops, but doing it in linear time is getting to be frustratingly difficult.

1
Contributor
1
Reply
2
Views
9 Years
Discussion Span
Last Post by meddlepal
0

Went back to the drawing board and wrote an entirely new algorithm and solved it.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.