پہلا عنصر دوگنا اور صفر کو ختم کرنے کے لئے منتقل کریں


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے مائیکروسافٹ Zoho
لڑی

مسئلہ یہ بیان

فرض کریں کہ آپ کے پاس ایک صف ہے اشارے. یہاں "0" وہ نمبر نہیں ہے جس کو ایک ان پٹ کے طور پر سمجھا جاتا ہے۔ یہ یہاں درست ان پٹ نہیں ہے۔ مسئلہ "پہلے عنصر کو دوگنا اور صفر کو ختم کرنے کے لئے منتقل کریں" سے صف کو اس طرح سے ترتیب دینے کے لئے کہتا ہے اگر 0 کے علاوہ کوئی اور تعداد مل جاتی ہے اور اس کا اگلا نمبر ایک ہی نمبر ہوتا ہے جس کے بعد اس کی تعداد دوگنی ہوجاتی ہے اور نشان لگا دیا جاتا ہے اگلی نمبر کے طور پر 0. آخر میں آخر میں تمام زیرو کو دبائیں۔

مثال کے طور پر

arr[] = {3, 3, 5, 0, 1, 0, 0, 1, 0}
6 5 1 1 0 0 0 0 0

وضاحت: چونکہ 3 ایک عدد ہے جو متواتر ہوتا ہے ، لہذا ہم اس کو 3 بنانے کے لئے پہلے 6 کو دوگنا کرتے ہیں اور اگلے 3 کو 0 کی حیثیت سے نشان زد کرتے ہیں۔ اور یہ بھی تمام صفر کو آخری ڈاٹ ایکس میں منتقل کردیا گیا ہے۔

پہلے عنصر کو دوگنا کرنے کے ل Al الگورتھم اور صفر کو ختم کرنے کے لئے منتقل کریں

1. Traverse the array from 0 to n-1(inclusively).
2. Check if arr[i] is not equal to 0 and arr[i]==arr[i+1](next value is same as current value).
  1. If true, then make the current value twice of the self.
  2. Update next element as 0 and do i++.
3. Traverse the array from i = 0 to n-1(step of shifting all the zeroes to the end).
  1. Check if arr[i] != 0.
    1. Arr[count]=arr[i] and do count++.
4. From the traversal of till count is less than n.
  1. Arr[count]=0 and do count++.
5. Print the array.

وضاحت

اسے دیئے گئے انداز میں دوبارہ ترتیب دینے کیلئے ایک صف دی۔ ہم نے اگلا نمبر تبدیل کرنے کو کہا ہے اگر موجودہ نمبر اگلے نمبر کی طرح ہے۔ تبدیلی یہ ہے کہ ہمیں موجودہ تعداد کو دوگنا کرنا ہے۔ اور اگلی نمبر کو 0 کے بطور نشان زد کریں اگر دی گئی شرط پوری ہوجائے۔ اس ترمیم کے بعد ، ہمیں تمام صفر کو صف کے آخری حصے میں منتقل کرنا ہے جو ہم نے بنائے ہیں یا جو پہلے ہی صف میں موجود ہیں۔ پھر آؤٹ پٹ کو واپس کرنا ہے۔

صف کو 0 سے n تک عبور کریں - 1. چیک کریں کہ آیا ہر ایک کی قیمت 0 کے برابر نہیں ہے کیونکہ ہمیں 0 کی اقدار میں کوئی تبدیلی کرنے کی اجازت نہیں ہے۔ اور چیک کریں کہ آیا موجودہ عنصر اگلے عنصر کے برابر ہے جیسا کہ arr [i] = = arr [i + 1]۔ ہم نے این -1 کو ٹراورسل کے آخری پوائنٹ کے طور پر لیا ہے کیونکہ ہم موجودہ نمبر تک اگلے نمبر کی تلاش کر رہے ہیں۔ لہذا اگر ہم تلاش کرنے کے لئے آخری عنصر کی حیثیت سے ن کو تلاش کریں تو ، ہم نلی پوائنٹر کی رعایت حاصل کریں گے۔ اگر دی گئی شرائط مطمئن ہیں تو ہم موجودہ عنصر کو منتخب کرتے ہیں اور اسے موجودہ قیمت سے دوگنا کرتے ہیں اور اگلی قیمت 0 میں اپ ڈیٹ کرتے ہیں۔ ہمیں یہ صف کی تمام اقدار کے ل do کرنا چاہئے۔

