صف ۾ سڀئي جوڙا ڳوليو (a ، b) جيئن هڪ٪ b = k


تڪليف جي سطح سخت
بار بار پڇڻ ۾ Amazon آرڪسيميم قلعي سڌو مفت چارج ياهو
ڪيريو هاش ماڊل آرٽيڪل

مسئلي جو بيان

مسئلو ”ساري ۾ سڀ جوڙي (a، b) ڳوليو ته٪ b = k“ ٻڌائي ٿو ته توهان کي انٽيگرز ۽ هڪ انٽيگر ويل شي ترتيب ڏني وئي آهي k. مسئلو بيان ڪرڻ واري جوڙي کي اهڙي طرح ڳولڻ چاهي ٿو ته x ٪ y = k (ڏنل قيمت) هڪ صف ۾.

مثال

arr[] = {3, 4, 7, 5, 6 }
k = 3
(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)

وضاحت

جڏهن اهي٪ b = k صحيح آهي ته انهن 4 جوڙن جي تصديق ڪئي وئي آهي.

صف ۾ سڀئي جوڙا ڳوليو (a ، b) جيئن هڪ٪ b = k

arr[]={2, 3, 5, 1},
k = 2
(2, 3) (2, 5) (5, 3)

وضاحت

جڏهن اهي٪ b = k صحيح آهي ته انهن 3 جوڙن جي تصديق ڪئي وئي آهي.

الورورٿم

  1. اعلان ڪيو اي نقشي ۽ انهي جو هڪڙو دلائل چونڊيو اي ٻيلو.
  2. اصل کي گهرايو صف ۽ صحيح بولين جي قيمت کي صف جي سڀني قدرن کي نقشي ۾ محفوظ ڪريو.
  3. چوڻ لاءِ ڪوبه بولين متغير مقرر ڪريو جوڙو چڪاس غلط ڪرڻ.
  4. 0 کان ن -1 تائين صف کي ڳولهيو (ن صف جي ڊيگهه آهي).
    1. چيڪ ڪريو جيڪڏهن ڏنل ڪي قيمت نقشي ۾ داخلا آهي ۽ ڪي پڻ موجوده صف واري عنصر کان نن isا آهي. جيڪڏهن صحيح ، پوءِ قدر ڪي ۽ پراريز آرٽ کي پرنٽ ڪيو ۽ Boolean ويليو کي صحيح سيٽ ڪيو
    2. چيڪ ڪريو ڪي ڪ موجوده آرٽ عنصر کان گهٽ يا برابر آهي.
      1. جيڪڏھن صحيح آھي ته ویکٹر ٺاھيو ۽ arr [i] -k ويل جي سڀني تقسيم ڳوليو ۽ ان کي ویکٹر ۾ اسٽور ڪريو.
      2. ان ويٽر کي پار ڪيو ۽ چيڪ ڪريو ته سيٽر جو عنصر ۽ صف جو عنصر جوڙيو ويو آهي جڏهن ماڊولو ٿي ويو ته حالت کي پورو ڪري ٿو.
        1. ویکٹر ۽ موجوده ليئر عنصر کي پرنٽ ڪيو ۽ سچ ڪريو Boolean قيمت کي ترتيب ڏيو.
  5. واپسي جوڙو چڪاس.

وضاحت

انٽيگرز جي هڪ قطار ۽ انٽيگر قيمت ڪي. اهڙي طرح جوڙو ڳوليو جڏهن اسان هڪ جوڙي کي ماڊلو آپريشن انجام ڏيون (x، y) ته x٪ y = k ، پوءِ اسان کي انهي جوڙي کي پرنٽ ڪرڻ جي ضرورت آهي ، اسان کي اهو پوري انگ اکر سان ڪرڻ گهرجي. اهي سڀئي پاڙا ڳوليو جيڪي قدر ڏيو جڏهن اسان هڪ نمبر x ٪ y تي ماڊليو آپريشن انجام ڏيو. ان لاءِ ، اسان ھڪڙو مجموعو استعمال ڪرڻ وارا آھيون يا ايس ٽي ايل کي ويڪٽر ۽ نقشو سڏيو وڃي ٿو.

صف جي سڀني عنصرن کي نقشي ۾ رکو ۽ انھن کي سڀني کي ”سچي“ بولين قيمت سان نشان لڳايو. اسان کي بوائلين متغير شروع ڪرڻ جي ضرورت آهي سڏيو ويندو آهي جوڙو چڪاس غلط ڪرڻ. اسان انهي کي تازه ڪاري ڪرڻ وارا آهيون جڏهن اسان کي صحيح جوڙو ملندو. پوءِ اسان هينئر ترتيب ڏيارڻ جا آهيون. ۽ چيڪ ڪريو ته ڏنل ڪ ويليو نقشي ۾ موجود آهي يا نه. ان کان علاوه جيڪڏهن k موجوده صف واري عنصر کان گهٽ آهي. پوء اسان صرف انهي جوڙي کي پرنٽ ڪريون ٿا. ڇو ته جڏهن اسان نن numberي انگ کي وڏي انگ سان ورهايو ٿا ته باقي کي نن aو نمبر ڪري ڇڏيندو آهي.

