I was practising this problem asked in the last round of Google Kick Start 2020. The problem is called Record Breaker and is as follows:
Isyana is given the number of visitors at her local theme park on N consecutive days. The number of visitors on the i-th day is Vi. A day is record breaking if it satisfies both of the following conditions: The number of visitors on the day is strictly larger than the number of visitors on each of the previous days. Either it is the last day, or the number of visitors on the day is strictly larger than the number of visitors on the following day. Note that the very first day could be a record breaking day!
Please help Isyana find out the number of record breaking days.
Input The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. The second line contains N integers. The i-th integer is Vi.
Output For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of record breaking days.
Limits Time limit: 20 seconds per test set. Memory limit: 1GB. 1 ≤ T ≤ 100. 0 ≤ Vi ≤ 2 × 105.
Test set 1 1 ≤ N ≤ 1000.
Test set 2 1 ≤ N ≤ 2 × 105 for at most 10 test cases. For the remaining cases, 1 ≤ N ≤ 1000.
Sample
Input 4 8 1 2 0 7 2 0 2 0 6 4 8 15 16 23 42 9 3 1 4 1 5 9 2 6 5 6 9 9 9 9 9 9
Output Case #1: 2 Case #2: 1 Case #3: 3 Case #4: 0
In Sample Case #1, the bold and underlined numbers in the following represent the record breaking days: 1 2 0 7 2 0 2 0.
In Sample Case #2, only the last day is a record breaking day.
In Sample Case #3, the first, the third, and the sixth days are record breaking days.
In Sample Case #4, there is no record breaking day.
This is the solution I created. It gives a Wrong Answer in the first Test Case but I can't think of any specific case that I have missed.
#include<iostream>
#include<algorithm>
using namespace std;
int record_breaking(long long int arr[], long long int n)
{
long long int ans = 0;
long long int m = arr[0];
for(long long int i = 0; i<n; i++)
{
//For first element
if(i == 0 && arr[0] > arr[1])
{
ans++;
}
//For the last element
else if(i == n - 1 && arr[i] > m)
{
ans++;
//cout<<arr[i]<<" is a answer "<<endl;
}
//Normal Case
else if(arr[i] > m && arr[i] > arr[i + 1])
{
ans++;
//cout<<arr[i]<<" is a answer "<<endl;
}
m = max(arr[i], m);
}
return ans;
}
int main()
{
int t;
cin>>t;
for(int test = 1; test <= t; test++)
{
long long int n;
cin>>n;
long long int arr[200000];
//int *arr = new int [n];
for(long long int i = 0; i<n; i++)
{
cin>>arr[i];
}
cout<<endl<<"Case #"<<test<<": "<<record_breaking(arr, n);
//delete [] arr;
}
return 0;
}
Please help me figure out the problem with my solution!
This will pass...
Edge Case:
Input:
1
1
2
Output:
1
but your code is giving 0 as an output...
What's wrong:
You are adding first if statement as (i == 0 && arr[0]>arr[1]) but there is no more than one element... So here first you have to check for this condition (i == n-1 && arr[i] > m)... That means you have to make correct order...
Also, initialize m = -1 Crucial for above edge case...
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int record_breaking(vector<int> arr, int n)
{
int ans = 0;
int m = -1;
for(int i = 0; i<n; i++)
{
//For the last element
if(i == n - 1 && arr[i] > m)
{
ans++;
//cout<<arr[i]<<" is a answer "<<endl;
}
//For first element
else if(i == 0 && arr[0] > arr[1])
{
ans++;
}
//Normal Case
else if(arr[i] > m && arr[i] > arr[i + 1])
{
ans++;
//cout<<arr[i]<<" is a answer "<<endl;
}
m = max(arr[i], m);
}
return ans;
}
int main()
{
int t;
cin>>t;
for(int test = 1; test <= t; test++)
{
int n, temp;
cin>>n;
vector<int> arr;
//long long int arr[200000];
//int *arr = new int [n];
for(int i = 0; i<n; i++)
{
cin>>temp;
arr.push_back(temp);
}
cout<<endl<<"Case #"<<test<<": "<<record_breaking(arr, n);
//delete [] arr;
}
return 0;
}