دی گئی رقم کے ساتھ سبابرے


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایڈوب ایمیزون امریکن ایکسپریس ایپل بلومبرگ ByteDance کوپنگ ای بے فیس بک گولڈمین سیکس گوگل لنکڈ مائیکروسافٹ اوریکل کوئرا Twilio Uber چاہتے ہیں یاہو Yandex
لڑی ہیش ہیکنگ

مسئلہ یہ بیان

صابرے میں دیئے گئے دشواری کے مسئلہ میں ، ہم نے ایک دیا ہے صف ن مثبت عنصر پر مشتمل ہمیں وہ سبیارے ڈھونڈنا ہے جس میں سبیارے کے تمام عناصر کا مجموعہ دیئے گئے_سوم کے برابر ہے۔ سرے کے آغاز یا اختتام سے کچھ عناصر کو حذف کرکے سبریے اصل صف سے حاصل کیا جاتا ہے۔

مثال کے طور پر

a. ان پٹ صف: [1 ، 3 ، 7 ، 9 ، 11 ، 15 ، 8 ، 6]

رقم = 19
آؤٹ پٹ ہوگی: 1 اور 3 → [3، 7، 9]، subarray sum = 19

b. ان پٹ صف: [1 ، 3 ، 7 ، 9 ، 11 ، 15 ، 8 ، 6]

رقم = 20
آؤٹ پٹ ہوگا: 0 اور 3 → [1، 3، 7، 9]، سبری رے = 20

c ان پٹ صف: [1 ، 3 ، 7 ، 9 ، 11 ، 15 ، 8 ، 6]

رقم = 40
آؤٹ پٹ ہوگا: دی گئی رقم کے ساتھ کوئی subarray نہیں ملا۔

d. ان پٹ صف: [4 ، 3 ، 2 ، 8 ، 9 ، 11]

رقم = 8
آؤٹ پٹ ہوگی: 3 اور 3 8 [8]، سبریی جوڑ = XNUMX

نقطہ نظر 1

الگورتھم

تمام subarrays پر غور کریں اور ہر subarray کی رقم چیک کریں.

  1. دو لوپ چلائیں۔
  2. بیرونی لوپ تصویر ابتدائیہ انڈیکس۔
  3. اندرونی لوپ تمام سبریوں کو تلاش کرتا ہے اور اس کی رقم تلاش کرتا ہے۔
  4. اگر مجموعہ = موجودہ_سم ، کرنٹ_سم موجودہ سبری ، پرنٹ اسٹارٹ ، اور انڈیکس انڈیکس کا مجموعہ ہے۔

عمل

سی ++ پروگرام برائے ضمنی کے ساتھ دی گئی رقم

#include <bits/stdc++.h>
using namespace std;
int SubarraySum(int array[], int N, int sum)
{
    int current_sum, i, j;
    //i is start point and j - 1 is end point
    for (i = 0; i < N; i++)
    {
        current_sum = array[i];
        for (j = i+1; j < N + 1; j++)
        {
            if (current_sum == sum)
            {
                cout<<"Subarray with given sum is between indexes "<<i<<" and "<<j-1<<endl; 
                return 1;
            }
            else if (current_sum > sum)
            {
                break;
            }
           current_sum = current_sum + array[j];
        }
    }
    cout<<"No subarray found with given sum"<<endl;
    return 0;
}
 
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sum;
    cin>>sum;
    SubarraySum(a,n,sum);
    return 0;
}

جاوا پروگرام سبابرے کے لئے دی گئی سم کے ساتھ

import java.util.Scanner;
class sum
{
    public static int SubarraySum(int array[], int N, int sum)
    {
        int current_sum, i, j;
        //i is start point and j - 1 is end point
        for (i = 0; i < N; i++)
        {
            current_sum = array[i];
            for (j = i+1; j < N + 1; j++)
            {
                if (current_sum == sum)
                {
                    System.out.println("Subarray with given sum is between indexes " + i + " and " + (j-1)); 
                    return 1;
                }
                else if (current_sum > sum)
                {
                    break;
                }
               current_sum = current_sum + array[j];
            }
        }
        System.out.println("No subarray found with given sum");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum;
        sum = sr.nextInt();
        SubarraySum(a,n,sum);
    }
}
8
1 3 8 9 11 13 17 21
28
Subarray with given sum is between indexes 2 and 4

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (n * n) جہاں n دیئے گئے صفوں کا سائز ہے۔ یہاں ہم سباری کے نقطہ اغاز (i) کو ٹھیک کرتے ہیں اور j میں اختتام پذیر ہونے والے تمام ممکنہ سبری کے مجموعے کا حساب لگاتے ہیں۔

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

