The Captain's Room | Hackerrank Problem Solution With Explanation

Problem Statement

Mr. Anant Asankhya is the manager at the INFINITE hotel. The hotel has an infinite amount of rooms.

One fine day, a finite number of tourists come to stay at the hotel.
The tourists consist of:
→ A Captain.
→ An unknown group of families consisting of members per group where K ≠ 1.

The Captain was given a separate room, and the rest were given one room per group.

Mr. Anant has an unordered list of randomly arranged room entries. The list consists of the room numbers for all of the tourists. The room numbers will appear K times per group except for the Captain's room.

Mr. Anant needs you to help him find the Captain's room number.
The total number of tourists or the total number of groups of families is not known to you.
You only know the value of K and the room number list.

Input Format
The first line consists of an integer, K, the size of each group.
The second line contains the unordered elements of the room number list.

Output Format
Output the Captain's room number.

Sample Input
5
1 2 3 6 5 4 4 2 5 3 6 1 6 5 3 2 4 1 2 5 1 4 3 6 8 4 3 1 5 6 2

Sample Output
8

Link to question: https://www.hackerrank.com/challenges/py-the-captains-room/problem

Solution (Python3)

if __name__ == '__main__':
    k = int(input())
    rooms = list(map(int, input().split()))
    roomSet = set(rooms)
    roomSum = sum(rooms)
    roomSetSum = sum(roomSet) * k
    captiansRoom = (roomSetSum - roomSum) // (k - 1)
    print(captiansRoom)

Explanation

The logic behind this is simple mathematics. If all the unique elements were present in the array K times then their sum would have been sum of unique elements mutliplied K times. But there is one unique element that is present only one time. So the roomSetSum variable's value will be more than the actual sum of elements of the given array, let's say it x.

If we see it from a different angle then we will find that our desired element, let's say it z is present only one time but is missing k-1 times from the array. So we can conclude that x is nothing but z multiplied by k-1. Now all we've to do is to do reverse engineering and just find the x (that is the difference between the sum of all the elements of rooms array if it contained all the unique elements exactly k times and actual sum of all the elements of the rooms array, i.e. the array that contains all the elements k times but a single element only one time) and divide it with k-1 and voila! We got the answer.