একটি বৃত্তাকার অ্যারে একটানা পার্থক্য যোগফল


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় ক্যাডেন্স ইন্ডিয়া ইবে জিই হেলথকেয়ার ক্যারাট Quora এসএপি ল্যাব বর্গক্ষেত্র
বিন্যাস লোভী শ্রেণীবিভাজন

সমস্যা বিবৃতি

মনে করুন আপনার একটি আছে পূর্ণসংখ্যা বিন্যাস। এই অ্যারেটিকে একটি হিসাবে বিবেচনা করা উচিত বিজ্ঞপ্তি অ্যারে। একটি অ্যারের শেষ মানটি প্রথম অ্যারের সাথে সংযুক্ত হবে, কn ⇒ এ 1। সমস্যাটি "একটি বৃত্তাকার অ্যারেতে ধারাবাহিক পার্থক্যের পরিমাণকে সর্বাধিক করে তোলা" প্রতিটি পরপর উপাদানগুলির মধ্যে পার্থক্যের সর্বাধিক যোগফলটি জানতে চাইতে। সুতরাং আপনি একটি পরপর উপাদান মধ্যে পার্থক্য খুঁজে পেতে হবে। আপনাকে অ্যারে নম্বরগুলি পুনরায় সাজানোর অনুমতি দেওয়া হয়েছে। তাদের পার্থক্যের যোগফল সর্বাধিক হওয়া উচিত।

সর্বাধিক যোগ = | a1 - a2 | + | a3 - a4 | + | কn-1 - কn | + | কn - এ 1 |

উদাহরণ

arr[]={9, 8, 4, 2}
22

ব্যাখ্যা

আমরা প্রদত্ত অ্যারে 9, 2, 8, 4 হিসাবে ব্যবস্থা করতে পারি তবে তা দেবে

| 9 - 2 | + | 2 - 8 | + | 8 - 4 | + | 4 - 9 | = 22

একটি বৃত্তাকার অ্যারে একটানা পার্থক্য যোগফল

অ্যালগরিদম

1. Set a variable output to 0.
2. Sort the given array.
3. Traverse up to n/2 length of the array(n is the length of the array).
    1. Sum up the value of output and array’s last values and store it to sum.
    2. Get the difference of output and twice of array’s starting value and store it to the output.
4. Return the value of output.

ব্যাখ্যা

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

এখানে আমরা একটি অ্যারে দিয়েছি। আমরা আসলে অ্যারে পুনর্বিন্যাস করতে যাচ্ছি না, আমরা কেবল এটির সংখ্যা নিয়ে খেলতে পারি। এখন আমরা অ্যারের অর্ধেকটি পেরোতে যাচ্ছি। এটি অ্যারের কেবলমাত্র n / 2 দৈর্ঘ্য পর্যন্ত যেখানে n অ্যারের প্রকৃত দৈর্ঘ্য। আমরা আউটপুট নামক একটি ভেরিয়েবল ঘোষণা করেছি। যা অ্যারের পার্থক্য পেতে চলেছে। এবং তারপরে যোগফলটি আউটপুট থেকে সঞ্চয় করুন। তবে অ্যারেটি ট্র্যাভার করার আগে আমরা অ্যারে বাছাই করতে যাচ্ছি। আমরা অ্যারে বাছাই করতে যাচ্ছি যাতে এটি ক্রমবর্ধমান ক্রম হওয়া উচিত। পরে শ্রেণীবিভাজন অ্যারেতে অ্যারেতে আমরা সবচেয়ে কম নম্বর পেয়েছি অ্যারের শুরুতে। আর অ্যারেতে বৃহত্তর সংখ্যাটি অ্যারের শেষে হয়।

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

কোড

একটি বৃত্তাকার অ্যারেতে ধারাবাহিক পার্থক্যের যোগফলকে সি ++ কোড

#include<iostream>
#include<algorithm>

using namespace std;

int getMaxDiff(int arr[], int n)
{
    int output = 0;

    sort(arr, arr + n);

    for (int i = 0; i < n/2; i++)
    {
        output -= (2 * arr[i]);
        output += (2 * arr[n - i - 1]);
    }

    return output;
}
int main()
{
    int arr[] = { 9, 8, 2, 4 };
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << getMaxDiff(arr, n) << endl;
    return 0;
}
22

একটি বৃত্তাকার অ্যারেতে ধারাবাহিক পার্থক্যের যোগফলকে জাভা কোড

import java.util.Arrays;

class maximumDiff
{
    public static int getMaxDiff(int arr[], int n)
    {
        int output = 0;

        Arrays.sort(arr);

        for (int i = 0; i < n/2; i++)
        {
            output -= (2 * arr[i]);
            output += (2 * arr[n - i - 1]);
        }

        return output;
    }
    public static void main (String[] args)
    {
        int arr[] = {9, 8, 2, 4 };
        int n = arr.length;
        System.out.println(getMaxDiff(arr, n));
    }
}
22

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

সময় জটিলতা

ও (এন লগ এন) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা। কারণ আমরা অ্যারে বাছাই করেছি। সুতরাং সময় জটিলতা মার্জ সাজানোর মতো হয়ে যায়। যেহেতু সময়ের জটিলতার উপরের সীমা চিহ্নিত করে।

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

ও (1) কোন অতিরিক্ত স্থান প্রয়োজন হিসাবে। সুতরাং অ্যালগরিদমের দ্বারা প্রয়োজনীয় স্থান জটিলতা ধ্রুবক। তবে পুরো প্রোগ্রামটির স্পেস জটিলতা লিনিয়ার।