O (1) کیونکہ ہم یہاں کوئی معاون جگہ استعمال نہیں کرتے ہیں۔

نقطہ نظر 2

الگورتھم

ایک subarray رقم بنائیں تقریب جو ایک معقول دلیل کے طور پر سرنی اور رقم کو لیتا ہے اور دیئے گئے جوڑے کے ساتھ سباری کے آغاز اور اختتامی اشاریے دیتا ہے۔

  1. پہلے کرین کے پہلے عنصر کے طور پر کرنٹ_سم کو شروع کریں اور اسٹارٹ اسٹارٹ انڈیکس کو 0 کے طور پر اسٹور کریں
  2. اگر کرنٹ_سم رقم سے زیادہ ہے تو ، ستارہ عناصر اور انکریمنٹ اسٹارٹ انڈیکس کو ہٹا دیں۔
  3. اگر کرنٹ_سم برابر کے برابر ہے تو پھر اسٹارٹ اور اختتامی اشاریہ جات کو لوٹاتا ہے۔
  4. ایک ایک کرکے کرنٹ_سم میں عناصر شامل کریں۔
  5. اگر لوپ ختم ہوجاتا ہے تو پھر پرنٹ کریں "عطا کردہ_سنم کے ساتھ کوئی subarray نہیں ملا۔"

دی گئی رقم کے ساتھ سبابرے کے لئے عمل درآمد

سی ++ پروگرام

#include <bits/stdc++.h>
using namespace std;
int SubarrySum(int array[], int n, int sum)
{
    //Initialize current_sum = first element.Therefore, start_index =0
    int current_sum = array[0];
    int start_index = 0;
    
    //if current_sum > sum remove last element
    for(int i = 1; i <= n; i++)
    {
        while(current_sum > sum && start_index < i-1)
        {
            current_sum = current_sum - array[start_index];
            start_index++;
        }
        if(current_sum == sum)
        {
            cout<<"Subarray with given sum is between indexes "<<start_index<<" and "<<i-1<<endl;
            return 1;
        }
        //Add current element to current_sum
        if(i < n)
        {
          current_sum = current_sum + array[i];
        }
    }
    cout<<"No subarray found with given sum"<<endl;
    return 0;
}
 
//Main function
int main()
{
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    int sum;
    cin>>sum;
    SubarrySum(a,n,sum);
    return 0;
}

جاوا پروگرام

import java.util.Scanner;
class sum
{
    public static int SubarraySum(int array[], int n, int sum)
    {
            //Initialize current_sum = first element.Therefore, start_index =0
        int current_sum = array[0];
        int start_index = 0;

        //if current_sum > sum remove last element
        for(int i = 1; i <= n; i++)
        {
            while(current_sum > sum && start_index < i-1)
            {
                current_sum = current_sum - array[start_index];
                start_index++;
            }
            if(current_sum == sum)
            {
                System.out.println("Subarray with given sum is between indexes " + start_index + " and " + (i-1)); 
                return 1;
            }
            //Add current element to current_sum
            if(i < n)
            {
              current_sum = current_sum + array[i];
            }
        }
        System.out.println("No subarray found with given sum");
        return 0;
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        int sum;
        sum = sr.nextInt();
        SubarraySum(a,n,sum);
    }
}
6
10 6 8 4 3 8
34
No subarray found with given sum

پیچیدگی کا تجزیہ

وقت کی پیچیدگی

O (n * n) جہاں n دیئے گئے صفوں کا سائز ہے۔ یہاں ہم ایک بار صف کو عبور کرتے ہیں اور حالات کا جائزہ لیتے ہیں۔

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

O (1) کیونکہ ہم یہاں کوئی معاون جگہ استعمال نہیں کرتے ہیں۔

حوالہ جات