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 amount of questions with the same answer in a succession (multiple trues or multiple falses in a row). You're given a string answerKey, where answerKey[i] is the ith question's original answer. You're also provided 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 answerKey[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

answerKey=”TTFF”, K = 2.

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

Output: 4

Example 2

answerKey=”TTFTTFTT”, k=1.

We can toggle ‘F’ at index 2, or we can toggle ‘F’ at index ‘5’. Thus the modifies ‘answerKey’ will be “TTTTTFTT” or “TTFTTTTT”.  In both cases, we have 5 consecutive ‘T’. Therefore the output is 4.

Output: 5  

Approach

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. We've now called our function helper 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 helper function represents the starting index from which a subsequent string begins. Now we create a loop in which two conditions are established if character c is not equal to string element. 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. If ‘M’ does not equal ‘K’, change the current character and increment ‘M’. Also, for each iteration, update ‘ANS’. Finally, return ‘ANS’.

Program

#include<string>
#include<iostream>
#include<vector>
using namespace std;

int helper(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);  
  
  int first=0;  // Index of first character to be modified.
  int last=0;   // Index of last character to be modified.
  int count=0;  // Number of characters modified.
  
  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 solve(string answerKey, int k) {
  int ans1=helper(answerKey,k,'T');
  int ans2=helper(answerKey,k,'F');
  return max(ans1, ans2);       
}
int main(){
  string answerKey;
  cin>>answerKey;
  int K;
  cin>>K;
  cout<<solve(answerKey,K);
  return 0;
}

Input

“TTFTTFTT”, K = 1

Output

5

Time Complexity

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

 

We are using one for loop in the helper 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

In this blog, we learned about an interesting problem, namely, “Maximize the confusion of an Exam”. Then we discuss the solution to the problem in C++. It took O(N) time and constant space. Practice more such ad-hoc problems and improve your logical thinking. Stay tuned for more such problems.

 

Happy Coding!

Was this article helpful ?
0 upvotes