ਦਿੱਤੀ ਰਕਮ ਦੇ ਨਾਲ ਉਪਨਗਰੀ ਲੱਭੋ (ਨਕਾਰਾਤਮਕ ਨੰਬਰ ਹੈਂਡਲ ਕਰੋ)


ਮੁਸ਼ਕਲ ਪੱਧਰ ਦਰਮਿਆਨੇ
ਅਕਸਰ ਪੁੱਛਿਆ ਜਾਂਦਾ ਹੈ ਐਮਾਜ਼ਾਨ ਕੂਪਨਡਨੀਆ ਦਿੱਲੀ ਵਾਸੀ GE ਹੈਲਥਕੇਅਰ ਜਾਣਕਾਰੀ ਮੂਨਫ੍ਰਾਗ ਲੈਬਜ਼
ਅਰੇ ਹੈਸ਼ ਸਲਾਈਡਿੰਗ ਵਿੰਡੋ

ਸਮੱਸਿਆ ਦਿੱਤੀ ਗਈ ਰਕਮ ਦੇ ਨਾਲ ਉਪਨਗਰ ਲੱਭੋ (ਨਕਾਰਾਤਮਕ ਨੰਬਰਾਂ ਨੂੰ ਹੈਂਡਲ ਕਰਦਾ ਹੈ) ਦੱਸਦਾ ਹੈ ਕਿ ਤੁਹਾਨੂੰ ਇੱਕ ਪੂਰਨ ਅੰਕ ਐਰੇ, ਜਿਸ ਵਿੱਚ ਨਕਾਰਾਤਮਕ ਪੂਰਨ ਅੰਕ ਅਤੇ ਇੱਕ ਨੰਬਰ "ਜੋੜ" ਹੁੰਦਾ ਹੈ. ਸਮੱਸਿਆ ਦਾ ਬਿਆਨ ਉਪ-ਐਰੇ ਨੂੰ ਪ੍ਰਿੰਟ ਕਰਨ ਲਈ ਕਹਿੰਦਾ ਹੈ, ਜਿਹੜੀ "ਜੋੜ" ਕਹਿੰਦੇ ਹਨ, ਇੱਕ ਦਿੱਤੀ ਗਈ ਸੰਖਿਆ ਤੱਕ ਦਾ ਬਣਦੀ ਹੈ. ਜੇ ਇਕ ਤੋਂ ਵੱਧ ਸਬ-ਐਰੇ ਸਾਡੇ ਆਉਟਪੁੱਟ ਦੇ ਰੂਪ ਵਿਚ ਮੌਜੂਦ ਹਨ, ਤਾਂ ਉਨ੍ਹਾਂ ਵਿਚੋਂ ਕਿਸੇ ਨੂੰ ਵੀ ਪ੍ਰਿੰਟ ਕਰੋ.

ਉਦਾਹਰਨ

ਦਿੱਤੀ ਰਕਮ ਦੇ ਨਾਲ ਉਪਨਗਰੀ ਲੱਭੋ (ਨਕਾਰਾਤਮਕ ਨੰਬਰ ਹੈਂਡਲ ਕਰੋ)

arr[] = {2,4,-2,3,1}
sum = 1
Sum found between index 2 to index 3
arr[] = {12,10,-20,30,1}
sum = 20
Sum found between index 1 to index 3
arr[] = {2,4,-2,3,1}
sum = -1
No such sub-array exists.

ਐਲਗੋਰਿਥਮ

  1. ਘੋਸ਼ਣਾ ਏ ਫੋਲਡਰ ਨੂੰ.
  2. ਸੈੱਟ ਕਰੋ ਵਰਤਮਾਨ ਸੂਮ 0 ਤੱਕ
  3. ਐਰੇ ਨੂੰ ਪਾਰ ਕਰੋ, ਜਦੋਂ ਕਿ ਮੈਂ <ਐਨ,
    1. ਕਰੰਟਸਮ ਅਤੇ ਐਰੇ ਐਲੀਮੈਂਟ ਦਾ ਮੁੱਲ ਜੋੜਦਾ ਹੈ ਅਤੇ ਇਸ ਨੂੰ ਕਰੰਟਸਮ ਵਿੱਚ ਸਟੋਰ ਕਰਦਾ ਹੈ.
    2. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਕਰੰਟਸਮ ਜੋੜ ਦੇ ਬਰਾਬਰ ਹੈ.
      • ਜੇ ਇਹ ਸਹੀ ਹੈ, ਤਾਂ ਇੰਡੈਕਸ ਨੂੰ 0 ਤੋਂ i ਦੇ ਤੌਰ ਤੇ ਪ੍ਰਿੰਟ ਕਰੋ ਅਤੇ ਤੋੜੋ.
    3. ਜਾਂਚ ਕਰੋ ਕਿ ਕੀ ਨਕਸ਼ੇ ਵਿੱਚ ਮੌਜੂਦਾ ਕਰੰਟ-ਜੋੜ ਦਾ ਮੁੱਲ ਹੈ.
      • ਜੇ ਸਹੀ ਹੈ ਤਾਂ ਤਤਕਰਾ ਨੂੰ ਨਕਸ਼ਾ ਦੇ ਮੌਜੂਦਾ ਸਮ ਮੁੱਲ ਵਜੋਂ i ਅਤੇ ਬਰੇਕ ਤੇ ਛਾਪੋ.
    4. ਜੇ ਦਿੱਤੀ ਗਈ ਸ਼ਰਤ ਵਿਚੋਂ ਕੋਈ ਵੀ ਸੰਤੁਸ਼ਟ ਨਹੀਂ ਹੁੰਦਾ, ਇਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਸਾਨੂੰ ਦਿੱਤੀ ਰਕਮ ਨਾਲ ਕੁਝ ਨਹੀਂ ਮਿਲਿਆ.

ਕਥਾ

ਸਾਨੂੰ ਇੱਕ ਸਮੱਸਿਆ ਬਿਆਨ ਦਿੱਤਾ ਜਾਂਦਾ ਹੈ ਜਿਸ ਵਿੱਚ ਉਪ-ਐਰੇ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ ਕਿਹਾ ਜਾਂਦਾ ਹੈ ਜੋ ਦਿੱਤੀ ਰਕਮ ਦੇ ਅਨੁਸਾਰ ਬਣਦੀ ਹੈ ਅਤੇ ਜੇ ਇੱਕ ਤੋਂ ਵੱਧ ਉਪ-ਐਰੇ ਮਿਲੀਆਂ ਹਨ, ਤਾਂ ਉਹਨਾਂ ਵਿੱਚੋਂ ਕਿਸੇ ਨੂੰ ਵੀ ਪ੍ਰਿੰਟ ਕਰੋ. ਅਸੀਂ ਵਰਤਣ ਜਾ ਰਹੇ ਹਾਂ ਹੈਸ਼ਮੈਪ ਅਤੇ ਅਸੀ ਮੁੱਲ ਨੂੰ ਸਟੋਰ ਕਰਨ ਜਾ ਰਹੇ ਹਾਂ ਵਰਤਮਾਨ ਸੂਮ ਅਤੇ ਇਸ ਦਾ ਸੂਚਕਾਂਕ ਜੇ ਦੇ ਹਰੇਕ ਤੱਤ ਨੂੰ ਜੋੜਨ ਤੋਂ ਬਾਅਦ ਕੋਈ ਵੀ ਸ਼ਰਤਾਂ ਪੂਰੀਆਂ ਨਹੀਂ ਹੁੰਦੀਆਂ ਐਰੇ ਅਤੇ ਕਰੰਟਸਮ (ਜੋ ਕਿ ਪਹਿਲਾਂ 0 ਵਾਂਗ ਸ਼ੁਰੂ ਹੋਇਆ ਸੀ).

ਆਓ ਇੱਕ ਉਦਾਹਰਣ ਤੇ ਵਿਚਾਰ ਕਰੀਏ:

ਉਦਾਹਰਨ

ਐਰ [] = {14, 1, -10, 20, 1}, ਜੋੜ = 5

