fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. //Using BST to find distinct elements in an array
  6. // We store the array elements in BST and then count the number of nodes in BST as these will be the only distinct elements
  7. // The time complexity to insert all array elements in BST is O(nlogn) on avg and O(n_square) in worst case
  8. // The time complexity to count nodes in bst is O(logn) for a balanced tree and O(n_square) if sorted array.
  9. class TreeNode {
  10. public:
  11.     int data;
  12.     TreeNode* left;
  13.     TreeNode* right;
  14.  
  15.     TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
  16. };
  17.  
  18. class BST {
  19. private:
  20.     TreeNode* root;
  21.     // Recursive function to insert a value into the BST
  22.     TreeNode* insert(TreeNode* node, int value) {
  23.         if (node == nullptr) {
  24.             return new TreeNode(value);
  25.         }
  26.  
  27.         if (value < node->data) {
  28.             node->left = insert(node->left, value);
  29.         } else if (value > node->data) {
  30.             node->right = insert(node->right, value);
  31.         }
  32.  
  33.         return node;
  34.     }
  35.  
  36.     // Recursive function to count the number of nodes in the BST
  37.     int countNodes(TreeNode* node) {
  38.         if (node == nullptr) {
  39.             return 0;
  40.         }
  41.         return 1 + countNodes(node->left) + countNodes(node->right);
  42.     }
  43.  
  44. public:
  45.     BST() : root(nullptr) {}
  46.  
  47.     void insert(int value) {
  48.         root = insert(root, value);
  49.     }
  50.  
  51.     int countDistinct() {
  52.         return countNodes(root);
  53.     }
  54. };
  55.  
  56. // Function to classify the array based on the number of distinct elements
  57. string classifyArray(int N, int X, int A[]) {
  58.     BST bst;
  59.  
  60.     for (int i = 0; i < N; ++i) {
  61.         bst.insert(A[i]);
  62.     }
  63.  
  64.     int distinctCount = bst.countDistinct();
  65.     // Compareing the count of distinct elements with the expected count and classifying the array accordingly
  66.     if (distinctCount == X)
  67.         return "Good";
  68.     else if (distinctCount < X)
  69.         return "Bad";
  70.     else
  71.         return "Average";
  72. }
  73.  
  74. int main() {
  75.     int T;
  76.     cin >> T;
  77.  
  78.     for (int t = 0; t < T; ++t) {
  79.         int N, X;
  80.         cin >> N >> X;
  81.  
  82.         int A[N];
  83.         for (int i = 0; i < N; ++i) {
  84.             cin >> A[i];
  85.         }
  86.  
  87.         cout << classifyArray(N, X, A) << endl;
  88.     }
  89.  
  90.     return 0;
  91. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
4
4 1
1 4 2 5
4 2
4 2 1 5
4 3
5 2 4 1
4 4
1 2 4 5
stdout
copy 
Average
Average
Average
Good
https://ideone.com/FMBKud
language:
C++ 4.3.2 (gcc-4.3.2)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!