Why Divide and Conquer and What It Gives You in DSA C++ - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to split the problem into two halves.

DSA C++

int mid = (start + end) [1] 2;

Drag options to blanks, or click blank then click option'

A/

B+

C*

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using multiplication instead of division.

Using subtraction which gives wrong midpoint.

We divide the sum of start and end by 2 to find the middle point.

2fill in blank

medium

Complete the code to recursively solve the left half of the problem.

DSA C++

solve(start, [1]);

Drag options to blanks, or click blank then click option'

Amid + 1

Bend

Cmid

Dstart

Attempts:

3 left

💡 Hint

Common Mistakes

Using end instead of mid for left half.

Using mid + 1 which is for the right half.

We solve the left half from start to mid.

3fill in blank

hard

Fix the error in the base case condition to stop recursion.

DSA C++

if (start [1] end) return;

Drag options to blanks, or click blank then click option'

A==

B>

C<

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' which causes infinite recursion on single elements.

Using '<' which stops recursion too early.

The recursion stops when start == end, meaning a single element (base case).

4fill in blank

hard

Fill both blanks to combine results from left and right halves.

DSA C++

int leftResult = solve(start, [1]);
int rightResult = solve([2], end);

Drag options to blanks, or click blank then click option'

Amid

Bmid + 1

Cstart

Dend

Attempts:

3 left

💡 Hint

Common Mistakes

Using start for right half start.

Using end for left half end.

The left half is from start to mid, and the right half is from mid + 1 to end.

5fill in blank

hard

Fill all three blanks to merge two sorted halves into one sorted array.

DSA C++

int i = [1], j = [2], k = [3];
while (i <= mid && j <= end) {
  if (arr[i] <= arr[j]) temp[k++] = arr[i++];
  else temp[k++] = arr[j++];
}

Drag options to blanks, or click blank then click option'

Astart

Bmid + 1

Cend

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Starting i or j at wrong indices.

Starting k at mid or end instead of 0.

We start merging from the beginning of left half (start) and right half (mid + 1), and k starts at 0 for the temp array.

Practice

1. What is the main advantage of using the Divide and Conquer approach in algorithms?

easy

A. It uses more memory to store all intermediate results

B. It breaks a problem into smaller subproblems to solve them independently

C. It always solves problems in a single step

D. It avoids recursion completely

Solution

1. Step 1: Understand the divide and conquer approach

   Divide and conquer splits a big problem into smaller parts that are easier to solve.

2. Step 2: Identify the main advantage

   By solving smaller subproblems independently, it simplifies complex problems and often improves efficiency.

3. Final Answer:

   It breaks a problem into smaller subproblems to solve them independently -> Option B

4. Quick Check:

   Divide and conquer = break into smaller parts [OK]

Hint: Divide big problems into smaller parts to solve easily [OK]

Common Mistakes:

• Thinking divide and conquer avoids recursion
• Believing it solves problems in one step
• Confusing it with using more memory

2. Which of the following is the correct syntax to recursively call a function divideAndConquer on two halves of an array arr from indices start to mid and mid+1 to end in C++?

easy

A. divideAndConquer(arr, start, mid); divideAndConquer(arr, mid + 1, end);

B. divideAndConquer(arr, start, end); divideAndConquer(arr, mid, end);

C. divideAndConquer(arr, 0, mid); divideAndConquer(arr, mid, end);

D. divideAndConquer(arr, start, mid - 1); divideAndConquer(arr, mid, end);

Solution

1. Step 1: Understand the indices for dividing the array

   The array is split into two parts: from start to mid, and from mid+1 to end.

2. Step 2: Match the correct recursive calls

   Calling divideAndConquer(arr, start, mid) and divideAndConquer(arr, mid + 1, end) correctly covers both halves without overlap or missing elements.

3. Final Answer:

   divideAndConquer(arr, start, mid); divideAndConquer(arr, mid + 1, end); -> Option A

4. Quick Check:

   Split array at mid, call both halves [OK]

