Minimum number of Bottles visible when a bottle can be enclosed inside another Bottle

0 0 3 minutes read

Given N bottles. The i^th bottle has A[i] radius. Once a bottle is enclosed inside another bottle, it ceases to be visible. The task is to minimize the number of visible bottles. You can put the i^th bottle into a j^th bottle if the following condition is fulfilled.

i^th bottle itself is not enclosed in another bottle.
j^th bottle does not enclose any other bottle.
Radius of bottle i is smaller than bottle j ( i.e. A[i] < A[j] ).

Examples:

Input :
8
1 1 2 3 4 5 5 4  
Output :
2
Explanation:
1 -> 2 [1, 2, 3, 4, 5, 5, 4]
2 -> 3 [1, 3, 4, 5, 5, 4]
3 -> 4 [1, 4, 5, 5, 4]
4 -> 5 [1, 5, 5, 4]
1 -> 4 [5, 5, 4]
4 -> 5 [5, 5]

Finally, there are 2 bottles
left which are visible. 
Hence the answer is 2.

Approach: If you carefully observe, you will find that the number of minimum visible bottles will be equal to the maximum number of repeated bottles. Here intuition is, as these repeated bottles cannot be fit in single bigger bottle hence we require at least as many bigger bottles as the number of repeated bottles.
Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
using namespace std;
 
void min_visible_bottles(int* arr, int n)
{
    map<int, int> m;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        m[arr[i]]++;
        ans = max(ans, m[arr[i]]);
    }
 
    cout << "Minimum number of "
         << "Visible Bottles are: "
         << ans << endl;
}
 
// Driver code
int main()
{
    int n = 8;
    int arr[] = { 1, 1, 2, 3, 4, 5, 5, 4 };
 
    // Find the solution
    min_visible_bottles(arr, n);
 
    return 0;
}

Java

// Java code for the above approach
import java.util.*;
 
class GFG 
{
    static void min_visible_bottles(int[] arr, int n)
    {
        HashMap<Integer, 
                Integer> mp = new HashMap<Integer,
                                          Integer>();
        int ans = 0;
        for (int i = 0; i < n; i++) 
        {
            if (mp.containsKey(arr[i]))
            {
                mp.put(arr[i], mp.get(arr[i]) + 1);
            } 
            else
            {
                mp.put(arr[i], 1);
            }
            ans = Math.max(ans, mp.get(arr[i]));
        }
 
        System.out.print("Minimum number of " + 
                      "Visible Bottles are: " + 
                                   ans + "\n");
    }
 
    // Driver code
    public static void main(String[] args) 
    {
        int n = 8;
        int arr[] = { 1, 1, 2, 3, 4, 5, 5, 4 };
 
        // Find the solution
        min_visible_bottles(arr, n);
    }
}
 
// This code is contributed by Rajput-Ji

Python3

# Python3 code for the above approach
def min_visible_bottles(arr, n):
 
    m = dict()
    ans = 0
    for i in range(n):
        m[arr[i]] = m.get(arr[i], 0) + 1
        ans = max(ans, m[arr[i]])
 
    print("Minimum number of",
          "Visible Bottles are: ", ans)
 
# Driver code
n = 8
arr = [1, 1, 2, 3, 4, 5, 5, 4]
 
# Find the solution
min_visible_bottles(arr, n)
 
# This code is contributed 
# by Mohit Kumar

C#

// C# code for the above approach
using System;
using System.Collections.Generic;
 
class GFG 
{
    static void min_visible_bottles(int[] arr, int n)
    {
        Dictionary<int, 
                   int> mp = new Dictionary<int,
                                            int>();
        int ans = 0;
        for (int i = 0; i < n; i++) 
        {
            if (mp.ContainsKey(arr[i]))
            {
                mp[arr[i]] = mp[arr[i]] + 1;
            } 
            else
            {
                mp.Add(arr[i], 1);
            }
            ans = Math.Max(ans, mp[arr[i]]);
        }
 
        Console.Write("Minimum number of " + 
                   "Visible Bottles are: " + 
                                ans + "\n");
    }
 
    // Driver code
    public static void Main(String[] args) 
    {
        int n = 8;
        int []arr = { 1, 1, 2, 3, 4, 5, 5, 4 };
 
        // Find the solution
        min_visible_bottles(arr, n);
    }
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
function min_visible_bottles(arr, n) {
    let m = new Map();
    let ans = 0;
    for (let i = 0; i < n; i++) {
        if(m.has(arr[i])){
            m.set(arr[i], m.get(arr[i]) + 1)
        }else{
            m.set(arr[i], 1)
        }
        ans = Math.max(ans, m.get(arr[i]));
    }
 
    document.write("Minimum number of " + 
    "Visible Bottles are: " + ans + "<br>");
}
 
// Driver code
 
    let n = 8;
    let arr = [1, 1, 2, 3, 4, 5, 5, 4];
 
    // Find the solution
    min_visible_bottles(arr, n);
 
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Output:

Minimum number of Visible Bottles are: 2

Time Complexity: O(nlogn)

Auxiliary Space: O(n)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!