اب تمام اقدار کو 0 کی طرح آخری پر منتقل کریں۔ اس صف کو دوبارہ عبور کرنے کے ل check ، اور جانچ کریں کہ اگر قیمت برابر نہیں ہے تو ، پھر اسے بائیں طرف منتقل کریں ، تمام اقدار کو بائیں طرف منتقل کرنے کے بعد ، ہمیں آخر میں منتقل کردہ قیمت کا ایک اشاریہ ملتا ہے ، اس گنتی سے ہم آگے بڑھیں گے لوپ اور اس گنتی سے ن کی قیمت تک ، ہم تمام اقدار کو 0 کے طور پر اپ ڈیٹ کریں گے۔ آخر میں سرنی پرنٹ کریں۔

پہلا عنصر دوگنا اور صفر کو ختم کرنے کے لئے منتقل کریں

ضابطے

پہلے عنصر کو دوگنا کرنے کے لئے سی ++ کوڈ اور مسئلہ کو ختم کرنے کے لئے صفر منتقل کریں

#include<iostream>

using namespace std;

void shiftZeroAtLast(int arr[], int n)
{
    int count = 0;

    for (int i = 0; i < n; i++)
        if (arr[i] != 0)
            arr[count++] = arr[i];

    while (count < n)
        arr[count++] = 0;
}
void arrayModification(int arr[], int n)
{
    if (n == 1)
        return;
    for (int i = 0; i < n - 1; i++)
    {
        if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
        {
            arr[i] = 2 * arr[i];

            arr[i + 1] = 0;

            i++;
        }
    }
    shiftZeroAtLast(arr, n);
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {3,3,5,0,1,0,0,1,0};
    int n = sizeof(arr) / sizeof(arr[0]);

    arrayModification(arr, n);

    cout << "Modified array: ";
    printArray(arr, n);

    return 0;
}
Modified array: 6 5 1 1 0 0 0 0 0

پہلے عنصر کو دوگنا کرنے کے لئے جاوا کوڈ اور مسئلہ کو ختم کرنے کے لئے صفر منتقل کریں

class arrayRearrange
{
    public static void shiftZeroAtLast(int arr[], int n)
    {
        int count = 0;

        for (int i = 0; i < n; i++)
            if (arr[i] != 0)

                arr[count++] = arr[i];

        while (count < n)
            arr[count++] = 0;
    }
    public static void arrayModification(int arr[], int n)
    {
        if (n == 1)
            return;

        for (int i = 0; i < n - 1; i++)
        {
            if ((arr[i] != 0) && (arr[i] == arr[i + 1]))
            {
                arr[i] = 2 * arr[i];

                arr[i + 1] = 0;

                i++;
            }
        }
        shiftZeroAtLast(arr, n);
    }
    public static void printArray(int arr[], int n)
    {
        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    public static void main(String[] args)
    {
        int arr[] = {3,3,5,0,1,0,0,1,0};
        int n = arr.length;


        arrayModification(arr, n);

        System.out.print("Modified array: ");
        printArray(arr, n);
    }
}
Modified array: 6 5 1 1 0 0 0 0 0

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (N) کہاں "N" صف میں عناصر کی تعداد ہے۔ ہم نے دو مرتبہ صف کو آسانی سے عبور کیا ہے جس کی وجہ سے الگورتھم خطی وقت میں چلتا ہے۔

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

الگورتھم کی ضرورت ہے O (1) اضافی جگہ لیکن پروگرام ان پٹ کو اسٹور کرنے کے لئے O (N) کی کل جگہ لیتا ہے۔