Partition and product

Questions 1 to 5 of 8

1. 1. Predict the output of this program. Ignore the trailing space after the last value. ``cpp #include <cstddef> #include <iostream> #include <utility> #include <vector> using namespace std; void sort_flags(vector<int>& a) { size_t lo = 0, mid = 0, hi = a.size(); while (mid < hi) { if (a[mid] == 0) { swap(a[lo], a[mid]); ++lo; ++mid; } else if (a[mid] == 1) { ++mid; } else { --hi; swap(a[mid], a[hi]); } } } int main() { vector<int> v = {2, 1, 0, 2, 1}; sort_flags(v); for (int x : v) cout << x << ' '; } ``

   2 1 0 2 10 1 2 1 20 1 1 2 21 0 1 2 2
2. 2. Put the steps of the second version of productExceptSelf in the order the code runs them.

   Use the arrows to put the steps in order.

   1. 1.Walk left to right: store running in result[i], then multiply running by nums[i]↑↓
   2. 2.Set running back to 1↑↓
   3. 3.Walk right to left: multiply result[i - 1] by running, then multiply running by nums[i - 1]↑↓
   4. 4.Make result the same length as nums, with every box set to 1↑↓
3. 3. Why does the product-except-self lesson avoid dividing the total product by each value?

   Dividing by a zero value is undefined behaviour, and nums may contain a zeroDivision is always slower than multiplication, so the code would be too slowInteger division rounds the answers down, so they would always be wrongThe total product would overflow an int before any division happens
4. 4. When the card at mid is a 2, put these actions in the order sort_flags does them.

   Use the arrows to put the steps in order.

   1. 1.Swap the card at mid with the card at hi↑↓
   2. 2.Leave mid where it is↑↓
   3. 3.Repeat the loop, so the card that moved into mid is checked↑↓
   4. 4.Subtract 1 from hi↑↓
5. 5. Predict the output of this program. Ignore the trailing space after the last value. ``cpp #include <iostream> #include <vector> using namespace std; vector<long long> productExceptSelf(const vector<int>& nums) { size_t n = nums.size(); vector<long long> result(n, 1); long long running = 1; for (size_t i = 0; i < n; ++i) { result[i] = running; running *= nums[i]; } running = 1; for (size_t i = n; i > 0; --i) { result[i - 1] *= running; running *= nums[i - 1]; } return result; } int main() { for (long long x : productExceptSelf({2, 5, -1, 3})) cout << x << ' '; } ``

   15 6 -30 10-15 -6 30 -10-15 -6 15 -100 0 0 0