-2

I have the following vector:

std::vector<int> ExampleVector {10, 2, 5, 1, 8, 20};

I need to find a 3 elements (A, B, C) where:

1) A > B < C

2) (A + B) > C

3) A < (B + C)

In the case of ExampleVector, 10 5 8 meet the above conditions.

My initial attempt used a number of iterators with given conditions:

int main()
{
  for(auto first_iterator = A.begin(); first_iterator != A.end(); first_iterator++)
  {
    for(auto second_iterator = first_iterator() + 1; second_iterator != A.end(); second_iterator++)
    {
        for(auto third_iterator = second_iterator() + 1; third_iterator != A.end(); third_iterator++)
        {
            bool condition_1 {(*first_iterator + *second_iterator) > *third_iterator};
            bool condition_2 {(*second_iterator + *third_iterator) > *first_iterator};
            if(condition_1 && condition_2)
            {
                return 1;
            }
        }
    }
  }
  return 0;
}

This effectively results in:

iterator         cycle1  cycle2  cycle3  cycle4  cycle5  cycle6  cycle7 ... N
first_iterator:    10     10       10      10      10     10       10
second_iterator:   2      2        2       2       5      5        5
third_iterator:    5      1        8       20      1      8        20

Clearly this is extremely inefficient!

Are there better approaches I can use for tackling problems such as this?

Babra Cunningham
  • 2,949
  • 1
  • 23
  • 50

2 Answers2

-1

Edit 

vector<vector<double>> store = vector<vector<double>>(0);    
for (int i = 0; i < theVect.size(); ++i) {
        for (vector<double> v : store) {
            if (v.size() == 1) {
                if (v[0] > B) {
                    v.push_back(b)
                    }
            } 
            else if (v.size() == 2) {
            if (A + B > C && A < B + C) {
                return true;
            }
        }
        store.push_back(vector<double> {theVect[i]});
    }

Here's the right answer. --> Requires a single total iteration I believe this is N^2 time where your answer is N^3 time. (Worst case)

*technically a little less then N^3 time but close enough.

** Below this is original post, above is the edit (for future viewers)

Wow that is some convoluted coding.

I believe you have the right idea but your coding style is really strange. A more readable method would to simply use a for loop.

bool condition1 = false;
bool condition2 = false; 
bool condition3 = false;

for (int x = 0; x < theVector.size(); ++x) {
   for (int y = x + 1; y < theVector.size(); ++y) {
        for (int z = y + 1; z < theVector.size(); ++z) {
           if (!condition1) {
               condition1 = conditionChk1(theVector[x], theVector[y], theVector[z]);
           }
           if (!condition2) {
               condition2 = conditionCk2(theVector[x], theVector[y], theVector[z]);
           }
           if (!condition3) {
               condition3 = conditionCk3(theVector[x], theVector[y], theVector[z]);
           }
        }
    }
}

Where the conditionCk methods are accepting the double values and returning a boolean value based on if they meet the requirement. This is essentially your method just much less convoluted.

Jjoseph
  • 206
  • 2
  • 9
  • Alternatively you could choose not to write the separate conditional methods and simply write another if statement then true. (This is just aesthetically nicer) – Jjoseph Dec 19 '16 at 02:03
  • The only difference between mine and yours in that my loops are using iterators. Otherwise its the exact same approach. I used iterator loops as potentially using std::advance or std::next could reduce run time complexity – Babra Cunningham Dec 19 '16 at 02:04
  • For loops vs iterators are extremely similar, for vectors this shouldn't increase performance in any substantial way. – Jjoseph Dec 19 '16 at 02:07
  • Does your problem require each element to be in order? If not, neither of our implementations are correct. – Jjoseph Dec 19 '16 at 02:09
  • Using std::next or std::advance (instead of nested loops) would increase performance. No in this case I just need to identify the existence of the sequence (hence returning 1). – Babra Cunningham Dec 19 '16 at 02:11
  • I updated my answer. (Should be faster requires much less comparisons) Here is a source in which most users report the operator[] being faster. Later though another user comments on it being compile dependantr. If you have a source which states iterators are faster I would genuinely be interested in seeing it. (I don't mean to be combative I would actually like to know for the sake of knowledge) http://stackoverflow.com/questions/776624/whats-faster-iterating-an-stl-vector-with-vectoriterator-or-with-at – Jjoseph Dec 19 '16 at 02:27
-1

You first need to ask yourself if it can be improved

Realign your stuff so that it's read more easily...

1) B < A && B < C
2) (B + A) > C
3) (B + C) > A

If you look closely, if B == 0, A > C and C > A, which is impossible.

user
  • 675
  • 4
  • 11