Is my solution considered time efficient? I understand that it is inefficient from memory, because data structures \ containers are used, but I don’t know how to determine by time.

The task:

C4
The communication channel transmits positive integers not exceeding 1000. After the termination, the control value is transmitted - the largest number R, which satisfies the following conditions:

1) R is the sum of two different transmitted sequence elements.
2) R is an odd number.

Write a program to solve the problem, which will be effective both in time and in memory (or at least one of these characteristics).

A program is considered effective in time if the time of program operation is proportional to the number of elements of the sequence N, i.e. when N is increased by k times, the program operation time should increase by no more than k times.

#include <iostream> #include <vector> #include <conio.h> #include <algorithm> int main() { std::vector<int> vec; std::vector<int>::size_type count; std::cin >> count; for (std::vector<int>::size_type i = 0; i < count; i++) { std::vector<int>::size_type current; std::cin >> current; vec.push_back(current); } std::sort(vec.begin(), vec.end()); std::vector<int>::size_type maximum = 0; std::vector<int>::size_type left = vec.size() - 2; std::vector<int>::size_type right = vec.size() - 1; for ( std::vector<int>::size_type i = 0; ++i < vec.size(); ) { std::vector<int>::size_type summary = vec[left] + vec[right]; if ((maximum < summary) && (summary & 1 != 0)) { maximum = summary; left--; } else { if ((summary & 1) == 0) { left--; } else { right--; } } } if (maximum) { std::cout << "\nFound: " << maximum; } else { std::cout << "\nNot found"; } _getch(); }
  • one
    But does the sort function alone no longer satisfy the set conditions? - zed
  • @zed you are right. When I wrote, I did not think about it at all. And what if I have 2-3 cycles in the program, but none of them is invested in the other. What happens with time according to the criteria of the task? - phen0menon
  • The sum of the times of these cycles. - HasmikGaryaka
  • If there are no nested loops, then time remains N. - zed
  • Right in the cycle where the data is entered, do all the work. The answer says what. - HasmikGaryaka

1 answer 1

After you have sorted the vector, there is no need to iterate. You must take the largest odd number plus the largest even. The odd sum can be, if one number is even and the other is odd. If there is no odd, then there is no answer. Do not make the sort that takes nlog n, but simply look for the maximum even and odd during time n. Yes, and store all the data in the vector is not required.

  • Thank you very much. Before you could not imagine a solution without iterating through the array. Can someone come in handy - pastebin.com/VN2Szr0k - phen0menon
  • If there is no odd, you need to display a message. If (odd == 0) cout << "# $ %% ^^"; - HasmikGaryaka
  • and also displays :) - phen0menon