Friend Groups

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 64M

Problem type

Pam is intruiged by the friend groups at her school. At the beginning of the school year, there are N lone students, none of which know each other. A "join" happens when either

  • 2 different lone students or
  • 2 different friend groups or
  • a single lone person and a friend group join together to form a single friend group.

If K such joins occur throughout the school year, how many distinct friend groups will exist at the end of the school year? (Note that a lone person is also considered as a friend group).


1 \le K < N \le 10^5.

Input Specification

Two space-separated integers on one line: N (the initial number of students) and K (the number of joins that occur throughout the year).

Output Specification

One integer: the number of distinct friend groups at the end of the year.

Sample Input

3 2

Output for Sample Input

Explanation for Sample Case

A possible sequence of events is:

Initially, everyone is a lone student: Image 1

Person 1 joins with Person 2: Image 2

Lastly, the [1, 2] friend-group joins with Person 3: Image 3

Since all three of them are in the same friend group, there is 1 friend group that remains.


There are no comments at the moment.