ਅਸੀਂ ਇਕ ਪੂਰਨ ਅੰਕ ਲੜੀ ਦਿੱਤੀ ਹੈ ਜਿਸ ਵਿਚ ਕੁਝ ਨਕਾਰਾਤਮਕ ਪੂਰਨ ਅੰਕ ਅਤੇ ਇਕ ਸੰਖਿਆ ਜੋੜ ਸ਼ਾਮਲ ਹੈ. ਸਾਨੂੰ ਉਪ-ਐਰੇ ਦਾ ਪਤਾ ਲਗਾਉਣਾ ਹੈ ਜੋ ਦਿੱਤੀ ਗਈ ਸੰਖਿਆ, ਜੋੜ ਨੂੰ ਜੋੜਦਾ ਹੈ. ਸਾਰੀ ਐਰੇ ਨੂੰ ਟ੍ਰੈਵਲ ਕਰਦੇ ਸਮੇਂ ਸਾਨੂੰ ਆਪਣਾ ਵਰਤਮਾਨ ਸਮਾਲ ਰੱਖਣਾ ਚਾਹੀਦਾ ਹੈ, ਇਹ ਉਹ ਹੈ ਜੋ ਸਾਨੂੰ ਸੰਭਵ ਸਬ-ਐਰੇ ਦਿੰਦਾ ਹੈ.

i = 0, ਮੌਜੂਦਾਸਮ = 0

ਕਰੰਟਸਮ = ਕਰੰਟਸਮ + ਐਰ [i] => ਕਰੰਟਸਮ = 14, ਹੁਣ ਸਾਡੇ ਕੋਲ ਸਾਡੇ ਕਰੰਟਸਮ ਵਿੱਚ 14 ਹਨ, ਅਸੀਂ ਜਾਂਚ ਕਰਾਂਗੇ ਕਿ ਕੀ ਇਹ ਦਿੱਤੀ ਰਕਮ ਦੇ ਬਰਾਬਰ ਹੈ ਜੋ 5 ਹੈ, ਅਤੇ ਇਹ ਗਲਤ ਹੈ, ਫਿਰ ਅਸੀਂ ਜਾਂਚ ਕਰਾਂਗੇ ਕਿ ਕੀ ਮੈਪ ਵਿੱਚ ਸ਼ਾਮਲ ਹੈ ਜਾਂ ਨਹੀਂ ਕਰੰਟਸਮ-ਰਕਮ ਦਾ ਅਰਥ ਹੈ ਕਿ 14-5 = 9 ਵੀ ਗਲਤ ਹੈ. ਇਸ ਲਈ ਅਸੀਂ ਅਗਲੇ ਤੱਤ ਵਿਚੋਂ ਲੰਘਾਂਗੇ. ਇਸ ਲਈ ਅਸੀਂ ਨਕਸ਼ੇ ਵਿਚ ਕਰੰਟਸਮ ਅਤੇ i ਜੋੜਦੇ ਹਾਂ.

i = 1, ਮੌਜੂਦਾਸਮ = 14

ਕਰੰਟਸਮ = ਕਰੰਟਸਮ + ਐਰ [i] => 14 + 1 = 15, ਕਰੰਟਸਮ = 15, ਹੁਣ ਸਾਡੇ ਕੋਲ ਸਾਡੇ ਕਰੰਟਸਮ ਵਿੱਚ 15 ਹਨ, ਅਸੀਂ ਜਾਂਚ ਕਰਾਂਗੇ ਕਿ ਇਹ ਦਿੱਤੀ ਰਕਮ ਦੇ ਬਰਾਬਰ ਹੈ ਪਰ ਇਹ ਸੰਤੁਸ਼ਟ ਨਹੀਂ ਹੈ, ਅਸੀਂ ਜਾਵਾਂਗੇ ਜੇ ਨਕਸ਼ੇ ਵਿੱਚ ਕਰੰਟ-ਸਮ-ਜੋੜ ਹੈ ਜੋ 15-5-10 ਹੈ ਇਹ ਵੀ ਗਲਤ ਹੈ. ਇਸ ਲਈ ਅਸੀਂ ਨਕਸ਼ੇ ਵਿਚ ਕਰੰਟਸਮ ਅਤੇ i ਜੋੜਦੇ ਹਾਂ.

i = 2, ਮੌਜੂਦਾਸਮ = 15,

