0 തുകയുള്ള ഒരു സബ്‌റേ ഉണ്ടോയെന്ന് കണ്ടെത്തുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ക്സെൻ ഡി.ഇ.ഷാ ഗോൾഡ്മാൻ സാക്സ് തീർച്ചയായും MakeMyTrip OYO മുറികൾ Paytm ടിസിഎസ്
അറേ ഹാഷ്

“0 സംഖ്യയുള്ള ഒരു സബ്‌റേ ഉണ്ടോയെന്ന് കണ്ടെത്തുക” എന്ന പ്രശ്‌നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു പൂർണ്ണസംഖ്യ ശ്രേണി നെഗറ്റീവ് സംഖ്യകളും അടങ്ങിയിരിക്കുന്നു. കുറഞ്ഞത് 1 എങ്കിലും വലുപ്പമുള്ള ഏതെങ്കിലും ഉപ-അറേ ഉണ്ടോ എന്ന് നിർണ്ണയിക്കാൻ പ്രശ്ന പ്രസ്താവന ആവശ്യപ്പെടുന്നു. ഈ ഉപ-അറേയ്‌ക്ക് 1 ന് തുല്യമായ തുക ഉണ്ടായിരിക്കണം.

ഉദാഹരണം

0 തുകയുള്ള ഒരു സബ്‌റേ ഉണ്ടോയെന്ന് കണ്ടെത്തുക

arr[] = {2,1,-3,4,5}
yes

വിശദീകരണം

ഇവിടെ, സൂചിക 0 മുതൽ 2 വരെയുള്ള ഘടകങ്ങൾക്ക് ആകെ 0 ഉണ്ട്.

arr[] = {4,1,-4,5,1}
yes

വിശദീകരണം

തുക 0 ഉള്ള ഒരു ഉപ-അറേ നിലവിലില്ല.

അൽഗോരിതം

  1. ഒരു പ്രഖ്യാപിക്കുക ഗണം.
  2. ആരംഭിക്കുക തുക 0 ലേക്ക്.
  3. അതേസമയം, അറേയിലൂടെ സഞ്ചരിക്കുക i <n (അറേയുടെ ദൈർഘ്യം).
    1. Ar [i] ലേക്ക് തുക ചേർത്ത് തുകയായി സംഭരിക്കുക.
    2. ഇനിപ്പറയുന്ന നിബന്ധനകളിലേതെങ്കിലും ശരിയാണോയെന്ന് പരിശോധിക്കുക:
      1. sum == 0 / arr [i] == 0 / സെറ്റിൽ തുകയുടെ മൂല്യം അടങ്ങിയിട്ടുണ്ടെങ്കിൽ.
      2. ശരിയാണെങ്കിൽ, ശരിയിലേക്ക് മടങ്ങുക.
    3. സെറ്റിലേക്ക് തുക ചേർക്കുക.
  4. തെറ്റായി മടങ്ങുക.

വിശദീകരണം

0 ന് തുല്യമായ തുകയോടുകൂടി ഏതെങ്കിലും ഉപ-അറേ ഉണ്ടോ എന്ന് കണ്ടെത്താൻ ആവശ്യപ്പെടുന്ന ഒരു പ്രശ്ന പ്രസ്താവന ഞങ്ങൾക്ക് ലഭിച്ചു. ഇത് പരിഹരിക്കുന്നതിന് ഞങ്ങൾ ഈ പ്രശ്നം പരിഹരിക്കാൻ ഒരു സെറ്റ് ഉപയോഗിക്കും. തന്നിരിക്കുന്ന അറേയുടെ ഘടകങ്ങൾ ഞങ്ങൾ സെറ്റിലേക്ക് സംഭരിക്കാൻ പോകുന്നു. തുടർന്ന് ഒരേസമയം മൂല്യം തുകയിലേക്ക് ചേർത്ത് സെറ്റിലെ നിലവിലെ തുകയുമായി ഉപ-അറേയുടെ എന്തെങ്കിലും പൊരുത്തമുണ്ടോ അല്ലെങ്കിൽ തുക 0 ന് തുല്യമാണോ എന്ന് പരിശോധിക്കുക. സംഖ്യ 0 ഉള്ള ഒരു ഉപ-അറേ ഉണ്ടെന്ന് കണ്ടെത്തിയാൽ ഞങ്ങൾ മടങ്ങും ശരി.

ഉപ അറേകളിലൊന്നും സംഖ്യ 0 ഉണ്ടെന്ന് കണ്ടെത്തിയില്ലെങ്കിൽ, ഞങ്ങൾ ലൂപ്പിൽ നിന്ന് തെറ്റായി മടങ്ങാൻ പോകുന്നു. കൂടാതെ, ഒരു കാര്യമുണ്ട്, ഏതെങ്കിലും ഒരു മൂലകം 0 ആണെങ്കിൽ ഞങ്ങൾ ശരിയാകും, കാരണം ഒരു മൂലകം തന്നെ ഒരൊറ്റ മൂലകത്തിന്റെ ഉപ-അറേ ആണ്. അതിനാൽ അത്തരമൊരു ഉപ-അറേ ഞങ്ങൾ കണ്ടെത്തി എന്നാണ് ഇതിനർത്ഥം.

ഇവിടെ കോഡിൽ, ഞങ്ങൾ ഒരു ബൂളിയൻ ഫംഗ്ഷൻ പ്രഖ്യാപിക്കുന്നു, അത് ശരിയോ തെറ്റോ ആയിരിക്കും, ഉപ-അറേ കണ്ടെത്തിയാൽ അത് ശരിയാകും, അല്ലാത്തപക്ഷം അത് തെറ്റായി മടങ്ങും.

നമുക്ക് ഒരു ഉദാഹരണം നോക്കാം:

