PROBLEM LINK:
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:
- Increasing the count variable twice in a single iteration.
- 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.