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

Practice - 5 Tasks

1fill in blank

easy

Complete the code to split the problem into two halves.

DSA Java

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 addition or subtraction instead of division.

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 Java

return solve(start, [1]) + solve(mid + 1, end);

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

Amid

Bend

Cstart

Dmid - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using end instead of mid for the left half.

Using mid - 1 which excludes the middle element.

We solve the left half from start to mid.

3fill in blank

hard

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

DSA Java

if (start [1] end) return array[start];

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

A>

B==

C<

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than or less than which may skip the base case.

Using not equal which never stops recursion.

The base case is when start equals end, meaning one element left.

4fill in blank

hard

Fill both blanks to correctly combine results from subproblems.

DSA Java

return [1] + [2];

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

AleftResult

BrightResult

CmidResult

Dtotal

Attempts:

3 left

💡 Hint

Common Mistakes

Using midResult which is not defined.

Using total which is not a variable here.

We add the results from the left and right subproblems to get the total.

5fill in blank

hard

Fill all three blanks to complete the divide and conquer sum function.

DSA Java

public int sum(int start, int end) {
    if (start [1] end) return array[start];
    int mid = (start + end) [2] 2;
    int leftSum = sum(start, mid);
    int rightSum = sum(mid + 1, end);
    return [3] + rightSum;
}

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

A==

B/

CleftSum

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using inequality in base case.

Using multiplication instead of division for mid.

Returning midResult which is undefined.

The base case checks if start equals end. We find mid by dividing by 2. Finally, we add leftSum and rightSum.

Practice

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

easy

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

B. It uses more memory to store intermediate results

C. It always uses iterative loops instead of recursion

D. It avoids sorting data before processing

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 benefit

   By solving smaller subproblems independently, the overall problem becomes simpler and often faster to solve.

3. Final Answer:

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

4. Quick Check:

   Divide and conquer = break problem into smaller parts [OK]

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

Common Mistakes:

• Thinking divide and conquer always uses loops
• Confusing divide and conquer with dynamic programming
• Believing it avoids recursion

2. Which of the following is the correct syntax to recursively divide an array arr from index start to end in Java?

easy

A. if (start < end) { int mid = (start + end) / 2; divide(arr, start, mid); divide(arr, mid + 1, end); }

B. if (start > end) { int mid = (start + end) / 2; divide(arr, start, mid); divide(arr, mid + 1, end); }

C. while (start < end) { int mid = (start + end) / 2; divide(arr, start, mid); divide(arr, mid + 1, end); }

D. for (int i = start; i < end; i++) { divide(arr, start, i); divide(arr, i + 1, end); }

Solution

1. Step 1: Check the base condition for recursion

   Recursion continues while start is less than end to avoid infinite calls.

2. Step 2: Calculate mid and recursively divide

   Mid is the middle index; recursive calls split array into two halves correctly.

3. Final Answer:

   if (start < end) { int mid = (start + end) / 2; divide(arr, start, mid); divide(arr, mid + 1, end); } -> Option A

4. Quick Check:

   Correct base condition and recursive calls = if (start < end) { int mid = (start + end) / 2; divide(arr, start, mid); divide(arr, mid + 1, end); } [OK]

Hint: Use if (start < end) and mid = (start+end)/2 for recursion [OK]

Common Mistakes:

• Using wrong base condition like start > end
• Using loops instead of recursion
• Incorrect mid calculation

3. What will be the output of the following Java code snippet?

public class Test {
  static int count = 0;
  static void divide(int n) {
    if (n <= 1) return;
    count++;
    divide(n / 2);
    divide(n / 2);
  }
  public static void main(String[] args) {
    divide(8);
    System.out.println(count);
  }
}

medium

A. 3

B. 15

C. 6

D. 7

Solution

1. Step 1: Trace recursive calls for divide(8)

   divide(8) calls divide(4) twice, count increments to 1.

2. Step 2: Trace divide(4) calls

   Each divide(4) calls divide(2) twice, count increments by 2 total (now 3).

3. Step 3: Trace divide(2) calls

   Each of 4 divide(2) calls divide(1) twice (returns), count increments by 4 (total 7).

4. Step 4: Calculate total count

   Increments: 1 (divide 8) + 2 (divide 4s) + 4 (divide 2s) = 7.

5. Final Answer:

   7 -> Option D

6. Quick Check:

   Count increments at non-leaf nodes = 1+2+4=7 [OK]

Hint: Count increments before recursive calls: 1+2+4=7 [OK]

Common Mistakes:

• Counting base case calls
• Not doubling recursive calls
• Miscounting increments

4. Identify the error in the following divide and conquer code snippet and choose the correct fix:

void divide(int[] arr, int start, int end) {
  if (start <= end) {
    int mid = (start + end) / 2;
    divide(arr, start, mid);
    divide(arr, mid + 1, end);
  }
}

medium

A. Change mid calculation to int mid = (start - end) / 2

B. Change base condition to if (start < end) to avoid infinite recursion

C. Add else block to print the array segment

D. Replace recursion with a for loop

Solution

1. Step 1: Analyze base condition

   Using if (start <= end) causes recursion even when start == end, leading to infinite calls.

2. Step 2: Correct base condition

   Changing to if (start < end) stops recursion when start equals end, preventing infinite recursion.

3. Final Answer:

   Change base condition to if (start < end) to avoid infinite recursion -> Option B

4. Quick Check:

   Base condition must stop recursion at single element [OK]

Hint: Use strict less than in base condition to stop recursion [OK]

Common Mistakes:

• Using <= instead of < in base condition
• Incorrect mid calculation
• Adding unnecessary else block

5. You want to use divide and conquer to find the maximum element in an array of 16 integers. Which of the following best describes the number of comparisons needed in the worst case?

hard

A. About 32 comparisons, since each element is compared twice

B. Exactly 16 comparisons, one per element

C. Exactly 15 comparisons, because each divide step compares two halves once

D. About 8 comparisons, dividing array into halves repeatedly

Solution

1. Step 1: Understand divide and conquer max search

   The array is split into halves recursively until single elements remain.

2. Step 2: Count comparisons

   Each merge step compares two maximums from halves, total comparisons = n - 1 for n elements.

3. Final Answer:

   Exactly 15 comparisons, because each divide step compares two halves once -> Option C

4. Quick Check:

   Max comparisons = n - 1 = 15 for 16 elements [OK]

Hint: Max comparisons in divide and conquer = n - 1 [OK]

Common Mistakes:

• Assuming comparisons double each step
• Confusing comparisons with number of elements
• Thinking fewer than n-1 comparisons possible