PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Abhinav Sharma, Manan Grover
Editorialist: Lavish Gupta
DIFFICULTY:
Simple
PREREQUISITES:
Loops
PROBLEM:
A particular month has 30 days, numbered from 1 to 30.
Day 1 is a Monday, and the usual 7-day week is followed (so day 2 is Tuesday, day 3 is Wednesday, and so on).
Every Saturday and Sunday is a holiday. There are N festival days, which are also holidays. Note that it is possible for a festival day to occur on a Saturday or Sunday.
You are given the dates of the festivals. Determine the total number of holidays in this month.
EXPLANATION:
We can have an array holiday of length 30, where holiday[i] is 1 if it is a holiday on i^{th} day, and 0 otherwise.
Because Day 1 is a Monday, we have Saturday on Day 6, 13, 20, 27. Similarly, we have Sunday on Day 7, 14, 21, 28.
We can also take the N holidays from the input, and mark the respective dates as 1 in the holiday. Finally, we need to count the total number of holidays using this array.
Note that a concise way to represent a Saturday is - i^{th} day is a Saturday if i\%7 = 6, where \% denotes the modulus sign.
Similarly, i^{th} day is a Sunday if i\%7 = 0
TIME COMPLEXITY:
O(N + 30) for each test case.
SOLUTION:
Editorialist's Solution
#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll ,ll>
using namespace std ;
const ll z = 998244353 ;
int main()
{
int t ;
cin >> t ;
while(t--)
{
int n ;
cin >> n ;
vector<int> holiday(31) ;
for(int i = 1 ; i <= 30 ; i++)
{
if(i%7 == 0 || i%7 == 6)
holiday[i] = 1 ;
}
for(int i = 0 ; i < n ; i++)
{
int u ;
cin >> u ;
holiday[u] = 1 ;
}
int ans = 0 ;
for(int i = 1 ; i <= 30 ; i++)
ans += holiday[i] ;
cout << ans << endl ;
}
return 0;
}