Algorithms : complete 01-algorithmic_toolbox 02-greedy_algorithms

1 files changed, 15 insertions, 1 deletions

diff --git a/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/different_summands.cpp b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/different_summands.cpp
index 0f8b4cb..fe36866 100644
--- a/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/different_summands.cpp
+++ b/01-algorithmic_toolbox/02-greedy_algorithms/05-different_summands/different_summands.cpp
@@ -5,7 +5,20 @@ using std::vector;
 
 vector<int> optimal_summands(int n) {
   vector<int> summands;
-  //write your code here
+  int s = 0;
+  for (int i = 1; ; i++) {
+      s += i;
+      if (s == n) {
+          summands.push_back(i);
+          break;
+      }
+      if (s > n) {
+          s -= (i + i - 1);
+          summands[summands.size() - 1] = (n - s);
+          break;
+      }
+      summands.push_back(i);
+  }
   return summands;
 }
 
@@ -17,4 +30,5 @@ int main() {
   for (size_t i = 0; i < summands.size(); ++i) {
     std::cout << summands[i] << ' ';
   }
+  std::cout << '\n';
 }