Hint: Call function on start to mid and mid+1 to end [OK]

Common Mistakes:

• Using mid instead of mid+1 for second half
• Overlapping indices causing repeated work
• Missing elements by incorrect index ranges

3. Consider the following C++ code snippet using divide and conquer to find the sum of an array segment:

int sumArray(int arr[], int start, int end) {
    if (start == end) return arr[start];
    int mid = (start + end) / 2;
    int leftSum = sumArray(arr, start, mid);
    int rightSum = sumArray(arr, mid + 1, end);
    return leftSum + rightSum;
}

int main() {
    int arr[] = {2, 4, 6, 8};
    int result = sumArray(arr, 0, 3);
    std::cout << result << std::endl;
    return 0;
}

What is the output when this code runs?

medium

A. 20

B. 10

C. 0

D. Compilation error

Solution

1. Step 1: Trace the recursive calls

   The function splits the array into halves and sums each part: - sumArray(arr,0,3) splits into sumArray(arr,0,1) and sumArray(arr,2,3) - sumArray(arr,0,1) splits into sumArray(arr,0,0)=2 and sumArray(arr,1,1)=4 - sumArray(arr,2,3) splits into sumArray(arr,2,2)=6 and sumArray(arr,3,3)=8

2. Step 2: Calculate sums and combine

   Left sum = 2 + 4 = 6 Right sum = 6 + 8 = 14 Total sum = 6 + 14 = 20

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Sum of 2+4+6+8 = 20 [OK]

Hint: Sum halves recursively and add results [OK]

Common Mistakes:

• Confusing mid calculation causing wrong splits
• Adding indices instead of values
• Assuming output is partial sum

4. The following code attempts to implement divide and conquer to find the maximum element in an array segment. Identify the error:

int maxElement(int arr[], int start, int end) {
    if (start == end) return arr[start];
    int mid = (start + end) / 2;
    int leftMax = maxElement(arr, start, mid);
    int rightMax = maxElement(arr, mid, end);
    return (leftMax > rightMax) ? leftMax : rightMax;
}

medium

A. The comparison operator should be '<' instead of '>'

B. The base case condition is incorrect

C. The second recursive call should be from mid + 1 to end

D. The function should return sum instead of max

Solution

1. Step 1: Analyze the recursive calls

   The first call is maxElement(arr, start, mid), which is correct. The second call is maxElement(arr, mid, end), which overlaps the mid element with the first call.

2. Step 2: Correct the second call range

   The second call should start from mid + 1 to avoid overlapping and missing elements. So it should be maxElement(arr, mid + 1, end).

3. Final Answer:

   The second recursive call should be from mid + 1 to end -> Option C

4. Quick Check:

   Second call must start at mid+1 to avoid overlap [OK]

Hint: Second half starts at mid+1, not mid [OK]

Common Mistakes:

• Using mid instead of mid+1 causing overlap
• Changing base case unnecessarily
• Confusing max with sum

5. You want to use divide and conquer to count how many elements in an array are greater than a given value x. Which of the following approaches correctly applies divide and conquer to solve this?

hard

A. Iterate the entire array once and count elements > x without recursion

B. Count elements > x only in the middle element of the array

C. Split the array into halves but only count elements > x in the left half recursively

D. Split the array into halves, count elements > x in each half recursively, then add counts

Solution

1. Step 1: Understand the problem and divide and conquer method

   We want to count elements greater than x by breaking the array into smaller parts and counting in each part.

2. Step 2: Apply divide and conquer correctly

   Split the array into two halves, recursively count elements > x in each half, then add the two counts to get the total.

3. Final Answer:

   Split the array into halves, count elements > x in each half recursively, then add counts -> Option D

4. Quick Check:

   Divide, count in parts, then combine counts [OK]

Hint: Count recursively in both halves, then add [OK]

Common Mistakes:

• Counting only one half and ignoring the other
• Not using recursion for divide and conquer
• Counting only one element instead of all