Let’s tackle the problems from your CS-100 Practice Problem Set one by
one. Since these are practice problems for an exam, I’ll provide solutions
in C++ that leverage the concepts you’ve been studying (`sort`,
`reverse`, `find`, `substr`, `bool`, `vector`, `pair`, etc.). I’ll also keep the
solutions concise, efficient, and well-commented for your cheat sheet.
Let’s go through each problem systematically.
---
### **Problem 1: Reverse Array**
**Task**: Write a function that reverses an integer array.
#### Solution
We can use the `reverse` function from the `<algorithm>` library, which
you’ve already studied.
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
// Function to reverse an array and return it
void reverseArray(int arr[], int n) {
reverse(arr, arr + n); // Reverses the array in place
int main() {
int arr[] = {1, 2, 3, 4, 5};
int n = sizeof(arr) / sizeof(arr[0]);
reverseArray(arr, n);
for (int i = 0; i < n; i++) {
cout << arr[i] << " "; // Output: 5 4 3 2 1
return 0;
```
#### Notes
- **Alternative**: If you can’t use `reverse`, you can manually swap
elements:
```cpp
for (int i = 0; i < n / 2; i++) {
swap(arr[i], arr[n - 1 - i]);
```
- **Time Complexity**: \(O(n)\)
---
### **Problem 2: Palindrome Arrays**
**Task**: Check if an array reads the same forwards and backwards (e.g.,
`[2, 3, 5, 5, 3, 2]` is a palindrome).
#### Solution
We can compare elements from the start and end, moving inward.
Alternatively, we can create a copy of the array, reverse it, and compare.
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isPalindrome(int arr[], int n) {
for (int i = 0; i < n / 2; i++) {
if (arr[i] != arr[n - 1 - i]) {
return false; // Not a palindrome if elements don't match
return true;
int main() {
int arr1[] = {2, 3, 5, 5, 3, 2};
int arr2[] = {1, 2, 3, 5, 2};
int n1 = sizeof(arr1) / sizeof(arr1[0]);
int n2 = sizeof(arr2) / sizeof(arr2[0]);
cout << (isPalindrome(arr1, n1) ? "true" : "false") << endl; // Output:
true
cout << (isPalindrome(arr2, n2) ? "true" : "false") << endl; // Output:
false
return 0;
```
#### Notes
- **Alternative with `reverse`**:
```cpp
vector<int> copy(arr, arr + n);
reverse(copy.begin(), copy.end());
for (int i = 0; i < n; i++) {
if (arr[i] != copy[i]) return false;
return true;
```
- **Time Complexity**: \(O(n)\)
---
### **Problem 3: Array Split**
**Task**: Split an array into two halves (e.g., `[1, 2, 3, 4, 5, 6, 7, 8]` splits
into `[1, 2, 3, 4]` and `[5, 6, 7, 8]`).
#### Solution
We’ll split the array into two parts at the middle index. Since the problem
doesn’t specify output format, we’ll print the two halves.
```cpp
#include <iostream>
using namespace std;
void splitArray(int arr[], int n) {
int mid = n / 2; // Middle index
// First half
cout << "First half: ";
for (int i = 0; i < mid; i++) {
cout << arr[i] << " ";
cout << endl;
// Second half
cout << "Second half: ";
for (int i = mid; i < n; i++) {
cout << arr[i] << " ";
cout << endl;
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
int n = sizeof(arr) / sizeof(arr[0]);
splitArray(arr, n);
// Output:
// First half: 1 2 3 4
// Second half: 5 6 7 8
return 0;
```
#### Notes
- **If \(n\) is odd**: The first half gets \(\lfloor n/2 \rfloor\) elements, the
second gets the rest.
- **Using `vector`** (if storing halves is needed):
```cpp
vector<int> first(arr, arr + mid);
vector<int> second(arr + mid, arr + n);
```
- **Time Complexity**: \(O(n)\)
---
### **Problem 4: Rotate Array Left by \(d\) Positions**
**Task**: Rotate an array to the left by \(d\) positions (e.g., `[1, 2, 3, 4, 5,
6, 7]` with \(d=2\) becomes `[3, 4, 5, 6, 7, 1, 2]`).
#### Solution
We can use the `reverse` function to rotate the array:
1. Reverse the first \(d\) elements.
2. Reverse the remaining \(n-d\) elements.
3. Reverse the entire array.
```cpp
#include <iostream>
#include <algorithm>
using namespace std;
void rotateLeft(int arr[], int n, int d) {
d = d % n; // Handle d > n
if (d == 0) return;
reverse(arr, arr + d); // Reverse first d elements
reverse(arr + d, arr + n); // Reverse remaining elements
reverse(arr, arr + n); // Reverse entire array
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
int d = 2;
rotateLeft(arr, n, d);
for (int i = 0; i < n; i++) {
cout << arr[i] << " "; // Output: 3 4 5 6 7 1 2
cout << endl;
return 0;
```
#### Notes
- **Why This Works**:
- Original: `[1, 2, 3, 4, 5, 6, 7]`, \(d=2\)
- Reverse first \(d\): `[2, 1, 3, 4, 5, 6, 7]`
- Reverse rest: `[2, 1, 7, 6, 5, 4, 3]`
- Reverse all: `[3, 4, 5, 6, 7, 1, 2]`
- **Time Complexity**: \(O(n)\)
---
### **Problem 5: Find Two Elements with Sum Closest to Zero**
**Task**: Find two elements in an array whose sum is closest to zero (e.g.,
`[5, -5, 10, -15, 20]` → `-5, 5`).
#### Solution
Sort the array and use two pointers to find the pair with the smallest
absolute sum.
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
pair<int, int> closestToZero(int arr[], int n) {
vector<int> v(arr, arr + n);
sort(v.begin(), v.end()); // Sort the array
int left = 0, right = n - 1;
int minSum = INT_MAX;
pair<int, int> result;
while (left < right) {
int sum = v[left] + v[right];
if (abs(sum) < abs(minSum)) {
minSum = sum;
result = {v[left], v[right]};
if (sum < 0) left++; // Sum too negative, increase it
else right--; // Sum too positive, decrease it
return result;
int main() {
int arr[] = {5, -5, 10, -15, 20};
int n = sizeof(arr) / sizeof(arr[0]);
auto [a, b] = closestToZero(arr, n);
cout << a << "," << b << endl; // Output: -5,5
return 0;
```
#### Notes
- **Why Sort?**: Sorting allows us to use two pointers to efficiently find
the closest sum.
- **Time Complexity**: \(O(n \log n)\) due to sorting.
- **Test Cases**:
- `[3, 7, -2, 5, -4]` → `-2, 3` (sum = 1)
- `[0, 2, 3, -6, 5]` → `-6, 5` (sum = -1)
---
### **Problem 6: Water Collection (Trapping Rain Water)**
**Task**: Compute how much water can be trapped in an elevation map
(e.g., `[0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]` traps 12 units).
#### Solution
Use two arrays to store the maximum height to the left and right of each
bar, then calculate trapped water.
```cpp
#include <iostream>
using namespace std;
int trapWater(int arr[], int n) {
int leftMax[n], rightMax[n];
leftMax[0] = arr[0];
for (int i = 1; i < n; i++) {
leftMax[i] = max(leftMax[i - 1], arr[i]);
rightMax[n - 1] = arr[n - 1];
for (int i = n - 2; i >= 0; i--) {
rightMax[i] = max(rightMax[i + 1], arr[i]);
int water = 0;
for (int i = 0; i < n; i++) {
water += min(leftMax[i], rightMax[i]) - arr[i];
return water;
int main() {
int arr[] = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
int n = sizeof(arr) / sizeof(arr[0]);
cout << trapWater(arr, n) << endl; // Output: 12
return 0;
```
#### Notes
- **Logic**: For each bar, water trapped = \(\min(\text{leftMax}, \
text{rightMax}) - \text{height}\).
- **Time Complexity**: \(O(n)\), Space Complexity: \(O(n)\).
- **Test Cases**:
- `[7, 4, 0, 9]` → 10
- `[6, 9, 9]` → 0
- `[3, 0, 0, 2, 0, 4]` → 10
---
### **Problem 7: Roadtrip Adventure**
**Task**: Given locations and gas costs, calculate how many cycles you
can complete with a 50-liter gas tank, starting from a chosen index,
moving rightwards in a cyclic array.
#### Solution
Simulate the journey, tracking gas usage and cycles.
```cpp
#include <iostream>
using namespace std;
void roadtrip(char locations[], int costs[], int n, int start) {
int tank = 50; // Gas tank capacity
int cycles = 0;
int pos = start;
cout << "Starting at location: " << locations[start] << endl;
while (tank >= costs[pos]) { // Continue while enough gas
tank -= costs[pos]; // Use gas to move to next location
pos = (pos + 1) % n; // Move to next location (cyclic)
if (pos == start) cycles++; // Increment cycle if back to start
cout << "Number of cycles completed: " << cycles << endl;
cout << "Gas left: " << tank << " Litres" << endl;
cout << "Final Location: " << locations[pos] << endl;
}
int main() {
char locations[] = {'A', 'B', 'C', 'D', 'E'};
int costs[] = {10, 20, 15, 25, 30}; // Example costs
int n = 5;
int start = 2; // Start at C
cout << "starting index: " << start << endl;
roadtrip(locations, costs, n, start);
return 0;
```
#### Notes
- **Assumption**: Used example costs since none were provided.
- **Output for Example** (with costs `[10, 20, 15, 25, 30]`, start at index
2):
```
starting index: 2
Starting at location: C
Number of cycles completed: 1
Gas left: 1 Litres
Final Location: B
```
- **Time Complexity**: \(O(k)\), where \(k\) is the number of moves
(depends on gas and costs).
- **Optional Features** (for practice):
- User input for tank capacity:
```cpp
int tank;
cout << "Enter tank capacity: ";
cin >> tank;
```
- Input validation for `start`:
```cpp
if (start < 0 || start >= n) {
cout << "Invalid starting index" << endl;
return;
```
---
### Summary for Your Cheat Sheet
- **Problem 1 (Reverse Array)**: Use `reverse(arr, arr + n)`.
- **Problem 2 (Palindrome)**: Compare elements from both ends.
- **Problem 3 (Split Array)**: Split at `n/2`, print halves.
- **Problem 4 (Rotate Left)**: Use `reverse` three times.
- **Problem 5 (Sum Closest to Zero)**: Sort, use two pointers.
- **Problem 6 (Water Collection)**: Use leftMax/rightMax arrays.
- **Problem 7 (Roadtrip)**: Simulate cyclic movement, track gas.
These solutions use concepts you’ve studied (`sort`, `reverse`, `bool`,
`vector`, etc.) and should help you prepare for similar array-based
problems in your exam. Good luck! Let me know if you need further
clarification.