ഉദാഹരണം

arr [] = {- 3,2,1,9,6}

ഇവിടെ കോഡിൽ, ഞങ്ങൾ ഒരു അറേയിലൂടെ സഞ്ചരിച്ച് തുകയും അരയും ചേർത്ത് [i] സംഖ്യയായി സംഭരിക്കുകയും ആ പരിശോധനയ്ക്ക് ശേഷം തുക == 0 അല്ലെങ്കിൽ അറ [i] 0 ന് തുല്യമാണെങ്കിലോ സെറ്റിന്റെ തുകയുടെ മൂല്യം അടങ്ങിയിട്ടുണ്ടെങ്കിലോ തന്നിരിക്കുന്ന ഏതെങ്കിലും നിബന്ധന തൃപ്‌തികരമാണെങ്കിൽ, ഞങ്ങൾ ശരിയിലേക്ക് മടങ്ങുകയും തുടർന്ന് സെറ്റിലേക്ക് തുക ചേർക്കുകയും ചെയ്യും.

ഉപ-അറേകളൊന്നും കണ്ടെത്തിയില്ലെങ്കിൽ ഞങ്ങൾ തെറ്റായി മടങ്ങും.

തുക = 0, സജ്ജമാക്കുക = {}

i = 0, arr [i] = -3

sum = sum + arr [i] => 0 + - 3 = -3

sum == 0 അല്ലെങ്കിൽ arr [i] 0 ന് തുല്യമാണെങ്കിൽ അല്ലെങ്കിൽ സെറ്റിൽ തുകയുടെ മൂല്യം അടങ്ങിയിരിക്കുന്നുവെങ്കിൽ, അവയിൽ മൂന്നെണ്ണം തെറ്റാണ്, അതിനാൽ ഞങ്ങൾ ഇവിടെ ഒന്നും ചെയ്യാതെ സെറ്റിലേക്ക് -3 ചേർക്കുക.

i = 1, arr [i] = 2

sum = sum + arr [i] => -3 + 2 = -1

sum == 0 അല്ലെങ്കിൽ arr [i] 0 ന് തുല്യമാണെങ്കിൽ അല്ലെങ്കിൽ സെറ്റിൽ തുകയുടെ മൂല്യം അടങ്ങിയിരിക്കുന്നുവെങ്കിൽ, അവയിൽ മൂന്നെണ്ണം തെറ്റാണ്, അതിനാൽ ഞങ്ങൾ ഇവിടെ ഒന്നും ചെയ്യാതെ സെറ്റിലേക്ക് -1 ചേർക്കുക.

i = 2, arr [i] = 1

sum = sum + arr [i] => -1 + 1 = 0

sum == 0 അവസ്ഥ ഇവിടെ തൃപ്‌തികരമാണെങ്കിൽ‌, ഞങ്ങൾ‌ ശരിയാണ്, അതിനർത്ഥം തുക 0 ഉള്ള ഒരു ഉപ-അറേ ഞങ്ങൾ‌ കണ്ടെത്തി എന്നാണ്.

Put ട്ട്‌പുട്ട്: അതെ, തുക 0 ഉള്ള ഒരു ഉപ-അറേ നിലവിലുണ്ട്.

കോഡ്

0 തുകയുള്ള ഒരു സബ്‌റേ ഉണ്ടോയെന്ന് കണ്ടെത്താനുള്ള സി ++ കോഡ്

#include<iostream>
#include<unordered_set>

using namespace std;

bool isSubArrayZero(int arr[], int n)
{
    unordered_set<int> Set;
    int sum = 0;
    for (int i = 0 ; i < n ; i++)
    {
        sum += arr[i];
        if (sum == 0 || Set.find(sum) != Set.end())
            return true;

        Set.insert(sum);
    }
    return false;
}
int main()
{
    int arr[] = {-3, 2, 1, 9, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    if (isSubArrayZero(arr, n))
        cout << "Yes, a sub-array with sum 0 exist";
    else
        cout << "No, a sub-array with sum 0 does not exist";
    return 0;
}
Yes, a sub-array with sum 0 exist

0 തുകയുള്ള ഒരു സബ്‌റേ ഉണ്ടോയെന്ന് കണ്ടെത്താനുള്ള ജാവ കോഡ്

import java.util.Set;
import java.util.HashSet;

class sumOfSubArrayZero
{
    public static Boolean isSubArrayZero(int arr[])
    {
        Set<Integer> set = new HashSet<Integer>();
        int Sum = 0;
        for (int i = 0; i < arr.length; i++)
        {
            Sum += arr[i];
            if (arr[i] == 0 || Sum == 0 || set.contains(Sum))
                return true;

            set.add(Sum);
        }
        return false;
    }
    public static void main(String arg[])
    {
        int arr[] = {-3, 2, 1, 9, 6};
        if (isSubArrayZero(arr))
            System.out.println("Yes, a subarray with sum 0 exists");
        else
            System.out.println("No, a subarray with sum 0 does not exist");
    }
}
Yes, a subarray with sum 0 exists

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഒ (1) സമയത്ത് ഉൾപ്പെടുത്തൽ, തിരയൽ, ഇല്ലാതാക്കൽ എന്നിവ നടത്താൻ ഇത് ഞങ്ങളെ അനുവദിക്കുന്നതിനാൽ ഒരു ഹാഷ്‌സെറ്റ് ഉപയോഗിക്കുന്നതിനാൽ ഇതെല്ലാം സാധ്യമായിരുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. സൃഷ്ടിച്ച ഹാഷ് സെറ്റിൽ പരമാവധി n ഘടകങ്ങൾ ഉണ്ടാകാമെന്നതിനാൽ, സ്ഥല സങ്കീർണ്ണത രേഖീയമാണ്.