Maximize the Confusion of an Exam

Husen Kagdi
Last Updated: May 13, 2022

Introduction

Professor Reddy is a Physics teacher. He will be organizing a physics test that will contain True / False questions. Each question has an answer which is either true or false. He wants to design the question paper to maximize the confusion for the students. One way he can do this is to keep a series of questions whose answer is True, then keep a series of questions whose answer is False, and so on. Thus he can create confusion among the students. Let us now discuss the problem statement and the possible solution.

Problem Statement

A teacher is creating an exam containing N true/false questions, with the letters 'T' indicating true and 'F' indicating false. He intends to confuse the students by increasing the number of questions with the same answer in succession (multiple trues or multiple falses in a row). You're given a string ‘ANSWER_KEY’, where ANSWER_KEY[i] is the ‘i’th question's original answer. You're also provided with an integer ‘K’, which represents the maximum number of times you can conduct the following operation: Set any question's answer key to 'T' or 'F' (i.e., set ANSWER_KEY[i] to 'T' or 'F'). After completing the operation ‘K’ times, return the maximum number of consecutive 'T's or 'F's in the answer key.

Example 1:

ANSWER_KEY = ”FFTTTTTT”, K = 2.

We can toggle the first two ‘F’ to ‘T’ as K = 2. So we can do the operation two times at max. Thus, the final string will be “TTTTTTTT”. As a result, there are four consecutive ‘T’ in a row. 

Output: 8

Example 2:

ANSWER_KEY = ”TTFTTTTT”, K = 1.

We can toggle ‘F’ at index 2. Thus the modifies ‘ANSWER_KEY’ will be “TTTTTTTT”.  In both cases, we have 8 consecutive ‘T’. Therefore the output is 8.

Output: 8

Approach

The base condition occurs when ‘K’ is greater than half of the string length. We can argue that we can make the entire string either true or false. Now we calculate the number of consecutive T’s and the number of consecutive F’s using two separate function calls. Then we greedily try to find an answer such that the given two conditions are established. Finally, we return the answer.

Algorithm

  1. If ‘K’ is higher than half the length of the string, the answer is the string length. Since if the count of 'F' is greater than or equal to the count of 'T,' then the count of 'T' must be less than or equal to the count of 'F,' and vice versa.
  2. We've now called our function consecutiveCount() twice. We try to determine the maximum number of consecutive T's in the first call. Then, we try to determine the maximum number of consecutive Fs in the second call. The ‘BEGIN’ variable in the consecutiveCount() function represents the starting index from which a subsequent string begins.
  3.  Now, we create a loop in which two conditions are established if character c is not equal to the string element.
  4.  If ‘COUNT’ equals ‘K’, the ‘BEGIN’ variable is updated, which indicates the first modified character of the string is removed, and the current character is modified.
  5.  If ‘M’ does not equal ‘K’, change the current character and increment ‘M.’Also, for each iteration, update ‘ANS’. Finally, return ‘ANS’.

Program

#include<iostream>
#include<string>
#include<vector>

using namespace std;

int consecutiveCount(string str, int k, char c) {
  int ans = 0, begin = 0, n = str.size();

  // Stores index of modified characters in the string.
  vector <int> v(n);

  // Index of first character to be modified.
  int first = 0;

  // Index of last character to be modified.
  int last = 0;

  // Number of characters modified.
  int count = 0;
  for (int i = 0; i < n; i++) {
    if (str[i] != c) {
      // If count == k, we store update begin and modify the current character.
      if (k == count) {
        begin = v[first++] + 1;
        v[last++] = i;
      }

      // We modify the current character and increment count.
      else {
        v[last++] = i;
        count++;
      }
    }
    ans = max(ans, i - begin + 1);
  }
  return ans;
}

int maximizeConfusionOfAnExam(string answerKey, int k) {
  int ans1 = consecutiveCount(answerKey, k, 'T');
  int ans2 = consecutiveCount(answerKey, k, 'F');
  return max(ans1, ans2);
}

int main() {
  string answerKey;
  cout << "Enter the answer key: ";
  cin >> answerKey;
  cout << "Enter the value of K: ";
  int K;
  cin >> K;
  cout << "Answer is: " << maximizeConfusionOfAnExam(answerKey, K);
  return 0;
}


Input

Enter the answer key: TTFTTFTT 
Enter the value of K: 1


Output

Answer is: 5


Time Complexity

O(N), whereN’ is the size of the string.

We are using one for loop in the consecutiveCount method. The loop iterates upon string length. Thus the time complexity is O(N).

Space Complexity

O(1). We are using constant space as we just declaring a few variables. Thus space complexity is O(1).

Key Takeaways

We saw an interesting ad-hoc problem i.e., Maximize the confusion of an Exam. It took O(N) time and constant space. But every ad-hoc problem is unique in itself and requires separate logic, thus don’t stop practising and Move to our industry-leading practice platform CodeStudio to practice more such problems and many more.

Thank You and Happy Coding!

Was this article helpful ?
0 upvotes