Why Backtracking and What Greedy Cannot Solve in DSA C - Test Your Knowledge

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if a number can be placed in the current position of the Sudoku board.

DSA C

int isSafe(int board[9][9], int row, int col, int num) {
    for (int x = 0; x < 9; x++) {
        if (board[row][x] == [1]) {
            return 0;
        }
    }
    return 1;
}

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

Anum

Brow

Ccol

Dx

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with row or col instead of num.

Using the loop variable incorrectly.

The function checks if the number num is already present in the given row. So, we compare board[row][x] with num.

2fill in blank

medium

Complete the code to move to the next cell in the Sudoku board during backtracking.

DSA C

void solveSudoku(int board[9][9], int row, int col) {
    if (col == 9) {
        row++;
        col = [1];
    }
    if (row == 9) {
        // Sudoku solved
        return;
    }
    // Continue solving
}

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

A1

Brow

C0

Dcol

Attempts:

3 left

💡 Hint

Common Mistakes

Setting col to 9 instead of 0.

Incrementing row and col incorrectly.

When column reaches 9, we move to the next row and reset column to 0 to start from the first column of the new row.

3fill in blank

hard

Fix the error in the greedy coin change function to correctly count minimum coins.

DSA C

int minCoins(int coins[], int n, int amount) {
    int count = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (amount >= coins[[1]]) {
            amount -= coins[i];
            count++;
        }
    }
    return count;
}

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

An

Bi

C0

Dcount

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong index like n or 0 inside coins[].

Using count variable inside coins[].

The loop variable i is used to access the current coin denomination. Using i inside the while condition ensures correct coin value is checked.

4fill in blank

hard

Fill both blanks to create a backtracking function that tries all subsets to find a target sum.

DSA C

int subsetSum(int arr[], int n, int sum, int index) {
    if (sum == 0) return 1;
    if (index == n || sum < 0) return 0;
    return subsetSum(arr, n, sum - [1], index + 1) || subsetSum(arr, n, sum, [2]);
}

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

Aarr[index]

Bindex

Cindex + 1

Dsum

Attempts:

3 left

💡 Hint

Common Mistakes

Not moving to next index in recursive calls.

Using wrong variables in recursive calls.

The first recursive call includes the current element arr[index] and moves to the next index index + 1. The second call excludes the current element and also moves to the next index index + 1.

5fill in blank

hard

Fill all three blanks to implement a greedy algorithm that selects activities with maximum count.

DSA C

int activitySelection(int start[], int finish[], int n) {
    int count = 1;
    int last_finish = finish[0];
    for (int i = 1; i < n; i++) {
        if (start[[1]] >= last_finish) {
            count++;
            last_finish = finish[[2]];
        }
    }
    return count;
}

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

Ai

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong indices like 0 instead of i.

Not updating last_finish correctly.

In the loop, we check if the start time of the current activity start[i] is after or equal to the last selected activity's finish time. If yes, we select it and update last_finish to finish[i]. The variable i is used consistently for indexing.