جيڪڏهن مٿيون شرط غلط ٿي وڃي ، پوءِ چڪاس ٿيون ته موجوده عنصر ڪي کان وڏو آهي. جيڪڏهن صحيح ، ته پوءِ اسان کي هڪ ویکٹر اعلان ڪرڻ جي ضرورت آهي ، جتي اسان موجوده ليئر عنصر ۽ ڪي جو فرق پاس ڪريون ، جيڪو ويٽر کي واپس ڪندو جنهن ۾ پئرس ممڪن قيمتون موٽي وينديون آهن. اسان هر قيمت کي چونڊڻ وارا آهيون ۽ چڪاس ڪندا ته موجوده صف واري عنصر ماڊلو واپسي ويڪر کي ویکٹر ۾ باقي ڏني وئي آهي يا نه. جيڪڏھن اھو سچ آھي ته ٻيھر کي پرنٽ ڪريو ۽ صحيح جوڙي جوڙي چيڪ ڪريو ، اھو مطلب آھي اسان کي گھٽ ۾ گھٽ ھڪڙو جوڙو مليو. ساڳئي قدم سان وڌيڪ قدر سان اڳتي وڌو ۽ سڀني ممڪن نتيجن کي پرنٽ ڪيو.

ڪوڊ

سي ترتيب ڏيڻ ۾ C ++ ۾ سڀ جوڙو (a ، b) ڳولڻ لاءِ ته جيئن٪ b = k

#include <unordered_map>
#include<vector>
#include<iostream>
#include<math.h>

using namespace std;

vector<int> findPossibleDiv(int n)
{
    vector<int> vecDiv;

    for (int i = 1; i <= sqrt(n); i++)
    {
        if (n % i == 0)
        {
            if (n / i == i)
                vecDiv.push_back(i);
            else
            {
                vecDiv.push_back(i);
                vecDiv.push_back(n / i);
            }
        }
    }
    return vecDiv;
}
bool pairModulousK(int arr[], int n, int k)
{
    unordered_map<int, bool> MAP;
    for (int i = 0; i < n; i++)
        MAP[arr[i]] = true;

    bool pairCheck = false;
    for (int i = 0; i < n; i++)
    {
        if (MAP[k] && k < arr[i])
        {
            cout << "(" << k << ", " << arr[i] << ") ";
            pairCheck = true;
        }
        if (arr[i] >= k)
        {
            vector<int> vec = findPossibleDiv(arr[i] - k);

            for (int j = 0; j < vec.size(); j++)
            {
                if (arr[i] % vec[j] == k && arr[i] != vec[j] && MAP[vec[j]])
                {
                    cout << "(" << arr[i] << ", "<< vec[j] << ") ";
                    pairCheck = true;
                }
            }
            vec.clear();
        }
    }
    return pairCheck;
}
int main()
{
    int arr[] = { 3, 4, 7, 5, 6 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int k = 3;

    if (pairModulousK(arr, n, k) == false)
        cout << "No such pair exists";
    return 0;
}
(3, 4) (3, 7) (7, 4) (3, 5) (3, 6)

جاوا ڪوڊ سڀني جوڙي کي ڳولڻ لاءِ (اي ، ب) صف ۾ اهڙي قسم جو٪ b = k

import java.util.HashMap;
import java.util.Vector;

class PairModuloK
{
    public static Vector<Integer> findPossibleDiv(int n)
    {
        Vector<Integer> vecDiv = new Vector<>();

        for (int i = 1; i <= Math.sqrt(n); i++)
        {
            if (n % i == 0)
            {
                if (n / i == i)
                    vecDiv.add(i);
                else
                {
                    vecDiv.add(i);
                    vecDiv.add(n / i);
                }
            }
        }
        return vecDiv;
    }
    public static boolean pairModulousK(int arr[], int n, int k)
    {
        HashMap<Integer, Boolean> MAP = new HashMap<>();
        for (int i = 0; i < n; i++)
            MAP.put(arr[i], true);

        boolean pairCheck = false;
        for (int i = 0; i < n; i++)
        {
            if (MAP.get(k) && k < arr[i])
            {
                System.out.print("(" + k + ", " + arr[i] + ") ");
                pairCheck = true;
            }
            if (arr[i] >= k)
            {
                Vector<Integer> vec = findPossibleDiv(arr[i] - k);

                for (int j = 0; j < vec.size(); j++)
                {
                    if (arr[i] % vec.get(j) == k && arr[i] != vec.get(j) && MAP.get(vec.get(j)))
                    {
                        System.out.print("(" + arr[i] + ", "
                                         + vec.get(j) + ") ");
                        pairCheck = true;
                    }
                }
                vec.clear();
            }
        }

        return pairCheck;
    }
    public static void main(String args[])
    {
        int arr[] = {3, 4, 7, 6, 5};
        int k = 3;

        if (pairModulousK(arr, arr.length, k) == false)
            System.out.println("No such pair exists");
    }
}
(3, 4) (3, 7) (7, 4) (3, 6) (3, 5)

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (ن * اسڪوٽر (وڌ) جتي وڌ کان وڌ صف ۾ سڀ کان وڌيڪ عنصر آهي. هن ڀيري پيچيدگي حاصل ٿي هئي ڇو ته اسان استعمال ڪيو

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

اي (ن) جتي “ن” صف ۾ موجود عنصرن جو تعداد آهي. هن جڳهه کي نقشي ۾ موجود عناصر کي محفوظ ڪرڻ جي لاءِ گهربل آهي.