BROKPHON - Editorial

Author: Andrii Mostovyi
Tester: Sergey Kulik

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:

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

int main() {
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
``````for(int i=0;i<n;i++)