Verilən Fərqlə Bütün Cütləri tapın

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Amazon Bloomberg Citrix Expedia Goldman Sachs microsoft Nvidia Kahin Salesforce Twilio cuqquldamaq Viza VMware
Geyim İkili axtarış çeşidləyiciBaxılıb 208

Problem bəyanat

Biz verdik array fərqli elementləri ehtiva edən və ya massivdə təkrarlanan elementlərin olmaması. Verilən fərqi olan bütün cütləri tapın. Fərqli hər hansı bir cüt yoxdursa, yazdırın “Fərqli ilə cütlük yoxdur”.

misal

Input

10 20

90 70 20 80 50 25 35 15 100 150

Buraxılış

90 70

70 50

80 100

35 15 (Fərqi 20 olan element cütü çap olunacaq)

Verilən Fərqlə Bütün Cütləri tapmaq üçün 1 yanaşma

Dizidən bir element seçəcək iki döngə işlədin. İndeks 0-dan başlayaraq verilmiş fərqlə cütlük əldə etmək üçün sıra gözləyirik.

a) Elementi tapırıqsa, onları çap edin.
b) Başqa çap, tapılmadı.

Həyata keçirilməsi

Verilən Fərqlə Bütün Cütləri Tapmaq üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,d;
  cin>>n>>d;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  int flag=0;
  for(int i=0;i<n;i++)//select an element
  {
    for(int j=i+1;j<n;j++) // look forward in the array
        if(abs(a[i]-a[j])==d)//if we get a pair with given difference then success
        {
          cout<<a[i]<<"  "<<a[j]<<endl;
          flag=1;
        }
  }
  if(flag==0)
  cout<<"No pair with given different";
}

Müəyyən bir fərqlə bütün cütləri tapmaq üçün Java proqramı

import java.util.Scanner;
class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            x*=-1;
        }
        return x;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int d = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int flag=0;
        for(int i=0;i<n;i++)//select an element
        {
          for(int j=i+1;j<n;j++) // look forward in the array
              if(abs(a[i]-a[j])==d)//if we get a pair with given difference then success
              {
                System.out.println(a[i]+"  "+a[j]);
                flag=1;
              }
        }
        if(flag==0)
        System.out.println("No pair with given different");
    }
}
10 20
90 70 20 80 50 25 35 15 100 150
90  70
70  50
80  100
35  15

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N * N) burada N - verilən massivin ölçüsüdür. Sadəcə, hər bir cüt üçün döngələr üçün iki işləyərək yoxlayın.

Kosmik Mürəkkəblik

O (1) çünki burada əlavə yerdən istifadə etmirik.

Verilən Fərqlə Bütün Cütləri tapmaq üçün 2 yanaşma

1 Adım: Əvvəlcə verilmiş massivi çeşidləyin. O (NlogN) alır.

2 Adım: İlk alqoritmlə eyni şəkildə, birinci elementdən başlayan hər element üçün uyğun cütü tapın.

i) Burada elementi tapmaq üçün ikili axtarışdan istifadə edəcəyik.
ii) a elementi və verilən fərq n üçün a + n axtarırıq.

misal

Input

10 20

90 70 20 80 50 25 35 15 100 150

Fərq = 20 olan bütün cüt elementləri tapın

Alqoritmi giriş massivinə tətbiq edin,

Addım-addım işləyin

  1. Dizini sıralayın, Sıralanan massiv: 15 20 25 35 50 70 80 90 100 150
  2. a = 15, fərq (n) = 20 belə, a + n = 35, ikili_search (35, giriş massivi) = Doğrudur. Çap et 15 35. İrəli gedin
  3. a = 20, fərq (n) = 20 belə, a + n = 40, ikili_search (40, giriş massivi) = Yanlış. Önə doğru irəlilə
  4. a = 25, fərq (n) = 20 belə, a + n = 45, ikili_search (45, giriş massivi) = Yanlış. Önə doğru irəlilə
  5. a = 35, fərq (n) = 20 belə, a + n = 55, ikili_search (55, giriş massivi) = Yanlış. Önə doğru irəlilə
  6. a = 50, fərq (n) = 20 belə, a + n = 70, ikili_search (70, giriş massivi) = Doğrudur. Çap et 50 70. İrəli gedin
  7. a = 70, fərq (n) = 20 belə, a + n = 90, ikili_search (90, giriş massivi) = Doğrudur. Çap et 70 90. İrəli gedin
  8. a = 80, fərq (n) = 20 belə, a + n = 100, ikili_search (100, giriş massivi) = Doğrudur. Çap et 80 100. İrəli gedin
  9. a = 90, fərq (n) = 20 belə, a + n = 110, ikili_search (110, giriş massivi) = Yanlış. Önə doğru irəlilə
  10. a = 100, fərq (n) = 20 belə, a + n = 120, ikili_search (120, giriş massivi) = Yanlış. Döngünün sonu.

Həyata keçirilməsi

Verilən Fərqlə Bütün Cütləri Tapmaq üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
int main()
{
  int n,d;
  cin>>n>>d;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  sort(a,a+n);
  int flag=0;
  for(int i=0;i<n-1;i++)//select an element
  {
      int diff=a[i]+d;
      if(binary_search(a,a+n,diff))
      {
          cout<<a[i]<<" "<<diff<<endl;
          flag=1;
      }
  }
  if(flag==0)
  cout<<"No pair with given different";
}

Müəyyən bir fərqlə bütün cütləri tapmaq üçün Java proqramı

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    public static int abs(int x)
    {
        if(x<0)
        {
            x*=-1;
        }
        return x;
    }
    public static int binary_search(int arr[], int l, int r, int x)
    {
        if (r >= l) 
        {
            int mid = l + (r - l) / 2;
            if (arr[mid] == x)
                return mid;
            if (arr[mid] > x)
                return binary_search(arr, l, mid - 1, x);
            return binary_search(arr, mid + 1, r, x);
        }
        return -1;
    }
    
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int d = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        Arrays.sort(a);
        int flag=0;
        for(int i=0;i<n-1;i++)//select an element
        {
            int diff=a[i]+d;
            if(binary_search(a,0,n-1,diff)!=-1)
            {
                System.out.println(a[i]+"  "+diff);
                flag=1;
            }
        }
        if(flag==0)
         System.out.println("No pair with given different");
    }
}
10 20
90 70 20 80 50 25 35 15 100 150
15 35
50 70
70 90
80 100

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (NlogN) burada N - verilən massivin ölçüsüdür. İkili axtarış O (logN) alır, buna görə hər bir element üçün ikili axtarışdan istifadə etmək üçün zaman mürəkkəbliyi O (NlogN) olur.

Kosmik Mürəkkəblik

O (1) çünki burada əlavə yerdən istifadə etmirik.

References

Translate »