0 தொகையுடன் ஒரு துணை வரிசை இருக்கிறதா என்று கண்டுபிடிக்கவும்


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது Citrix டி.இ ஷா கோல்ட்மேன் சாக்ஸ் உண்மையில் மேக்மைட்ரிப் 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, அமை = {Set

i = 0, arr [i] = -3

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

sum == 0 அல்லது arr [i] 0 க்கு சமமாக இருந்தால் அல்லது Set என்பது கூட்டுத்தொகையின் மதிப்பைக் கொண்டிருந்தால், அவற்றில் மூன்று தவறானவை, எனவே நாங்கள் இங்கு எதுவும் செய்யாமல் -3 ஐ செட்டில் சேர்க்கிறோம்.

i = 1, arr [i] = 2

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

sum == 0 அல்லது arr [i] 0 க்கு சமமாக இருந்தால் அல்லது Set என்பது கூட்டுத்தொகையின் மதிப்பைக் கொண்டிருந்தால், அவற்றில் மூன்று தவறானவை, எனவே நாங்கள் இங்கு எதுவும் செய்யாமல் -1 ஐ செட்டில் சேர்க்கிறோம்.

i = 2, arr [i] = 1

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

கூட்டுத்தொகை == 0 நிபந்தனை இங்கே திருப்தி அடைந்தால், நாம் உண்மைக்குத் திரும்புவோம், இதன் பொருள் தொகை 0 உடன் துணை வரிசையைக் கண்டறிந்தோம்.

வெளியீடு: ஆம், கூட்டுத்தொகை 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. ஹாஷ்செட்டைப் பயன்படுத்துவதால் இவை அனைத்தும் சாத்தியமானது, ஏனெனில் இது ஓ (1) நேரத்தில் செருகவும், தேடவும், நீக்கவும் அனுமதிக்கிறது.

விண்வெளி சிக்கலானது

ஓ (n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை. உருவாக்கப்பட்ட ஹாஷ் தொகுப்பில் அதிகபட்சம் n கூறுகள் இருக்கக்கூடும் என்பதால், விண்வெளி சிக்கலானது நேரியல் ஆகும்.