সমস্ত অনন্য ট্রিপল্ট যা একটি প্রদত্ত মান হিসাবে সমষ্টি করে


কাঠিন্য মাত্রা মধ্যম
প্রায়শই জিজ্ঞাসা করা হয় সমষ্টি মর্দানী স্ত্রীলোক ধর্মান্ধদের
বিন্যাস হ্যাশ খোঁজ

আমরা একটি দিয়েছি বিন্যাস পূর্ণসংখ্যা এবং প্রদত্ত সংখ্যার সমষ্টি বলে সমস্যা বিবৃতি প্রদত্ত সংখ্যা 'যোগফল' যোগ করে এমন ট্রিপলটি জানতে জিজ্ঞাসা করে।

উদাহরণ

ইনপুট:

আরআর [] = {3,5,7,5,6,1}

যোগফল = 16

আউটপুট:

(3, 7, 6), (5, 5, 6)

ব্যাখ্যা:

ট্রিপলেট যা প্রদত্ত অঙ্কের সমান.

ইনপুট:

আরআর [] = {3,4,1,5,4}

যোগফল = 20

আউটপুট:

প্রদত্ত সংখ্যাটি দিয়ে গঠিত হতে পারে এমন কোনও ট্রিপল্ট নেই

অ্যালগরিদম

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

ব্যাখ্যা

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

অ্যারে বাছাই করার পরে, নেস্টেড লুপ থেকে শুরু করে, আমরা অ্যারেটিকে দৈর্ঘ্য n-1 পর্যন্ত পার করব। ভেরিয়েবলের মানগুলির একটিকে আই +1 হিসাবে সেট করে অন্য মানটি এন -1 এ সেট করুন। অভ্যন্তরীণ লুপে, আমরা একটি অ্যারের সমস্ত মান অতিক্রম করব এবং প্রদত্ত সংখ্যা 'যোগ' তিনটি বর্তমান অ্যারে উপাদানগুলির যোগফল (আরার [i] + অ্যারে [জে] + অ্যারের [কে] সমান কিনা তা পরীক্ষা করব ]) সমান বা না। যদি শর্তটি সন্তুষ্ট হয় তবে আমরা একটি অ্যারের সমস্ত বর্তমান মান মুদ্রণ করতে যাচ্ছি এবং isFound মানটি সত্য হিসাবে সেট করে দিচ্ছি, এটি নিশ্চিত করে যে আমাদের কোনও মিথ্যা মান ফেরত দেওয়া উচিত নয়।

যদি একটি অ্যারের তিনটি বর্তমান মানের যোগফল প্রদত্ত সংখ্যার সমান না হয়, আমরা এটির জন্য যাচাই করব যে যদি তিনটি বর্তমান উপাদানের যোগফল প্রদত্ত অঙ্কের তুলনায় কম হয়, যদি এটি যোগফলের চেয়ে কম হয়, আমরা মানটি বাড়িয়ে দেব জে এর অর্থ আমাদের বাম পয়েন্টার যা বাম দিক থেকে নির্দেশ করে traversal বৃদ্ধি হয় এবং যদি এই শর্তটিও সন্তুষ্ট না হয় তবে আমরা যোগফলের চেয়ে বড়টি বড় কিনা তা খতিয়ে দেখব, যদি সত্য হয় তবে আমরা কে এর মান হ্রাস করব।

অ্যারের সমস্ত মান ট্র্যাভ্যাস করা না যাওয়া পর্যন্ত এটি চলতে থাকবে। এবং আমরা isFound মানটি ফিরিয়ে আনতে যাচ্ছি, যা সত্য হিসাবে প্রত্যাবর্তিত হতে পারে যদি আমরা কোনও ট্রিপল্ট এবং মিথ্যা খুঁজে পাই তবে আমরা কোনও কিছু খুঁজে পাইনি।

বাস্তবায়ন

সমস্ত অনন্য ট্রিপল্টের জন্য সি ++ প্রোগ্রাম যা একটি প্রদত্ত মানের যোগফল দেয়

#include<iostream>
#include<algorithm>

using namespace std;

int getTripletOfSum(int arr[], int n, int sum)
{
    int i, j, k;
    bool isFound=false;
    sort(arr, arr + n);
    for(i = 0; i < n - 2; i++)
    {
        j = i + 1;
        k = n - 1;

        while(j < k)
        {
            if(arr[i] + arr[j] + arr[k] == sum)
            {
                cout<<"["<<arr[i]<<" "<<arr[j]<<" "<<arr[k]<<"]"<<endl;
                j++;
                k--;
                isFound=true;
            }
            else if(arr[i] + arr[j] + arr[k] > sum)
                k--;
            else
                j++;
        }
    }
    return isFound;
}
int main()
{
    int nums[] = {3,5,7,5,6,1};
    int n = sizeof(nums) / sizeof(nums[0]);
    int sum = 16;
    if(!getTripletOfSum(nums, n, sum))
        cout << "There are no triplets that can be formed with the given number";

    return 0;
}
[3 6 7]
[5 5 6]

সমস্ত অনন্য ট্রিপল্টের জন্য জাভা প্রোগ্রাম যা একটি প্রদত্ত মান হিসাবে সমষ্টি করে

import java.util.Arrays;

public class TripletsWithSum
{
    public static boolean getTripletOfSum(int arr[], int sum)
    {
        Arrays.sort(arr);

        boolean isFound=false;

        for (int i = 0; i < arr.length - 2; i++)
        {
            int j = i + 1;
            int k = arr.length - 1;
            while (j < k)
            {
                if (arr[i] + arr[j] + arr[k] == sum)
                {
                    System.out.println("["+arr[i] + " " + arr[j] +" " +arr[k]+"]");
                    j++;
                    k--;
                    isFound=true;
                }
                else if (arr[i] + arr[j] + arr[k] < sum)
                    j++;

                else
                    k--;
            }
        }
        return isFound;
    }
    public static void main(String[] args)
    {
        int arr[] = {3,5,7,5,6,1};
        int sum = 16;
        if (!getTripletOfSum(arr, sum))
        {
            System.out.println("There are no triplets that can be formed with the given number");
        }
    }
}
[3 6 7]
[5 5 6]

সমস্ত অনন্য ট্রিপল্টের জন্য জটিলতা বিশ্লেষণ যা একটি প্রদত্ত মানের সমষ্টি

সময় জটিলতা

চালু2কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

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

উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।