جوڑی میں صف تقسیم کرنے کے ساتھ ساتھ کے تقسیم کی رقم کے ساتھ


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

کے ذریعہ جوڑیوں میں تقسیم کی جانے والی رقم کو تقسیم کرکے تقسیم کرنا ایک مسئلہ ہے جو اب اور پھر مختلف ٹوئیکس کے ساتھ انٹرویو میں پوچھا جاتا ہے۔ جو لوگ مجھے جانتے ہیں وہ ان مسائل کو کہانیوں میں تبدیل کرنے کی میری عادت جانتے ہیں۔ اس مضمون میں آئیے اس مسئلے پر غور کریں۔

مسئلہ کو سمجھنے کی صورتحال

وبائی مرض کے پھیلاؤ کے ساتھ ، ہمارے پاس بہت ساری تنظیمیں غریبوں کی مدد اور امداد کے ل bring آگے بڑھ رہی ہیں۔ آج کے دن ہم ان امدادی کوششوں کے کو آرڈینیٹر ہیں۔ ہمیں راشن کے تھیلے اکٹھا کرنے اور انہیں "کے" بیگ میں بانٹنے کا کام سونپا گیا ہے۔ ہمیں ہر گھر سے راشن مل رہا ہے جس کی نمائندگی ایک صف میں کی جاتی ہے۔ بہتر تفہیم کے ل۔ آئیے مزید وضاحت کے ل a نمونہ ٹیسٹ کیس دیکھیں۔

مثال کے طور پر

ان پٹ:

5

A = [4,5,0،2،3,1، -XNUMX، -XNUMX،XNUMX]

: پیداوار

7

5 کے ذریعہ تقسیم ہونے والے سبریوں کی تعداد یہ ہے:

[4,5,0,-2,-3,1],[5],[5,0],[5,0,-2,-3],[0],[0,-2,-3],[-2,-3]

سرنی ہر گھر سے پیکٹوں کی تعداد کی نمائندگی کررہی ہے۔ ہم قریب کے مقام پر کے پیکٹ کی فراہمی کے لئے ملحقہ گھرانوں کو کلبھوشن کر رہے ہیں۔ زیادہ آسانی سے ، ہم سرنی کو سبریوں میں تقسیم کرنے کی تلاش میں ہیں رقم to “k”. ہم اس مسئلے کے بارے میں مختلف طریقوں پر غور کرسکتے ہیں۔ تاہم ، اس پوسٹ میں ، میں سب سے آسان پیش کر رہا ہوں جو بہت قابل فہم ہے۔

جوڑی میں صف کو تقسیم کرنے کے ل Al الگورتھم جس کے ذریعہ K کی تقسیم ہوتی ہے

  • ہم ایک ایسی صف تیار کریں گے جس میں مذکورہ انڈیکس کی رقم ہوسکے
  • تب ہم باقی رقم تلاش کر رہے ہیں جو اس انڈیکس تک پائے جاتے ہیں جب رقم انڈیکس کے ذریعہ تقسیم ہوجاتی ہے
  • اگر باقی 0 سے چھوٹا ہے تو ہم k شامل کرتے ہیں
  • ہاشمیپ بقیہ اور اس کی موجودگی کو اہم قدر کے جوڑے کے طور پر ذخیرہ کرے گا
  • اس کے بعد ہم استعمال کرنے والے ہر بقیہ کے ساتھ تیار کرسکتے ہوئے سبسیٹس کی تعداد ڈھونڈیں گے
  • رقم = رقم + قیمت * (ویلیو -1) / 2

عمل کی وضاحت کرنے والی تصویر ہوسکتی ہے

جوڑی میں صف تقسیم کرنے کے ساتھ ساتھ کے تقسیم کی رقم کے ساتھ
مسئلہ کی وضاحت

اب جب کہ ہمارے پاس یہ اختیار ہے کہ ہمیں کیا کرنا ہے کہ ہمیں ضابطہ اخلاق پر غور کریں

جاوا کوڈ

class Solution 
{
    public int subarraysDivByK(int[] A, int k) 
    {
        if(A==null || A.length<1)
            return -1;
        int sum[]=new int[A.length+1];
        for(int i=1;i<sum.length;i++)
        {
            sum[i]=sum[i-1]+A[i-1];
        }
        HashMap<Integer,Integer>combos=new HashMap<Integer,Integer>();
        for(int i=0;i<sum.length;i++)
        {
            int cur=sum[i]%k;
            if(cur<0)
                cur=cur+k;
            if(!combos.containsKey(cur))
                combos.put(cur,1);
            else
                combos.put(cur,combos.get(cur)+1);
        }
        System.out.println(combos);
        int ans=0;
        for(int i:combos.values())
        {
            ans+=i*(i-1)/2;
        }
        return ans;
    }
}

C ++ کوڈ

class Solution 
{
public:
    int subarraysDivByK(vector<int>& A, int k) 
    {
     if(A.size()<1)
            return -1;
        int sum[A.size()+1];
        for(int i=1;i<A.size()+1;i++)
        {
            sum[i]=sum[i-1]+A[i-1];
        }
        unordered_map<int,int>combos;
        for(int i=0;i<A.size()+1;i++)
        {
            int cur=sum[i]%k;
            if(cur<0)
                cur=cur+k;
            combos[cur]+=1;
        }
        int ans=0;
        for(auto i:combos)
        {
            ans+=(i.second)*(i.second-1)/2;
        }
        return ans;    
    }
};
5
{4, 5, 0, -2, -3, 1}
7

جوڑیوں میں صف تقسیم کرنے کے لئے پیچیدہ تجزیہ کے ذریعہ کے ذریعہ تقسیم کی رقم

اس حل میں ، مسئلے کے لئے وقت کی پیچیدگی اور خلائی پیچیدگی کو درج کیا جاسکتا ہے

وقت کی پیچیدگی = O (n)

خلائی پیچیدگی = O (n)

کیسا رہے گا؟

سب سے پہلے اسپیس کمپلیکسٹی

  • N اندراجوں پر مشتمل ہش میپ میں تمام اقدار ہیں
  • یہ نقشہ اتنا ہی بڑا ہے جتنا ہمارے پاس باقی بچے
  • آخر میں ، یہ خلائی پیچیدگی O (n) کی طرف لے جارہا ہے

دوم پیچیدگی

  • ہم حل میں تین لوپ چلا رہے ہیں
  • سب سے پہلے ، جوڑے = O (n) کو تلاش کرنے کے لئے ایک لوپ
  • دوم ، باقی = O (n) تلاش کرنے کے لئے ایک لوپ
  • تیسرا یہ کہ تمام امتزاج کی تلاش کریں = O (باقی)
  • آخر میں ، یہ سب O (n) کے وقت کی پیچیدگی کا باعث ہے

حوالہ جات