There are N bottles. ith bottle has A[i] radius. Once a bottle is enclosed inside another bottle, it ceases to be visible. Minimize the number of visible bottles.
You can put ith bottle into jth bottle if following condition is fulfilled:
1) ith bottle itself is not enclosed in another bottle.
2) jth bottle does not enclose any other bottle.
3) Radius of bottle i is smaller than bottle j (i.e. A[i] < A[j]).
Constraints
1 <= N <= 100000.
1 <= A[i] <= 10^18.
Input Format
First line contains a single integer N denoting the number of bottles.
Second line contains N space separated integers, ith integer denoting the radius of Ith bottle.
(1 <= i <= N).
Output
Minimum number of visible bottles.
Test Case
Explanation
Example 1
Input
8
1 1 2 3 4 5 5 4
Output
2
Explanation
1st bottle can be kept in 3 rd one 1-->2 , which makes following bottles visible [1,2,3,4,5,5,4]
similarly after following operations, the following will be the corresponding visible bottles
Operation ? Visible Bottles
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 which are visible. Hence, the answer is 2
Answers
Answer:
Explanation:
#include <iostream>
#include <algorithm>
//using namespace std; // <--- Best not to use.
int main()
{
constexpr size_t MAXSIZE{ 20 };
int arrayUsed{};
int numbers[MAXSIZE]{}, unknownUse[MAXSIZE]{}, i{}, count = 0;
std::cout << "\n Needs a prompt!: ";
std::cin >> arrayUsed;
if (arrayUsed >= MAXSIZE)
{
std::cout << "\n Size to large. Must be 20 or less.\n" << std::endl;
std::cout << "\n Needs a prompt!: ";
std::cin >> arrayUsed;
}
std::cout << '\n';
for (i = 0; i < arrayUsed; i++)
{
std::cout << " Enter number " << i + 1 << ": ";
std::cin >> numbers[i];
unknownUse[i] = 1;
}
std::sort(numbers, numbers + arrayUsed);
for (i = 0; i < arrayUsed; i++)
{
for (int j = i + 1; j < arrayUsed; j++)
{
if (numbers[i] < numbers[j] && unknownUse[j] == 1)
{
count = count + 1;
unknownUse[j] = 0;
break;
}
}
}
//int result = arrayUsed - count;
//std::cout << std::endl << result;
std::cout << "\n The result is: " << arrayUsed - count << std::endl; //
return 0; // <--- Not required, but does come in handy. Also a good place for a break point.
Answer
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(ans)
n=int(input())
for i in range(n):
k=int(input())
a=list(map(int,input().split()))
min_visible_bottles(a,k)
Explanation: