1 سے N-1 کے درمیان واحد تکرار عنصر تلاش کریں


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے کوپنڈونیا دہلی گرین اورنج انفارمیشن ایج لنکڈ نگررو SAP لیبز
لڑی ہیش تلاش

1 سے N-1 مسئلہ کے درمیان واحد تکرار عنصر تلاش کرنے میں ہم نے ایک صف 1 سے لے کر n-1 تک کی حد میں بے ترتیب اعداد کی تعداد۔ ایک نمبر ہوگا جو دہرایا جاتا ہے۔ آپ کا کام اس نمبر کو تلاش کرنا ہے۔

مثال کے طور پر

ان پٹ

[2,3,4,5,2,1،XNUMX،XNUMX،XNUMX،XNUMX،XNUMX] A

آؤٹ پٹ

2

وضاحت

2 عنصر ہے جو ایک صف میں دو بار آتا ہے۔

 

1 سے N-1 کے درمیان واحد بار بار عنصر تلاش کرنے کیلئے الگورتھم

  1. 0 کی رقم مقرر کریں۔
  2. جبکہ میں <این ، پوری صف کو عبور کرو۔
    1. رقم = جوڑ + ار [i]۔
  3. واپسی کی رقم- (n * (n-1)) / 2۔

1 سے N-1 کے درمیان واحد بار بار عنصر تلاش کرنے کے لئے وضاحت

ہم نے ایک مسئلہ (1 سے N-1 کے درمیان صرف دہرانا عنصر تلاش کریں) بیان دیا ہے جس میں اس نمبر کو جاننے کے لئے کہا گیا ہے جو ایک صف میں دہراتا ہے۔ ہم محض استعمال کرنے جارہے ہیں سم فارمولا۔ کا استعمال کرتے ہوئے سم فارمولا ، ہم بار بار عنصر کی آسانی سے شناخت کرسکتے ہیں۔ جیسا کہ نام سے ہمیں یہ معلوم ہوتا ہے سم فارمولا اس کا مطلب صرف اقدار کا خلاصہ کرنا ہے۔

ہم یہاں لوپ میں صف کو 0 ویں پوزیشن سے لوپ کے اختتام تک عبور کرنا شروع کردیتے ہیں جب تک کہ ہم آخری صف عنصر کا دورہ نہ کریں۔ ہر تکرار کے ساتھ اور سرنی کی ہر قیمت کے لئے [i] ہم اسے رقم کے ساتھ جوڑ کر اسے ذخیرہ کرنے جا رہے ہیں تاکہ اگلی بار جب ہم اس پر تکرار کریں گے تو ہم کو مجموعی قیمت مل جائے گی اور نہ کہ ابتدائی قیمت 0. لہذا ، ہر تکرار کے ذریعہ ، اس میں ہماری کچھ قدریں بطور رقم جمع ہوتی ہیں۔

ہمیں صرف ایک ایسا فارمولا بنانے کی ضرورت ہے جو بار بار عنصر دیتا ہے یا ہم یہ کہہ سکتے ہیں کہ یہ سلسلہ میں آنے والے ایک اضافی عنصر کو واپس کرتا ہے۔ فرض کریں کہ ہمارے پاس سلسلہ 1 سے 5 تک دیا گیا ہے ، جب ہم تمام اعداد شامل کرتے ہیں تو یہ تمام اعداد کا مجموعہ دیتا ہے اور بغیر سیریز میں کوئی اعادہ عنصر۔ اور ہم رقم کا فرق واپس کرتے ہیں - (n * (n-1)) / 2 ، جو ہمارا جمع فارمولا ہے۔

آئیے ایک مثال پر غور کریں:

arr = [2,3,4,5,2,1،0،XNUMX،XNUMX،XNUMX،XNUMX]، رقم = XNUMX

0 سے شروع ہوکر ، ہم ہر عنصر -> کو دیکھنے والے پورے لوپ کو عبور کرسکتے ہیں

i = 0؛

رقم = جوڑ + ارر [i] => رقم = 2

i = 1؛

رقم = جوڑ + ارر [i] => رقم = 5

i = 2؛

رقم = جوڑ + ارر [i] => رقم = 9

i = 3؛

رقم = جوڑ + ارر [i] => رقم = 14

i = 4؛

رقم = جوڑ + ارر [i] => رقم = 16

i = 5؛

رقم = جوڑ + ارر [i] => رقم = 17

اور ہم صرف رقم (- n * (n-1)) / 2 واپس کرتے ہیں جو 17- (6 * (6-1)) / 2 ہے۔

17 - 15 = 2 ، جو ہماری مطلوبہ آؤٹ پٹ ہے۔

 

1 سے N-1 کے درمیان واحد تکرار عنصر تلاش کریں

1 سے N-1 کے درمیان واحد تکرار عنصر تلاش کرنے کے لئے عمل درآمد

سی ++ پروگرام

#include<iostream>
using namespace std;
int getRepeatedElement(int arr[], int n)
{
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum = sum + arr[i];
    }
    return sum-(((n - 1) * n)/2);
}
int main()
{
    int arr[] = {1,5,3,2,6,4,7,8,4};
    int len = sizeof(arr)/sizeof(arr[0]);
    cout<<(getRepeatedElement(arr, len));
    return 0;
}
4

جاوا پروگرام

class repetitiveElement
{
    public static int getRepeatedElement(int[] arr, int n)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum = sum + arr[i];
        }
        return sum-(((n - 1) * n)/2);
    }
    public static void main(String args[])
    {
        int[] arr = {1,5,3,2,6,4,7,8,4};
        int len = arr.length;
        System.out.println(getRepeatedElement(arr, len));
    }
}
4

1 سے N-1 کے درمیان واحد بار بار عنصر تلاش کرنے کے لئے پیچیدگی کا تجزیہ

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

اے (ن) کہاں "این" صف میں عناصر کی تعداد ہے۔

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

O (1) کیونکہ ہم یہاں کوئی معاون جگہ استعمال نہیں کرتے ہیں۔

حوالہ جات