1.
Introduction
2.
Problem Statement
2.1.
Example 1
2.2.
Example 2
3.
Approach
4.
Program
4.1.
Input
4.2.
Output
4.3.
Time Complexity
4.4.
Space Complexity
5.
Key Takeaways
Last Updated: Mar 27, 2024

Maximize the Confusion of an Exam

Husen Kagdi
0 upvote
Create a resume that lands you SDE interviews at MAANG
Speaker
Anubhav Sinha
SDE-2 @
12 Jun, 2024 @ 01:30 PM

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.

Recommended topic, kth largest element in an array, and Euclid GCD Algorithm

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

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

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

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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

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!

Live masterclass