সাজানো অ্যারেতে সমস্ত ট্রিপল্ট মুদ্রণ করুন যা এপি গঠন করে form  


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় Accenture সমষ্টি ক্যাডেন্স ইন্ডিয়া গুগল তথ্যপ্রযুক্তি যুক্তি তর্ক পিন্টারেস্ট
বিন্যাস কাটা খোঁজ

সমস্যা "এপি রূপে সাজানো অ্যারেতে সমস্ত ট্রিপল্ট মুদ্রণ করুন" বলে যে আমরা একটি বাছাই করেছি পূর্ণসংখ্যা অ্যারে। কাজটি হ'ল সমস্ত সম্ভাব্য ট্রিপল্টগুলি সন্ধান করা যা পাটিগণিত অগ্রগতি গঠন করতে পারে।

সাজানো অ্যারেতে সমস্ত ট্রিপল্ট মুদ্রণ করুন যা এপি গঠন করে form

উদাহরণ  

arr[] = {1,3,5,7,8,12,15,16,20,30}
(1, 3, 5), (3, 5, 7), (1, 8, 15), (8, 12, 16), (12, 16, 20)

ব্যাখ্যা

এগুলি হ'ল ট্রিপল্ট যা এপি গঠন করে

arr[] = {2,4,5,6,9,14,18,24}
(2, 4, 6), (4, 5, 6), (4, 9, 14), (4, 14, 24)

ব্যাখ্যা

এগুলি হ'ল ট্রিপল্ট যা এপি গঠন করে

অ্যালগরিদম  

  1. থেকে লুপ i = 1 থেকে n-1(অন্তর্ভুক্ত না).
  2. J এর মান i এর চেয়ে কম এবং k এর মান i এর চেয়ে আরও একটিতে সেট করুন।
  3. যদিও j> = 0 && কে <এন.
    1. দুটি বর্তমান অ্যারে উপাদানের যোগফল অন্যান্য অ্যারের উপাদানের দ্বিগুণ কিনা তা পরীক্ষা করে দেখুন,
      1. যদি সত্য হয় তবে বর্তমানের তিনটি উপাদান মুদ্রণ করুন এবং যথাক্রমে কে এবং জ এর মান হ্রাস এবং বৃদ্ধি করুন।
    2. দুটি উপাদানের যোগফল অন্য উপাদানের দ্বিগুণের চেয়ে কম কিনা তা পরীক্ষা করে দেখুন, তারপরে কে দ্বারা 1 বাড়ান।
    3. দুটি উপাদানের যোগফল অন্য উপাদানের দ্বিগুণ চেয়ে বেশি কিনা তা পরীক্ষা করে দেখুন, তারপরে, 1 দ্বারা j হ্রাস করুন।

ব্যাখ্যা

আমরা একটি দিয়েছি সাজানো বিন্যাস। আমাদের কাছে সমস্ত ট্রিপলগুলি অনুসন্ধান করতে বলা হয়েছে যা পাটিগণিতের অগ্রগতি তৈরি করতে পারে। একটি গাণিতিক অগ্রগতি একটি সংখ্যার ক্রম হিসাবে সংজ্ঞায়িত করা যেতে পারে যেখানে সমস্ত উপাদান ক্রমাগতভাবে পুরো ক্রম বরাবর তাদের মধ্যে একটি নির্দিষ্ট দূরত্ব নিয়ে আসে। আমরা একটি এপি'র সূত্রে ট্রিপলেটটি খুঁজে পাব যা একটি + সি = 2 বি বলেছে যে দুটি সংখ্যার যোগফল যদি তৃতীয় সংখ্যার দ্বিগুণ হয়।

আরো দেখুন
ধাপের যোগ লেটকোড সমাধানের মাধ্যমে ধনাত্মক পদক্ষেপ পেতে সর্বনিম্ন মান

