Luke Hobbs and Gangsters

editorial
, , , , ,
1

Luke Hobbs and Gangsters

Given the number of Gangsters that were interrogated N and the answer of each gangster a1,a2…aN . We have to tell minimum number of Gangsters in the town.

Approach:

  1. We can sort the array of a1,a2…aN in increasing/decreasing order.

  2. Start from first gangster having group members K, he can share the gang with only K more members. The moment we encounter K+1’th gangster with a[i] equal to K Or a gangster with a[i] not equal to K, he will be assigned a new Gang and again the 2nd step will be repeated. Each time we encounter the Gangster from new gang the count(of total gangsters in the town) is incremented by a[i]+1.

  3. When no more gangsters are left to be considered. The count will give us number of total gangsters in the town.

complexity:
O(NlogN)

Solution: