PROBLEM LINK:
Setter: Vatsal Sanchala
Tester: Aishwarya K
Editorialist: Gaurish Baliga
DIFFICULTY
Easy
PREREQUISITES:
None.
PROBLEM
In the Wonderous School of Moon, the Logic Exam is scheduled today. The school belongs to Royal Family and hence has some weird yet interesting rules.
In the exam classroom, the students start sitting in random order with starting roll number X and the capacity of the classroom is Y. Now teacher takes attendance and finds out that one student is missing, Let’s assume his roll number to be K.
Now she makes the students stand up which are present at multiples of K^{th} position and snatches paper from them. After this process is completed, the teacher gives their papers except for the one who has the smallest roll number out of the students who are standing.
Hence, you task is to decode the roll number of who won’t get the paper back. If there are no such students, print -1.
EXPLANATION
For this problem, you are expected to find the missing element in the range X to X + Y. This could be found in many ways:
-
Use a map to store which elements are present.
-
Sum of numbers X to X + Y - Sum of elements in the array.
After doing this, we just need to check if K is in the range 1 to Y. If yes print the smallest element by iterating through multiples of k. Else print -1.
Time Complexity:
O(N) per testcase.
SOLUTION
Setter's Solution
#include<iostream>
using namespace std;
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t;
cin>>t;
while (t--) {
long long x, y, sum=0, res;
cin>>x>>y;
long long a[y], j=0;
for (int i=0; i<y; ++i) {cin>>a[i]; sum+=a[i];}
long long miss=(((x+y)*(x+y+1))/2)-(((x-1)*x)/2)-sum;
if (miss>=y) res=-1;
else {res=a[miss-1]; j+=miss-1;}
while (j<y) {
if (a[j]<res) res=a[j];
j+=miss;
}
cout<<res<<"\n";
}
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
// your code goes here
int t;
cin >> t;
while(t--)
{
int x,y;
cin >> x >> y;
int arr[y];
set <int> s1;
int ans;
for(int i=0;i<y;i++)
{
cin >> arr[i];
s1.insert(arr[i]);
}
int sz = s1.size();
for(int i=x;i<=x+y;i++)
{
s1.insert(i);
if(sz!=s1.size())
{
ans = i;
//cout << "ans: " <<ans << ", ";
break;
}
}
int p=INT_MAX;
for(int i=ans-1;i<y;i=i+ans)
{
//cout << arr[i] <<" ";
p = min(p,arr[i]);
}
if(p==INT_MAX)
{
cout << "-1" << endl;
}
else
{
cout<< p << endl;
}
}
return 0;
}