YULESIT - Editorial

editorial
, , ,
1

Problem Link:

https://www.codechef.com/CDSO2016/problems/YULESIT

Difficulty:

Medium

Pre-requisites:

Data structures

Problem:

It’s the time of YULE BALL! All students of Hogwarts are ready with their dates but someone is too lonesome. One person has sneaked in alone and Filch is desperate to find out this person. Even though you might not want to help him spoil someone’s party, you must! Each invite (one per couple) has been assigned a unique identification number. Everybody showed their invites and we have the list of invites accepted. Tell us the invite of the lonesome student.

Quick Explanation:

The solution involves two iterators. With the first iterator, we walk the list of integers. For each integer, we can use the second integer to scan the same list and try to find another instance of this integer at a different index. If the second iterator reaches the end of the list, then the index of the first iterator is the solution.

Explanation:

We use a data structure with efficient search operations. As we step through the list of integers, we take each value and see if it is already present in our data structure. If so, we remove it from the structure and if not we store the element in the structure. According to the problem statement, only one item will remain in our data structure at the end of the iteration. This solution depends on the efficiency of our side data structure, but if we use a hash based structure with constant time add/seek/remove operates it will run as O(n). In pseudocode:

Map<Integer, Integer> map = new HashMap();

for (int i=1; i<=num_guests; i++)

{

if (map.containsKey(guests[i]))

{

map.containsKey(guests[i]) ? map.remove(guests[i])

    : map.put(guests[i],i);

}

return map.values()[0];

Alternative Solution:

Simply start with a memory space bigger than the largest integer we expect to encounter and perform a bitwise XOR of each integer into the space. This will yield a linear (O(n)) runtime without any appreciable memory consumption. In C++:

for (int g = 0; g < num_guests; ++g)

{

  int id;

  cin >> id;

  solution = solution ^ id;

}

cout<<test<<’\t’<<solution;