परिपत्रक अ‍ॅरेमध्ये सलग फरकांची बेरीज वाढवा


अडचण पातळी सोपे
वारंवार विचारले कॅडन्स इंडिया हा कोड eBay जीई हेल्थकेअर करात Quora एसएपी लॅब स्क्वेअर
अरे लोभी वर्गीकरण

समस्या विधान

समजा आपल्याकडे एक आहे पूर्णांक अॅरे. या अ‍ॅरेला एक मानले पाहिजे परिपत्रक अ‍ॅरे. अ‍ॅरेची शेवटची व्हॅल्यू पहिल्या अ‍ॅरेला जोडली जाईलn ⇒ ए 1. "परिपत्रक अ‍ॅरेमध्ये सलग फरकांची बेरीज वाढवा" ही समस्या प्रत्येक सलग घटकांमधील फरकांची जास्तीत जास्त बेरीज शोधण्यासाठी विचारते. तर आपल्याला सलग घटकांमधील फरक शोधावा लागेल. आपल्याला अ‍ॅरे नंबरची पुनर्रचना करण्याची परवानगी आहे. त्यांच्या भिन्नतेची बेरीज जास्तीत जास्त असावी.

जास्तीत जास्त बेरीज = | ए 1 - ए 2 | + | ए 3 - ए 4 | + | अ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 पूर्णांक. अ‍ॅरेला एक म्हणून समजावे परिपत्रक अ‍ॅरे जे शेवटच्या घटका नंतर थेट प्रथम घटकावर जाऊ शकते. आम्हाला सतत घटकांमधील फरकांची जास्तीत जास्त बेरीज शोधण्यास सांगितले गेले आहे. अ‍ॅरेची पुनर्रचना करण्याचा आम्हाला फायदा आहे. अशा प्रकारे आम्ही फरकांची बेरीज अधिकतम करू शकतो.

येथे आपण अ‍ॅरे दिली आहे. आम्ही प्रत्यक्षात अ‍ॅरेची पुनर्रचना करणार नाही, आम्ही फक्त त्याच्या संख्येसह खेळू शकतो. आता आपण अ‍ॅरेच्या अर्ध्या भागावर जाणार आहोत. हे अ‍ॅरेच्या फक्त एन / 2 लांबीपर्यंत आहे जेथे एन अ‍ॅरेची वास्तविक लांबी आहे. आउटपुट नावाचे व्हेरिएबल घोषित केले आहे. जे अ‍ॅरेचे फरक मिळविते. आणि नंतर त्याचा सारांश आणि आउटपुटमध्ये संचयित करा. परंतु अ‍ॅरे travers करण्यापूर्वी आपण अ‍ॅरेची क्रमवारी लावणार आहोत. आपण अ‍ॅरेची क्रमवारी वाढवित आहोत की ती वाढत्या क्रमाने असावी. नंतर वर्गीकरण अ‍ॅरेमध्ये आपल्यात अ‍ॅरेची सर्वात कमी संख्या असलेल्या अ‍ॅरेच्या सुरूवातीस आहे. Rayरेमधील मोठी संख्या ofरेच्या शेवटी आहे.

आपण अ‍ॅरेची क्रमवारी लावली असल्यामुळे, अ‍ॅरेच्या लांबीच्या अर्ध्या भागापर्यंत केवळ अ‍ॅरेला जाणे आवश्यक आहे. तर आपल्याला अ‍ॅरेच्या वर्तमान मूल्याच्या दुप्पट फरक आणि आउटपुट व्हॅल्यू मिळेल आणि आउटपुटमध्ये संचित करू. यामधे आपल्याला फरक मिळेल आणि नंतर अ‍ॅरेची शेवटची व्हॅल्यू मिळेल, जे त्याचे मूल्य आहे. आणि नंतर आउटपुट व्हॅल्यू जोडा आणि आउटपुटमध्ये संचित करा. अ‍ॅरेची लांबी अर्ध्या होईपर्यंत ही प्रक्रिया चालू ठेवा आणि आउटपुटचे मूल्य परत करा.

कोड

परिपत्रक अ‍ॅरेमध्ये सलग फरकांची बेरीज करण्यासाठी C ++ कोड

#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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन लॉग एन) जेथे “एन” अ‍ॅरे मधील घटकांची संख्या. कारण आपण अ‍ॅरेची क्रमवारी लावली आहे. तर वेळेची जटिलता विलीनीकरण क्रमवारीप्रमाणे बनते. ते वेळेच्या जटिलतेच्या वरच्या बाजूस चिन्हांकित करते.

स्पेस कॉम्प्लेक्सिटी

ओ (1) अतिरिक्त जागेची आवश्यकता नसल्यामुळे. म्हणून अल्गोरिदमद्वारे आवश्यक स्पेस कॉम्प्लेक्सिटी स्थिर असते. परंतु संपूर्ण कार्यक्रमाची अवकाश जटिलता रेषात्मक आहे.