লুপের জন্য একটি দিয়ে পুরো অ্যারেটি অতিক্রম করুন এবং এ লুপ করার সময়, 'যখন লুপ' পরীক্ষা করতে চলেছে আমরা তিনটি উপাদানকে এপি গঠন করতে পারি কিনা তা পরীক্ষা করতে যাচ্ছি। আমরা যখনই লুপটির মধ্য দিয়ে যাব তখনই আমি j এর মান i এর মানের চেয়ে কম এবং কে এর মানকে i এর মানের চেয়ে এক থেকে কম সেট করব। এটি আমাদের চেক করার জন্য একটি উপাদান বাছাই করবে, সুতরাং প্রতিবার যখন আমাদের কাছে আরআর চেক করার জন্য তিনটি উপাদান থাকে [i], আরার [জে], এবং আরার [কে], আই, জে এবং কে এর মান যে প্রতিটিের জন্য আলাদা হবে লুপ জন্য বা মধ্যে কিনা তা traversal লুপ করার সময়.

যদি আমরা দেখতে পেলাম যে দুটি উপাদানের যোগফল তৃতীয় উপাদানের সমান, আমরা এই তিনটি অ্যারে উপাদান মুদ্রণ করতে যাচ্ছি, তারা একটি এপি গঠন করতে পারে। আমরা আমাদের অ্যালগরিদম অনুযায়ী জে এবং কে এর মান আপডেট করব। আমরা যদি তৃতীয় উপাদানের দ্বিগুণের চেয়ে কম দুটি উপাদানের যোগফল পাই। আমরা কে এর মান বাড়িয়ে দেব, বা যদি তৃতীয় উপাদানের দ্বিগুণের চেয়ে বড় যোগফল পাই, তবে আমরা j এর মান হ্রাস করব। এটি অব্যাহত থাকবে যতক্ষণ না আমরা পুরো অ্যারেটি অতিক্রম করি এবং সম্ভাব্য সমস্ত উপাদানগুলি খুঁজে বের করি যা এপি গঠন করতে পারে।

কোড  

সাজানো অ্যারেতে সমস্ত ট্রিপল্ট মুদ্রণ করতে সি ++ কোড যা এপি রূপান্তর করে

#include<iostream>

using namespace std;

void getTripletsWithAP(int arr[], int n)
{
  for (int i = 1; i < n - 1; i++)
  {
    int j = i - 1, k = i + 1;
        while(j >= 0 && k < n)
        {
            if (arr[j] + arr[k] == 2 * arr[i])
            {
        cout <<arr[j]<< " "<<arr[i]<<" "<<arr[k]<< endl;
                k++;
                j--;
            }
            else if (arr[j] + arr[k] < 2 * arr[i])
                k++;
            else
                j--;
        }
  }
}
int main()
{
  int arr[] = {1,3,5,7,8,12,15,16,20,30};
  int n = sizeof(arr) / sizeof(arr[0]);
  getTripletsWithAP(arr, n);
  return 0;
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

বাছাই করা অ্যারেতে সমস্ত ট্রিপল্ট মুদ্রণ করতে জাভা কোড যা এপি গঠন করে

class TripletAP
{
    public static void getTripletsWithAP(int arr[], int n)
    {
        for (int i = 1; i < n - 1; i++)
        {
            int j = i - 1, k = i + 1;
            while(j >= 0 && k < n)
            {
                if (arr[j] + arr[k] == 2 * arr[i])
                {
                    System.out.println(arr[j] +" " +arr[i]+ " " + arr[k]);
                    k++;
                    j--;
                }
                else if (arr[j] + arr[k] < 2 * arr[i])
                    k++;
                else
                    j--;
            }
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {1,3,5,7,8,12,15,16,20,30};
        int n = arr.length;
        getTripletsWithAP(arr, n);
    }
}
1 3 5
3 5 7
1 8 15
8 12 16
12 16 20

জটিলতা বিশ্লেষণ  

সময় জটিলতা

চালু2কোথায় "এন"  অ্যারেতে উপাদানগুলির সংখ্যা। কারণ আমাদের দুটি নেস্টেড লুপ রয়েছে যেখানে প্রথম লুপটি শেষ অবধি পৌঁছে যাওয়া পর্যন্ত চালিত হয় এবং তারপরে দ্বিতীয় নেস্টেড লুপটি এপি এর উপাদানগুলি খুঁজতে ব্যবহৃত হয়।

আরো দেখুন
সর্বাধিক আকারের subarray যোগফল কে

স্পেস জটিলতা ity

ও (1) কোন অতিরিক্ত স্থান প্রয়োজন হিসাবে।