দুটি সংখ্যার মধ্যে সর্বনিম্ন দূরত্ব নির্ণয় করুন  


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় কুপনডুনিয়া Coursera Delhivery মুনফ্রোগ ল্যাব পেপ্যাল Paytm Snapchat
বিন্যাস

সমস্যা বিবৃতি  

আপনি একটি অ্যারের এবং দুটি এবং x এবং y নাম্বার দিয়েছেন। সমস্যা "দুটি সংখ্যার মধ্যে ন্যূনতম দূরত্বটি সন্ধান করুন" তাদের মধ্যে ন্যূনতম সম্ভাব্য দূরত্বটি জানতে চাইতে। প্রদত্ত অ্যারেতে সাধারণ উপাদান থাকতে পারে। আপনি ধরে নিতে পারেন যে এক্স এবং y উভয়ই আলাদা।

উদাহরণ  

arr[] = {1, 3, 2, 5, 8, 2, 5, 1}

x = 2

y=8
1

ব্যাখ্যা: 2 সূচকগুলি 2 এবং 5 হয় এবং 8 এর সূচক 4 হয়, সুতরাং আমরা সূচকটি গ্রহণ করি যা দুটি প্রদত্ত সংখ্যার মধ্যে সর্বনিম্ন দূরত্বকে গণনা করে।

arr[] = {1, 3, 2, 5, 8, 2, 5, 1}

x = 3

y=5
2

ব্যাখ্যা: 3 এর সূচক 1 এবং 5 এর সূচক 3. সুতরাং তাদের উভয়ের মধ্যে সর্বনিম্ন দূরত্ব 3-1 = 2।

arr[] = {2, 4, 6, 8, 2, 5, 0, 56}

x = 6

y=5
3

ব্যাখ্যা: 6 এর সূচক 2 এবং 5 এর সূচক 5, সুতরাং উভয়ের মধ্যে সর্বনিম্ন দূরত্ব 5-2 = 3 হয়।

দুটি সংখ্যার মধ্যে সর্বনিম্ন দূরত্ব নির্ধারণের জন্য অ্যালগরিদম  

1. Set flag to -1 and output to the Maximum value of an Integer.
2. Traverse the array from i = 0 to i < n.
    1. Check if the array element is either equal to x or equal to y.
    2. Check if flag is not equal to i and arr[i] is not equal to arr[flag].
        1. If the condition is true, then find out the minimum between the output and i - flag.
3. Return output.

ব্যাখ্যা

আমরা একটি দিয়েছি বিন্যাস পূর্ণসংখ্যা এবং দুটি সংখ্যার x এবং y বলে numbers আমাদের দুটি প্রদত্ত সংখ্যার মধ্যে নূন্যতম দূরত্বটি খুঁজে বের করতে হবে, x এবং y। সর্বনিম্ন দূরত্ব জানতে আমরা দুটি সংখ্যা জোড় পরীক্ষা করব। আমাদের দেওয়া নম্বরটি, আমরা কেবল ট্র্যাভারসাল চলাকালীন তাদের জন্য পরীক্ষা করব। আমরা দুটি সংখ্যার একটির জন্য অনুসন্ধান করব, অ্যারের বর্তমান উপাদানটির সাথে মেলে। যদি এটি সত্য বলে প্রমাণিত হয় তবে আমরা এটি পরীক্ষা করব যে এটি পুনরাবৃত্তিকারী উপাদান বা একই উপাদান নয়। সমস্ত শর্ত যদি সত্য হিসাবে পাওয়া যায় তবে আমরা কেবল আউটপুট মানটি আপডেট করব।

আরো দেখুন
প্রদত্ত রেঞ্জগুলিতে এমনকি বা বিজোড় সংখ্যার সম্ভাবনা সম্পর্কিত প্রশ্নগুলি

বর্তমান অ্যারে উপাদানগুলির যে কোনও একটি x বা y এর সমান এবং সূচকগুলির একই শর্ত এবং একই উপাদানগুলি মিথ্যা হয়ে গেছে। তারপরে আমরা কেবল পতাকাটি আপডেট করব এবং বর্তমান উপাদান সূচকে পতাকাটিতে সংরক্ষণ করব। আসুন একটি উদাহরণ বিবেচনা করুন এবং এটি একবার দেখুন:

উদাহরণ

অ্যার [] = {1, 3, 2, 5, 8, 2, 5, 1}, এক্স = 2, y = 8

আউটপুট = একটি পূর্ণসংখ্যার সর্বোচ্চ মান, পতাকা = - 1

