Verilən Fərqlə Cüt 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
İkili axtarış Axtarış çeşidləyiciBaxılıb 315

Problem bəyanat

Verilmiş çeşidlənməmişdir array, verilən fərq n ilə verilən massivdəki element cütünü tapın.

misal

Input

arr [] = {120, 30, 70, 20, 5, 6},

fərq (n) = 40

Buraxılış

[30, 70]

Izahat

Burada 30 və 70 arasındakı fərq n-in dəyərinə bərabərdir.

Input

arr [] = {120, 30, 70, 20, 5, 6},

fərq (n) = 10

Buraxılış

[20, 30]

Izahat

Burada 20 və 30 arasındakı fərq n-in dəyərinə bərabərdir.

Input

arr = {120, 30, 70, 20, 5, 6},

fərq (n) = 30

Buraxılış

Verilən fərqlə cütlük tapılmadı

Izahat

Burada, aralarındakı fərq n-ə bərabər olan belə bir cüt element mövcud deyil.

Verilən Fərqlə Cüt tapma alqoritmi

İndi problem ifadəsini bilirik. Beləliklə, alqoritm hissəsinə sürətlə keçin. Əvvəlcə verilmiş massivi sıralayırıq və sonra bütün massivi gəzirik. Əvvəlcə indeks 0-da iki, göstərici 1-də ikinci göstərici alırıq. Əgər aralarındakı fərq veriləndən azdırsa, ikinci göstəricini 1-ə keçirin. Əgər aralarındakı fərq veriləndən daha böyükdürsə, onda birinci göstəricini 1-ə keçirin. Əgər elementlər arasındakı fərq eynidirsə, cavabı sayın. Nəhayət, sayma sayını çap edin.

1: Əvvəlcə verilmiş massivi çeşidləyin.

2: Bu massivdə iki indeks alın və j i = 0 və j = 1 başladın.

3: Dizinin [j] - array [i] = n olub olmadığını tapmaq üçün dövrəni çalıştırın

  • Array [j] - array [i] = n varsa, array [j] və [i] array yazdırın.
  • Yoxlayın, əgər array [j] - array [i]> n, i artımı.
  • Array [j] - array [i] <n olarsa, artım j.

4: Döngü sona çatırsa. Sonra 'cüt tapılmadı' yazdırın.

Həyata keçirilməsi

Verilən Fərqlə Cütlüyü Tapmaq üçün C ++ Proqramı

#include <bits/stdc++.h>
using namespace std;
 
//In the given array -> array[] of N N 
//finding the pair with difference n
int FindPair(int array[], int N, int difference)
{
    //sort the given array
    sort(array, array+N);
    int i = 0;  
    int j = 1;
    while(i<N && j<N)
    {
        if (i != j && array[j]-array[i] == difference)
        {
            cout<<"pair with difference "<<difference<<" is: ";
            cout<<"["<<array[i]<<", "<<array[j]<<"]";
            return 1;
        }
        //if difference here is less than given difference
        // move right pointer(j)
        else if (array[j]-array[i] < difference) 
        {
            j++;
        }
        //if difference here is greater than given difference
        // move left pointer(i)
        else
        {
            i++;
        }
    }
    cout<<"No pair found";
    return 0;
}
 
//Main function to check above functions
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int diff;
    cin>>diff;
    FindPair(a, n, diff);
    return 0;
}

Verilən Fərqlə Cüt tapın üçün Java Proqramı

import java.util.Arrays;
import java.util.Scanner;
class sum
{
    //In the given array -> array[] of N N 
    //finding the pair with difference n
    public static int FindPair(int array[], int N, int difference)
    {
        //sort the given array
        Arrays.sort(array);
        int i = 0;  
        int j = 1;
        while(i<N && j<N)
        {
            if (i != j && array[j]-array[i] == difference)
            {
                System.out.println(array[i] + " " + array[j]);
                return 1;
            }
            //if difference here is less than given difference
            // move right pointer(j)
            else if (array[j]-array[i] < difference) 
            {
                j++;
            }
            //if difference here is greater than given difference
            // move left pointer(i)
            else
            {
                i++;
            }
        }
        System.out.println("No pair found");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int arr[] = new int[n];
        for(int i=0;i<n;i++)
        {
            arr[i] = sr.nextInt();
        } 
        int diff ;
        diff = sr.nextInt();
        FindPair(arr,n,diff);
    } 
}
6 
5 20 3 2 50 80
78
2 80

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (NLogN) burada n serialın ölçüsüdür. Burada bizi nlogn zaman mürəkkəbliyinə aparan daxili ayrılma funksiyasından istifadə edirik.

Kosmik Mürəkkəblik

O (1) çünki nəticəni hesablayarkən əlavə yer yaratmırıq.

References

Translate »