Bottle Necks – TCS CodeVita

Find the minimum number of visible bottles after optimally nesting smaller bottles inside larger ones.

Understand the Problem

Problem Statement

The program must accept the radii of N bottles as the input. Once a bottle is enclosed inside another bottle, it ceases to be visible. A bottle X is enclosed inside another bottle Y only if the following conditions are fulfilled.
1) The bottle X itself is not enclosed in another bottle.
2) The bottle Y does not enclose any other bottle.
3) The radius of the bottle X is smaller than bottle Y.
The program must print the minimum number of visible bottles based on the given conditions.

Note: Optimize your logic to avoid Time Limit Exceed error.

Constraints

1 <= N <= 10^5
1 <= Radius of each bottle <= 10^18

Examples

Example 1

Input

8
2 3 1 1 4 5 5 3

Output

Explanation

We can nest bottles as follows: 1->2->3->4->5 and 1->3->5. The maximum frequency is 2 (for radius 1 and 5), so the minimum visible bottles is 2.

Example 2

Input

11
1 1 5 5 6 7 8 2 3 4 5

Output

Explanation

We can nest bottles as follows: 1->2->3->4->5->6->7->8, 1->5, and one standalone 5. The maximum frequency is 3 (for radius 5), so the minimum visible bottles is 3.

Solution

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    long long x = *(long long*)a;
    long long y = *(long long*)b;
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

int main() {
    int n;
    scanf("%d", &n);
    
    long long *radii = (long long*)malloc(n * sizeof(long long));
    for (int i = 0; i < n; i++) {
        scanf("%lld", &radii[i]);
    }
    
    qsort(radii, n, sizeof(long long), compare);
    
    int maxFreq = 1;
    int currentFreq = 1;
    
    for (int i = 1; i < n; i++) {
        if (radii[i] == radii[i-1]) {
            currentFreq++;
            if (currentFreq > maxFreq) {
                maxFreq = currentFreq;
            }
        } else {
            currentFreq = 1;
        }
    }
    
    printf("%d\n", maxFreq);
    free(radii);
    return 0;
}

Time:O(N log N) - dominated by the sorting operation

Space:O(N) - for storing the radii array

Approach:

1. Read the number of bottles and their radii into an array.
2. Sort the array using qsort to group identical radii together.
3. Iterate through the sorted array, counting consecutive occurrences of the same radius.
4. Track the maximum frequency encountered.
5. The maximum frequency is the answer, as it represents the minimum number of visible bottles.

Visual Explanation

Loading diagram...

All Problems