Answer for this algorithm
-
Imagine you have a array of integers, and you want to get any two numbers whose sum is 51, what you'll do? Using both O(n^2) and O(n).:^)
-
Imagine you have a array of integers, and you want to get any two numbers whose sum is 51, what you'll do? Using both O(n^2) and O(n).:^)
I do brutal
for (i=0 ; i < iMax-1; i++)
{
int temp = a[i];
if (temp > 51) continue;for ( j=i+1; j < iMax; j++)
{
if (temp + a[j] == 51)
{
// do whatever you need...
}
}
}:)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
-
I do brutal
for (i=0 ; i < iMax-1; i++)
{
int temp = a[i];
if (temp > 51) continue;for ( j=i+1; j < iMax; j++)
{
if (temp + a[j] == 51)
{
// do whatever you need...
}
}
}:)
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler. -- Alfonso the Wise, 13th Century King of Castile.
-
Imagine you have a array of integers, and you want to get any two numbers whose sum is 51, what you'll do? Using both O(n^2) and O(n).:^)
LongHC wrote:
Imagine you have a array of integers, and you want to get any two numbers whose sum is 51, what you'll do?
First, determine how to break the number down into two numbers whose sum is the original number. Instead of 51, let's pick a smaller number, say 11. Here are the numbers whose sum is 11: 11 + 0 = 11 10 + 1 = 11 9 + 2 = 11 8 + 3 = 11 7 + 4 = 11 6 + 5 = 11 To find these numbers, we can start with two values: the original number and zero, call these x and y. Run a loop in which 1 is subtracted from x and 1 is added to y at each iteration. Continue the loop until x is less than y:
int x = 11;
int y = 0;while(x > y)
{
x--;
y++;
}Now, we need to search for these values in our array. It would be helpful to have our array sorted first. Then at each iteration through the loop, we perform a binary search for x an y and store the indexes to the numbers in a list, if they are in the array. We'll assume that the binary search returns -1 if the number isn't in the array:
Sort(array);
List list;
int x = 11;
int y = 0;while(x > y)
{
int index = BinarySearch(array, x);if(index >= 0) { list.Add(index); } index = BinarySearch(array, y); if(index >= 0) { list.Add(index); } x--; y++;}
Note: this algorithm is off the top of my head. There may be better ways of doing this. [EDIT] My algorithm doesn't take into account possible duplicates in the array. :doh: [/EDIT] -- modified at 10:54 Friday 13th April, 2007
-
Imagine you have a array of integers, and you want to get any two numbers whose sum is 51, what you'll do? Using both O(n^2) and O(n).:^)
If the integers are positive, then I can think of an O(n) solution. As this sounds like homework I will just give a hint - try using an array of 51 integers. If the integers are unbounded then I can't see an O(n) solution.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
If the integers are positive, then I can think of an O(n) solution. As this sounds like homework I will just give a hint - try using an array of 51 integers. If the integers are unbounded then I can't see an O(n) solution.
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
cp9876 wrote:
If the integers are positive, then I can think of an O(n) solution.
They are +ve numbers.
cp9876 wrote:
As this sounds like homework
In fact this is not, I just came by this problem while reading and I tried so much in it and didn't get to any thing.
-
cp9876 wrote:
If the integers are positive, then I can think of an O(n) solution.
They are +ve numbers.
cp9876 wrote:
As this sounds like homework
In fact this is not, I just came by this problem while reading and I tried so much in it and didn't get to any thing.
In that case, start with an array of 51 numbers c[i] initialised to -1.
for (int i = 0 ; i < 51 ; i++)
{
if (a[i] < 51)
{
int n = 51 - a[i];
if (c[n] >= 0)
{
// found one, at a[i], a[c[n]]
}
else
{
c[n] = i;
}
}
}Basically, for each element, store its location where its complement can find it
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
-
In that case, start with an array of 51 numbers c[i] initialised to -1.
for (int i = 0 ; i < 51 ; i++)
{
if (a[i] < 51)
{
int n = 51 - a[i];
if (c[n] >= 0)
{
// found one, at a[i], a[c[n]]
}
else
{
c[n] = i;
}
}
}Basically, for each element, store its location where its complement can find it
Peter "Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."