ھڪڙي لڳاتار ٻن برابر جيترن کي ھڪڙي سان تبديل ڪريو


تڪليف جي سطح آسان
بار بار پڇڻ ۾ Accenture قلعي مفت چارج PayPal چورس ٽراداتا
ڪيريو

مسئلي جو بيان

فرض ڪيو ته توهان وٽ هڪ انوڊر آهي صف. مسئلو ”مسلسل دو برابر قدریں ایک سے زیادہ بدلیں يا ته هتي ڪا نئين لڳاتار ڪاٿي باقي ناهي بچي.

مثال

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

وضاحت

جئين 1 ھڪڙي لڳاتار نمبر آھي اھو ان جي بدلي جي قيمت کان گھڻي رھيو آھي ان جو مطلب آھي 2 ۽ ارو {5,2,2,2,2،XNUMX،XNUMX،XNUMX،XNUMX} ٿي ويندو

هاڻ 2 لڳاتار نمبر آهي تنهن ڪري ان جي ڀيٽ ۾ وڏي تعداد مان تبديل ٿي ويندي يعني 3 ۽ arr ٿيندو {5,3,2,2،XNUMX،XNUMX،XNUMX}

ٻيهر 2 لڳاتار نمبر آهي تنهنڪري 3 طرفان تبديل ڪيو ويندو ۽ arr ٿي ويندو {5,3,3،XNUMX،XNUMX}

ھاڻي 3 لڳاتار نمبر آھي تنھنڪري 4 جي طرف مٽايو ويندو ۽ arr ٿي ويندو {5,4،XNUMX}

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

وضاحت

جئين 5 ھڪڙي لڳاتار نمبر آھي ان کي بدلي ڪيو ويو آھي قدر 1 جي معني ان کان وڌيڪ آھي 6. تنھنڪري arr وانگر نظر ايندو [] = {2,6,6,2,7,7،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX}

6 انهي جي جاءِ تي اچي وڃن ٿا پر ايندڙ نمبر پڻ 6 آهي ، تنهن ڪري ان کي 1 کان وڌيڪ 6 جي قيمت سان پڻ تبديل ڪيو ويو آهي ، مطلب 7 ۽ arr {2,7,2,7,7،XNUMX،XNUMX،XNUMX،XNUMX} ٿي ويندا

جئين 7 آخرڪار پڻ لاڳيتو ٿين ٿا ، انهي ڪري ان کي 8 سان تبديل ڪيو وڃي ٿو ۽ arr {2,7,2,8،XNUMX،XNUMX،XNUMX} ٿي ويندو

الورورٿم

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 لڳاتار arrays ۾ اچي وڃن ، ته اهو 5 سان تبديل ٿي ويندو. اهو نمبر 1 کان وڏو آهي 4. هاڻي هڪ traversal سان ، اسان صرف هڪ ترميم ڪري سگهون ٿا. فرض ڪريو ، هتي موجود 3 عدد 4 ، 4 ، 5. پوءِ اسان 4 ، 4 کان 5 ۽ پوءِ 5 پڻ لڳاتار نمبر بدلائي رهيا آهيون. ڇو ته هن جو ايندڙ نمبر خود نمبر جيترو آهي. تنهن ڪري اسان اهو هڪ بند ٿيل لوپ استعمال ڪندي ڪندي.

0 کان ن تائين صف بندي جو سفر ڪيو. لوپ کي کوليو ، تنھنڪري اهو هڪ نئون ٿيل loopرندڙ ٿيندو. ٻاهرين لوپ سان ، اسان پيچرن کي سنڀالينداسين. ۽ اندروني لوپ سان ، اسان ڏنل شين جي مطابق قدرن کي تازه ڪاري ڪرڻ يا اقدار کي مٽائڻ وارا آهيون. ٻاهرين لوپ ۾ ، اسان ٻن قيمتن تائين ساڳئي صفن ۾ قدر ڪاپي ڪرڻ وارا آهيون.

صرف ٻاهرئين لوپ ۾ ٻن ٽاور کان پوءِ اهو اندرئين لوپ ۾ ويندو. اي ۾ جڏهن ته لوپ، اسان چڪاس ڪرڻ وارا آهيون ته انڊيڪس جي قيمت 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جتي“ن” صف ۾ موجود عنصرن جو تعداد آهي. ڇو ته اسان ٻن جوڙيل لوپز جو استعمال ڪيو آهي جيڪي الگونزم کي پولينيوميل ٽائيم ۾ هلائڻ لاءِ ٺاهيا هئا.

خلائي پيچيدگي

اي (1) ، اھو صف ۾ عناصر جي تعداد کان آزاد آھي. الگورٿم پاڻ کي مستقل جڳھ وٺندي آهي پر س asو پروگرام اي او (اين) اسپيس ورتي ٿو (انپٽ لاءِ).