Ashwin
BAN USERHow about using the mathematical property that says, 1+2+3+...+(n-1)+n = n*(n+1)/2
1. Calculate the sum of all numbers in the array.
2. Meanwhile find out the min and max elements in the array. Call it arrSum
3. Find
a. maxSum = 1+2+3+...+(max-1)+max
b. minSum = 1+2+3+...+(min-1)
4. Check if arrSum == maxSum - minSum
5. If true, it's a sequence. If not, it's not a sequence.
Here's some working code.
#include<iostream>
#include<vector>
#define MIN -1
#define MAX 100
using namespace std;
int main()
{
int a[] = {45, 50, 47, 46, 49, 48};
vector<int> input (a, a + sizeof(a) / sizeof(int) );
vector<int>::iterator it;
int min = MAX;
int max = MIN;
int arrSum = 0;
for(it = input.begin(); it != input.end(); it++)
{
arrSum += *it;
if(*it < min)
min = *it;
else if(*it > max)
max = *it;
}
int maxSum = max*(max+1)/2;
int minSum = (min*(min+1)/2) - min;
if(maxSum - minSum == arrSum)
cout<<"Yes! They're a sequence!"<<endl;
else
cout<<"No! They're not a sequence!"<<endl;
return 0;
}
In the worst-case, if there are no negative elements in the matrix, you need to traverse all rows and all columns and thus the complexity becomes O(n^2)
- Ashwin February 28, 2012