Lost pencil#11667
Written by @Yusif_M
In this problem we need to determine the lost pencil's number if all pencils are present then we should return -1. The thing which makes this problem more interesting and challenging than other problems is memory restriction.
To solve this problem we could sum the present pencils' numbers and seperately all pencils together then we subtract and output that number if it was guaranteed that none of input numbers are repeated. But some numbers are repeated and we can't use int array or set to remove repeations because of memory restriction. So we will use boolean array to see if that pencil is lost or not.Then if one of the element of that boolean array is true which means lost we will output it and stop our code and also we will use boolean variable to check if all are present or not if present then we will return -1. Here is the implementation of the idea in C++:
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <bitset>
#include <string>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <unordered_set>
#define ll long long
#define ld long double
#define db double
#define ch char
#define sg string
#define st set
#define stck stack
#define pq priority_queue
#define dq deque
#define vc vector
#define bl bool
#define mp map
#define cp cout.precision
#define ts to_string
#define mst multiset
#define uost unordered_set
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
ll n,num;
bl lost=false,isLost[2000001];
scanf("%lld",&n);
memset(isLost,true,sizeof(isLost)); //all pencils are lost first
for(int i=0;i<n;i++)
{
scanf("%lld",&num);
isLost[num]=false; //we saw that pencil so it is not lost.
}
for(int i=1;i<=n;i++)
{
if(isLost[i]) //if pencil with index i is lost
{
printf("%d",i); //then output it
lost=true; //and we found lost pencil so not all pencils are present
break;
}
}
if(!lost)
{
printf("-1"); //if no absent pencil is found then all are present
}
}