ఇచ్చిన మొత్తంతో సుబారే  


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది Adobe అమెజాన్ అమెరికన్ ఎక్స్ప్రెస్ ఆపిల్ బ్లూమ్బెర్గ్ ByteDance కూపాంగ్ eBay <span style="font-family: Mandali; ">ఫేస్‌బుక్ </span> గోల్డ్మన్ సాచ్స్ గూగుల్ లింక్డ్ఇన్ మైక్రోసాఫ్ట్ ఒరాకిల్ క్యూరా Twilio ఉబెర్ విష్ యాహూ Yandex
అర్రే హాష్ హ్యాషింగ్

సమస్యల నివేదిక  

ఇచ్చిన మొత్తం సమస్యతో సబ్రేలో, మేము ఒక ఇచ్చాము అమరిక n సానుకూల అంశాలను కలిగి ఉంటుంది. మేము ఇచ్చిన సబ్‌రేను కనుగొనవలసి ఉంది, దీనిలో సబ్‌రే యొక్క అన్ని మూలకాల మొత్తం ఇచ్చిన_సమ్‌కు సమానం. శ్రేణి యొక్క ప్రారంభ లేదా ముగింపు నుండి కొన్ని అంశాలను తొలగించడం ద్వారా అసలు శ్రేణి నుండి సుబారే పొందబడుతుంది.

ఉదాహరణ  

a. ఇన్‌పుట్ శ్రేణి ఇలా ఉంటుంది: [1, 3, 7, 9, 11, 15, 8, 6]

మొత్తం = 19
అవుట్‌పుట్ ఉంటుంది: 1 మరియు 3 → [3, 7, 9], సబ్‌రే మొత్తం = 19

బి. ఇన్‌పుట్ శ్రేణి ఇలా ఉంటుంది: [1, 3, 7, 9, 11, 15, 8, 6]

మొత్తం = 20
అవుట్పుట్ ఉంటుంది: 0 మరియు 3 → [1, 3, 7, 9], సబ్‌రేరే మొత్తం = 20

సి. ఇన్‌పుట్ శ్రేణి ఇలా ఉంటుంది: [1, 3, 7, 9, 11, 15, 8, 6]

మొత్తం = 40
అవుట్‌పుట్ ఉంటుంది: ఇచ్చిన మొత్తంతో సబ్‌రే కనుగొనబడలేదు.

d. ఇన్‌పుట్ శ్రేణి ఇలా ఉంటుంది: [4, 3, 2, 8, 9, 11]

మొత్తం = 8
అవుట్పుట్ ఉంటుంది: 3 మరియు 3 → [8], సబ్‌రే మొత్తం = 8

అప్రోచ్ 1  

అల్గారిథం

అన్ని సబ్‌రేలను పరిగణించండి మరియు ప్రతి సబ్‌రే యొక్క మొత్తాన్ని తనిఖీ చేయండి.

  1. రెండు ఉచ్చులు అమలు చేయండి.
  2. Outer టర్ లూప్ ప్రారంభ సూచికను చిత్రీకరిస్తుంది.
  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  

అల్గారిథం

సబ్‌రే మొత్తాన్ని సృష్టించండి ఫంక్షన్ ఇది శ్రేణి మరియు మొత్తాన్ని వాదనగా తీసుకుంటుంది మరియు ఇచ్చిన మొత్తంతో సబ్‌రే యొక్క ప్రారంభ మరియు ముగింపు సూచికలను ఇస్తుంది.

  1. మొదట ప్రస్తుత_సమ్‌ను శ్రేణి యొక్క మొదటి మూలకంగా ప్రారంభించండి మరియు ప్రారంభ సూచికను 0 గా నిల్వ చేయండి.
  2. ప్రస్తుత_సమ్ మొత్తాన్ని మించి ఉంటే, స్టార్టింగ్ ఎలిమెంట్ మరియు ఇంక్రిమెంట్ స్టార్ట్ ఇండెక్స్ తొలగించండి.
  3. ప్రస్తుత_సమ్ మొత్తానికి సమానం అయితే ప్రారంభ మరియు ముగింపు సూచికలను తిరిగి ఇస్తుంది.
  4. ప్రస్తుత_సమ్‌కు మూలకాలను ఒక్కొక్కటిగా జోడించండి.
  5. లూప్ ముగిస్తే, “ఇచ్చిన_సమ్‌తో సబ్‌రే కనుగొనబడలేదు.”

ఇచ్చిన మొత్తంతో సుబారే కోసం అమలు

సి ++ ప్రోగ్రామ్

#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 అనేది ఇచ్చిన శ్రేణి యొక్క పరిమాణం. ఇక్కడ మేము శ్రేణిని ఒక సారి ప్రయాణించి పరిస్థితుల కోసం తనిఖీ చేస్తాము.

ఇది కూడ చూడు
ఆపరేటింగ్ సిస్టమ్స్‌లో పేజీ పున lace స్థాపన అల్గోరిథంలు

అంతరిక్ష సంక్లిష్టత

O (1) ఎందుకంటే మేము ఇక్కడ ఏ సహాయక స్థలాన్ని ఉపయోగించము.

ప్రస్తావనలు