ਕਰੰਟਸਮ = ਕਰੰਟਸਮ + ਐਰ [i] => 15 + (-10), ਕਰੰਟਸਮ = 5, ਹੁਣ ਸਾਡੇ ਕੋਲ ਸਾਡੇ ਕਰੰਟਸਮ ਵਿੱਚ 15 ਹਨ, ਅਸੀਂ ਜਾਂਚ ਕਰਾਂਗੇ ਕਿ ਇਹ ਦਿੱਤੀ ਰਕਮ ਦੇ ਬਰਾਬਰ ਹੈ ਜੋ 5 ਹੈ, ਅਤੇ ਅਸੀਂ ਪਾਇਆ ਕਿ ਸਥਿਤੀ ਸੰਤੁਸ਼ਟ ਹੈ, ਮਤਲਬ ਕਿ ਸਾਨੂੰ ਆਪਣਾ ਆਉਟਪੁਟ ਮਿਲ ਗਿਆ, ਫਿਰ ਅਸੀਂ ਸੂਬਰੇ 0 ਤੋਂ i ਦੇ ਇੰਡੈਕਸ ਪ੍ਰਿੰਟ ਕਰਾਂਗੇ.

ਕੋਡ

ਸੀ ++ ਕੋਡ ਨੂੰ ਦਿੱਤੀ ਗਈ ਰਕਮ ਦੇ ਨਾਲ ਉਪਨਗਰੀ ਲੱਭਣ ਲਈ (ਨਕਾਰਾਤਮਕ ਨੰਬਰਾਂ ਨੂੰ ਸੰਭਾਲਦਾ ਹੈ)

#include<iostream>
#include<unordered_map>

using namespace std;

void getSubArray(int arr[], int n, int sum)
{
    unordered_map<int, int> map;
    int currentSum = 0;
    for (int i = 0; i < n; i++)
    {
        currentSum = currentSum + arr[i];
        if (currentSum == sum)
        {
            cout << "Sum found between index "<< 0 << " to index " << i << endl;
            return;
        }
        if (map.find(currentSum - sum) != map.end())
        {
            cout << "Sum found between index "<< map[currentSum - sum] + 1 << " to index " << i << endl;
            return;
        }
        map[currentSum] = i;
    }
    cout << " No such sub-array exists ";
}
int main()
{
    int arr[] = {14, 1, -10, 20, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    int sum = 5;
    getSubArray(arr, n, sum);
    return 0;
}
Sum found between index 0 to index 2

ਜਾਵਾ ਕੋਡ ਨੂੰ ਦਿੱਤੀ ਗਈ ਰਕਮ ਦੇ ਨਾਲ ਸੁਬਰੇਅਰ ਲੱਭਣ ਲਈ (ਨਕਾਰਾਤਮਕ ਸੰਖਿਆ ਹੈਂਡਲ)

import java.util.HashMap;

class printSubArraywithGivenSum
{
    public static void getSubArray(int[] arr, int n, int sum)
    {
        int currentSum = 0;
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; i++)
        {
            currentSum = currentSum + arr[i];
            if (currentSum - sum == 0)
            {
                System.out.println("Sum found between index "+ 0 + " to index " + i);
                return;
            }
            if (map.containsKey(currentSum - sum))
            {
                int val=map.get(currentSum-sum)+1;
                System.out.println("Sum found between index "+ val+" to index " + i);
                return;
            }
            map.put(currentSum, i);
        }
        System.out.println("No such sub-array exists");
    }
    public static void main(String[] args)
    {
        int[] arr = {14, 1, -10, -20, 2};
        int n = arr.length;
        int sum = 5;
        getSubArray(arr, n, sum);
    }
}
Sum found between index 0 to index 2

ਜਟਿਲਤਾ ਵਿਸ਼ਲੇਸ਼ਣ

ਟਾਈਮ ਜਟਿਲਤਾ

ਓ (ਐਨ) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ.

ਸਪੇਸ ਦੀ ਜਟਿਲਤਾ

ਓ (ਐਨ) ਜਿੱਥੇ ਕਿ “ਐਨ” ਐਰੇ ਵਿਚਲੇ ਤੱਤਾਂ ਦੀ ਗਿਣਤੀ ਹੈ.