दो लगातार बराबर मूल्यों को एक से अधिक के साथ बदलें


कठिनाई स्तर आसान
में अक्सर पूछा एक्सेंचर गढ़ स्वतंत्र प्रभार पेपैल चौकोर Teradata
ऐरे

समस्या का विवरण

मान लीजिए कि आपके पास पूर्णांक है सरणी। समस्या "दो लगातार समान मूल्यों को एक से अधिक के साथ बदलें" उन सभी जोड़ी मूल्यों को बदलने के लिए कहती है जो 'ए' कहती हैं, जो लगातार "एक + 1" 1 उनसे अधिक (दो लगातार संख्या) आती हैं, जैसे कि संशोधन के बाद भी या पुनरावृत्ति कोई नई लगातार जोड़ी शेष नहीं होगी।

उदाहरण

arr[]={5, 2, 1, 1, 2, 2}
5 4

व्याख्या

चूंकि 1 एक निरंतर संख्या है, जिसका अर्थ है कि इसका मतलब 2 से अधिक है और गिरफ्तारी {5,2,2,2,2} हो जाएगी

अब 2 एक निरंतर संख्या है, इसलिए इसे संख्या से बड़ा कर दिया जाएगा अर्थात 3 और गिरफ्तारी {5,3,2,2} हो जाएगी

फिर 2 एक निरंतर संख्या है इसलिए 3 से बदल दिया जाएगा और गिरफ्तारी {5,3,3} हो जाएगी

अब 3 लगातार संख्या है इसलिए 4 से बदल दिया जाएगा और गिरफ्तारी {5,4} हो जाएगी

arr[]={2,5,5,6,2,7,7}
2 7 2 8

व्याख्या

चूंकि 5 एक निरंतर संख्या है, जिसका अर्थ 1 से अधिक है, जिसका अर्थ है कि 6. तो गिरफ्तारी गिरफ्तारी की तरह दिखाई देगी [] = {2,6,6,2,7,7}

उसके स्थान पर 6 आते हैं लेकिन अगली संख्या भी 6 है, इसलिए इसे भी 1 से अधिक मान 6 से बदल दिया जाता है, 7 का अर्थ है और गिरफ्तारी {2,7,2,7,7} हो जाएगी

जैसा कि 7 भी अंतिम समय में होता है, इसलिए इसे 8 से बदल दिया जाता है और गिरफ्तारी {2,7,2,8} हो जाएगी

कलन विधि

1. Set the position’s value to 0.
2. Traverse the array from o to n(n is the length of the array).
  1. Copy the value of arr[i] to arr[position] and increase the value of the position by 1.
  2. While the position is greater than 1, its previous two values are equal or not.
    1. Decrease the value of a position by 1,
    2. and increase the value of arr[position -1] by 1.
3. Print the array from index 0 to position.

व्याख्या

हमने ए सरणी of पूर्णांकों। हमने उन सभी मूल्यों को प्रतिस्थापित करने के लिए कहा है जो संख्या 1 से अधिक संख्या के साथ लगातार आते हैं। यदि 4 लगातार सरणियों में आते हैं, तो इसे मान 5 से बदल दिया जाएगा। यह संख्या 1 से 4 अधिक है। अब एक ट्रैवर्सल के साथ, हम केवल एक संशोधन कर सकते हैं। मान लीजिए, 3 संख्याएँ मौजूद हैं 4, 4, 5. तब हम 4, 4 से 5 परिवर्तित करेंगे और फिर 5 भी एक संख्या है। क्योंकि इसकी अगली संख्या स्वयं संख्या के समान है। तो हम नेस्टेड लूप का उपयोग करके ऐसा करेंगे।

सरणी को 0 से n तक पार करें। एक लूप खोलें, ताकि यह नेस्टेड लूप बन जाए। बाहरी लूप के साथ, हम ट्रैवर्सल्स को संभालेंगे। और आंतरिक लूप के साथ, हम दिए गए शर्त के अनुसार मूल्यों को अद्यतन करने या मानों को बदलने जा रहे हैं। बाहरी लूप में, हम एक ही सरणी में दो मानों तक मानों की प्रतिलिपि बनाने जा रहे हैं।

बाहरी लूप में केवल दो ट्रैवर्सल्स के बाद, यह आंतरिक लूप में जाएगा। में घुमाव के दौरान, हम यह जांचने जा रहे हैं कि क्या सूचकांकों का मूल्य 1. से अधिक है क्योंकि हम पिछले दो मूल्यों के बराबर होने पर तुलना करने जा रहे हैं। इसलिए हम उस शर्त को छोड़ देते हैं कि दो मानों को सरणी स्थित मानों में कॉपी किया जाना चाहिए। फिर बस स्थिति के मूल्यों को कम करें और संख्या 1 से अधिक मान वाले सरणी तत्व को अपडेट करें। हम बस इस लूप और इस पद्धति को जारी रखेंगे। यह उन सभी मूल्यों को लगातार लोगों के साथ बदल देगा।

अब 0 से इंडेक्स स्थिति में सरणी को प्रिंट करें जो अंतिम अपडेट किया गया था, यह वांछित सरणी देगा।

दो लगातार बराबर मूल्यों को एक से अधिक के साथ बदलें

 

कोड

C ++ कोड एक से अधिक के साथ दो लगातार समान मूल्यों को बदलने के लिए

#include<iostream>

using namespace std;

void replaceValues(int arr[], int n)
{
    int position = 0;

    for (int i = 0; i < n; i++)
    {
        arr[position++] = arr[i];
        while (position > 1 && arr[position - 2] == arr[position - 1])
        {
            position--;
            arr[position - 1]++;
        }
    }
    for (int i = 0; i < position; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 2,5,5,6,2,7,7};
    int n = sizeof(arr) / sizeof(int);
    replaceValues(arr, n);
    return 0;
}
2 7 2 8

जावा कोड दो लगातार समान मूल्यों को एक से अधिक के साथ बदलना

class replaceConsecutiveValues
{
    public static void replaceValues(int arr[], int n)
    {
        int position = 0;
        for (int i = 0; i < n; i++)
        {
            arr[position++] = arr[i];
            while (position > 1 && arr[position - 2] == arr[position - 1])
            {
                position--;
                arr[position - 1]++;
            }
        }
        for (int i = 0; i < position; i++)
            System.out.print( arr[i] + " ");
    }
    public static void main(String args[])
    {
        int arr[] = {2,5,5,6,2,7,7};
        int n = arr.length;
        replaceValues (arr, n);
    }
}
2 7 2 8

जटिलता विश्लेषण

समय जटिलता

पर2जहां"N" सरणी में तत्वों की संख्या है. क्योंकि हमने दो नेस्टेड छोरों का उपयोग किया है जो कि बहुपद समय में एल्गोरिथ्म को चलाने के लिए बनाया है।

अंतरिक्ष जटिलता

ओ (1), यह सरणी में तत्वों की संख्या से स्वतंत्र है. एल्गोरिथ्म अपने आप में निरंतर स्थान लेता है लेकिन एक पूरे के रूप में कार्यक्रम O (N) स्थान (इनपुट के लिए) लेता है।