Number of Unique Categories

Problem Statement

In this problem, you are provided with an integer n and an object categoryHandler from the class CategoryHandler. The integer n represents the number of elements which are sequentially numbered from 0 to n - 1. Each of these elements is assigned a category. Your main objective is to determine the count of unique categories among these elements.

The CategoryHandler class includes a pivotal function, haveSameCategory(integer a, integer b), which can assist in solving the problem. This function outputs true if the elements a and b belong to the same category. Conversely, it outputs false if they belong to different categories or if any of the indices a or b is outside the valid range (less than 0 or greater than or equal to n).

Your task is to utilize this function effectively to ascertain the total number of unique categories among the n elements.

Examples

Example 1

Input:

n = 6, categoryHandler = [1,1,2,2,3,3]

Output:

3

Explanation:

There are 6 elements in this example. The first two elements belong to category 1, the second two belong to category 2, and the last two elements belong to category 3. So there are 3 unique categories.

Example 2

Input:

n = 5, categoryHandler = [1,2,3,4,5]

Output:

5

Explanation:

There are 5 elements in this example. Each element belongs to a unique category. So there are 5 unique categories.

Example 3

Input:

n = 3, categoryHandler = [1,1,1]

Output:

1

Explanation:

There are 3 elements in this example. All of them belong to one category. So there is only 1 unique category.

Constraints

• 1 <= n <= 100

Approach and Intuition

Given the unique functionality defined in the CategoryHandler class, the primary task is to leverage the haveSameCategory function to group elements into categories and then count these groups. Here’s a structured way to approach this:

1. Initialization: Start by initializing a data structure to keep track of which elements have been visited and categorized. A simple list or array can be used for this purpose.

2. Categorization Process: Iterate over each element from 0 to n - 1. For each element, if it has already been categorized in a previous step, skip to the next element. If not, initiate a new category starting from this element.

3. Identifying Same Category Members: Use a nested loop to compare the current element with all other elements using the haveSameCategory function. For each pair that returns true, mark them as part of the same category in the data structure initialized in step 1.

4. Counting Unique Categories: Each time a new category is initiated and processed, increment a count. This count at the end of the loops will represent the number of unique categories.

By following this structured approach, every element is checked, categorized properly based on the similarity function provided, and all unique categories are counted efficiently.

Solutions

class Solution {
public:
    int countDistinctCategories(int totalNum, CategoryHandler* handler) {
        int distinctCounts = totalNum;
            
        // Loop through all elements and combine if they share a category
        for (int index = 0; index < totalNum; index++) {
            for (int compareIndex = index - 1; compareIndex >= 0; compareIndex--) {
                if (handler->haveSameCategory(index, compareIndex)) {
                    distinctCounts--;
                    break;
                }
            }
        }
            
        return distinctCounts;
    }
};

class Solution {
    public int countCategories(int totalElements, CategoryHandler handler) {
        int count = totalElements;
            
        // Loop through all pairs and decrement count for pairs in the same category.
        for (int idx1 = 0; idx1 < totalElements; idx1++) {
            for (int idx2 = idx1 - 1; idx2 >= 0; idx2--) {
                if (handler.haveSameCategory(idx1, idx2)) {
                    count--;
                    break;
                }
            }
        }
            
        return count;
    }
}