BROKPHON - Editorial

PROBLEM LINK:

Practice
Contest

Author: Andrii Mostovyi
Tester: Sergey Kulik
Editorialist: Adury Surya Kiran

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Basics like iterating loops in any of your favourite programming language

PROBLEM:

There are N players sitting in a line, the first player receives a message and it is transmitted from each player to his next player sitting in the line. You are given the messages received by all the players and are asked to find the number of players that could mishear the message or whisper it wrongly.

EXPLANATION:

Given an array of N integers A[1], A[2], …A[N]. You need to find number of integers A[i], such that A[i] is not equal to either A[i-1] or A[i+1].
Keep a counter variable equal to zero in the beginning of each test case and just iterate through each of the index i from 1 to N and increase the counter variable by 1 if A[i] != A[i-1] OR A[i] != A[i+1]. Print the counter variable for each test case.

C++ Code :

#include <iostream>
using namespace std;
// allocate more than necessary
int A[112345];
int main() {
    int T;
    cin >> T;
    for (int cas = 1; cas <= T; cas++) {
        // we use 'cas' because 'case' is a keyword
        int N;
        cin >> N;
        int count = 0;
        for (int i = 1; i <= N; i++) {
            cin >> A[i];
        }
        for (int i = 1; i <= N; i++) {
            if(i > 1){
                if(A[i] != A[i - 1]){
                    count++;
                    continue;
                }
            }
            if(i < N){
                if(A[i] != A[i + 1]){
                    count++;
                }
            }
        }
        cout << count << '\n';
    }
}

Common mistakes:

  1. Increasing the count variable twice in a single iteration.
  2. Accessing out of bound memory, i.e, comparing A[1] with A[0] or A[N] with A[N + 1].

Complexity : O(N) per each test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

#include <iostream>
#include <set>
using namespace std;

int main() {
	// your code goes here
	int tc;
	cin>>tc;
	
	while(tc--)
	{
            set <int> ans;
	    int n;
	    cin>>n;
	    int arr[n];
	    for(int i=0;i<=n;i++)
	    {
	       cin>>arr[i];
	    }
	    for(int j=1;j<n;j++)
	    {
	        if(arr[j]!=arr[j-1])
	        {
	            ans.insert(j);
	            ans.insert(j-1);
	        }
	    }
	    cout<<ans.size()<<endl;
	}
	return 0;
}

What is the error in this code for multiple test case

Hey @innocentpranja
Thanks for asking your doubt.

There is a typo in your code :point_down:

here is the corrected code.

for(int i=0;i<n;i++)