C++ প্রোগ্রাম একটি সাবয়ারে নেগেট করার পর আমরা পেতে পারি এমন স্বতন্ত্র মানের সংখ্যা খুঁজে বের করতে

ধরুন আমাদের n উপাদান সহ একটি অ্যারে A আছে। আমরা প্রদত্ত সংখ্যার যেকোনো উপসেট নির্বাচন করি এবং এই সংখ্যাগুলিকে অস্বীকার করি। আমরা যে অ্যারে পেতে পারি তাতে আমাদের সর্বাধিক সংখ্যক বিভিন্ন মান খুঁজে বের করতে হবে।

সুতরাং, যদি ইনপুটটি A =[1, 1, 2, 2] এর মত হয় তবে আউটপুট হবে 4, কারণ আমরা অ্যারে [-1, 1, 2, -2] তৈরি করতে প্রথম এবং শেষ সংখ্যাগুলিকে অস্বীকার করতে পারি চারটি ভিন্ন মান।

পদক্ষেপ

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

Define one set se
n := size of A
for initialize i := 0, when i < n, update (increase i by 1), do:
   x := A[i]
   if x is present in se, then:
      insert -x into se
   Otherwise
      insert x into se
return size of se

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

#include <bits/stdc++.h>
using namespace std;

int solve(vector<int> A) {
   set<int> se;
   int n = A.size();
   for (int i = 0; i < n; i++) {
      int x = A[i];
      if (se.count(x))
         se.insert(-x);
      else
         se.insert(x);
   }
   return se.size();
}
int main() {
   vector<int> A = { 1, 1, 2, 2 };
   cout << solve(A) << endl;
}

ইনপুট

{ 1, 1, 2, 2 }