আমরা দুটি সংখ্যা x = 2 এবং y = 8 দিয়েছি

  • i = 0, আমরা যাচাই করবো যদি আরার [i] 2 বা আরার সমান হয় [i] 8 এর সমান হয় তবে শর্তটি সন্তুষ্ট হয় না।

শর্তটি সন্তুষ্ট হয় যখন আমি = 2।

  • i = 2, আরার [i] 2 এর সমান।

আমরা পতাকাটি যাচাই করব এবং এটি মিথ্যা কারণ পতাকাটি এখনও -1 রয়েছে। সুতরাং এটি প্রবেশ করে না, আমরা কেবল পতাকা = 2 হিসাবে পতাকা আপডেট করব।

  • পরবর্তী বাছাই, যখন আমি = 4, আরার [i] = 8, পতাকা -1 এর সমান হয় না এবং এছাড়াও তীর [i] আরার [পতাকা] এর সমান হয় না। আমরা এই শর্তটি পরীক্ষা করছি যাতে আমরা আবার একই নম্বরটি খুঁজে না পাই এবং এর দূরত্ব পাব।

সুতরাং এখন আমরা আউটপুটটি = 4 - 2 = 2 হিসাবে আপডেট করব এবং ফ্ল্যাগ = 4 আপডেটও করব

  • আবার i = 5 এ, অ্যারে [i] = 2 এ, আমরা শর্তটি সত্য দেখতে পাব এবং পতাকাটিও -1 এর সমান নয় এবং আরর [i] আরার [পতাকা] এর সমান নয়, তাই আমরা আবার আউটপুট আপডেট করব সর্বনিম্ন মিনিট (4, 5-4) এবং 1 এর মধ্যে আউটপুট আপডেট হবে।

সুতরাং এখন অ্যারে উপাদান অ্যারের মধ্যে আমাদের নূন্যতম দূরত্ব 1 [4] = 8 এবং অ্যারের [5] = 2।

আরো দেখুন
সর্বাধিক আকারের subarray যোগফল কে

আউটপুট = 1।

দুটি সংখ্যার মধ্যে সর্বনিম্ন দূরত্ব নির্ণয় করুন

কোড  

দুটি সংখ্যার মধ্যে সর্বনিম্ন দূরত্ব নির্ধারণের জন্য সি ++ কোড

#include<bits/stdc++.h>

using namespace std;

int getMinimumDistance(int arr[], int n, int x, int y)
{
    int flag=-1;
    int output=INT_MAX;

    for(int i = 0 ; i < n ; i++)
    {
        if(arr[i] ==x || arr[i] == y)
        {
            if(flag != -1 && arr[i] != arr[flag])
            {
                output = min(output,i-flag);
            }

            flag=i;
        }
    }
    if(output==INT_MAX)
        return -1;

    return output;
}

int main()
{
    int arr[] = {1, 3, 2, 5, 8, 2, 5, 1};
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 2;
    int y = 8;

    cout << "Minimum possible distance between " << x <<" and " << y << " : "<<getMinimumDistance(arr, n, x, y);
    return 0;
}
Minimum possible distance between 2 and 8 : 1

দুটি সংখ্যার মধ্যে সর্বনিম্ন দূরত্বের জন্য জাভা কোড

class MinimumDistanceBwNumbers
{
    public static int getMinimumDistance(int arr[], int n, int x, int y)
    {
        int flag=-1;
        int output=Integer.MAX_VALUE;

        for(int i = 0 ; i < n ; i++)
        {
            if(arr[i] ==x || arr[i] == y)
            {
                if(flag != -1 && arr[i] != arr[flag])
                {
                    output = Math.min(output,i-flag);
                }

                flag=i;
            }
        }
        if(output==Integer.MAX_VALUE)
            return -1;

        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1, 3, 2, 5, 8, 2, 5, 1};
        int n = arr.length;
        int x = 2;
        int y = 8;

        System.out.println("Minimum possible distance between " + x + " and " + y + ": " + getMinimumDistance(arr, n, x, y));
    }
}
Minimum possible distance between 2 and 8: 1

জটিলতা বিশ্লেষণ  

সময় জটিলতা

একক ট্র্যাভারসাল অলগরিদমকে রৈখিক সময়ের জটিলতায় চালিত করে। উপর) কোথায় "এন" অ্যারেতে উপাদানগুলির সংখ্যা।

স্পেস জটিলতা ity

চালু) স্থান জটিলতা যেহেতু আমরা ইনপুট সংরক্ষণের জন্য একটি অ্যারে ব্যবহার করি। তবে সর্বনিম্ন দূরত্বটি খুঁজতে অ্যালগরিদমের জন্য ও (1) অতিরিক্ত স্থান প্রয়োজন requires