nichoc
BAN USERSorry the idea is to compare the results. And turn the loop into an expression to validate if they match.
To illustrate, I could come up with the Formula Eg.
m-1
Σ (l-2)*(n-i-2) - (n^2/2 - n/2 - i^2/2 + i/2)
i=0
But how do you validate that ?
I did not simplify but this is the idea...
In C++
// ConsoleApplication3.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <algorithm>
using namespace std;
double Sum(int k, int l, int m)
{
double total = 0;
int x= min(l-1, m-1);
int y = min(x, k);
total = (y) * m * x - m*(y*(y-1))/2 - (y) * ((x+1)*(x+2)) / 2 + y * (( y * (y +1))/2) - ( ((y+1)* y * (2*y +1))/6 - (y*(y+1))/2);
return total;
}
int _tmain(int argc, _TCHAR* argv[])
{
int k = 1;
int l = 2;
int m = 3;
int sum = 0;
for(int i=0; i< k; i++)
for(int j= i+1; j< l; j++)
for(int z=j+1; z < m; z++)
sum++;
cout << sum << endl;
cout << Sum(k,l,m)<< endl;
getchar();
return 0;
}
Outputs
10
10
I suppose the recursive solution will make it easier to address the scenario where the pivot, low and high are the same and we need both sides of the array.
#include <iostream>
#include <vector>
using namespace std;
template <typename T>
int rotated_binary_search(const T &arr, int low, int high, int key) {
while (low <= high) {
// arrvoid overflow, same as mid=(low+high)/2
int mid = low + ((high - low) / 2);
if (arr[mid] == key) return mid;
// the bottom half is sorted
if (arr[low] < arr[mid]) {
if( key < arr[mid] )
return rotated_binary_search(arr, low, mid - 1, key);
else
return rotated_binary_search(arr, mid + 1, high, key);
}
else if( arr[mid] < arr[high] ) { // the upper half is sorted
if( key <= arr[high] )
return rotated_binary_search(arr, mid + 1, high, key);
else
return rotated_binary_search(arr, low, mid - 1, key);
}
else if ( arr[low] == arr[mid] )
{
if( arr[mid] == arr[high] ) // Can't tell which side to go - have to look at both.
{
int ret = rotated_binary_search(arr, low, mid - 1, key);
if ( ret == -1 )
return rotated_binary_search(arr, mid + 1, high, key);
else
return ret;
}
else
return rotated_binary_search(arr, mid + 1, high, key);
}
}
return -1;
}
int main() {
const int TESTS = 7;
int a[TESTS][9] = {{ 1, 3, 4, 5, 1, 1, 1, 1, 1},
{ 7, 8, 9, 1, 2, 3, 4, 5, 6},
{ 5, 6, 7, 8, 9, 10, 1, 1, 1},
{ 1, 3, 4, 5, 6, 7, 8, 9, 10},
{ 1, 1, 1, 1, 1, 5, 8, 9, 10},
{ 1, 1, 1, 5, 8, 8, 8, 8, 8},
{ 1, 3, 4, 4, 5, 6, 7, 1, 1}};
int iFound = -1;
for(int i = 0; i < TESTS; i++ )
{
iFound = rotated_binary_search(&a[i][0], 0, sizeof(a[i])/sizeof(int)-1, 5);
cout << iFound << endl;
}
return 0;
}
Output:
3
7
0
3
5
3
4
Something off in the result:
- nichoc January 08, 2014Take for instance:
m, n, l
4, 4, 5
Correct Output = 10
Your output = 14