subarray ၀ င်ငွေပေါင်း 0 ရှိလျှင်ရှာပါ


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Citrix DE Shaw Goldman Sachs တကယ်ပါပဲ ကွမ်းခြံကုန်း OYO အခန်းများ Paytm ကိုလန်ဘို
အခင်းအကျင်း hash

“ ၀ န်ဆောင်မှုက 0 ၀ င်တဲ့ subarray ရှိရင်ရှာပါ” ပြproblemနာကသင့်အားပေးထားသည်ဟုဖော်ပြထားသည် ကိန်း အခင်းအကျင်း အဖြစ်ကောင်းစွာအနုတ်လက္ခဏာကိန်းပါဝင်သည်။ ပြstatementနာကကြေငြာချက်သည်အနည်းဆုံးအနည်းဆုံး ၁ ခုရှိသည့် Sub-ခင်းကျင်းမှုရှိ၊ မရှိကိုဆုံးဖြတ်ရန်တောင်းဆိုသည်။

နမူနာ

subarray ၀ င်ငွေပေါင်း 0 ရှိလျှင်ရှာပါ

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

ရှင်းလင်းချက်

ဒီနေရာမှာအညွှန်းကိန်းကနေ ၂ ကနေ element တွေမှာ ၀ ပေါင်းလဒ် 0 ရှိတယ်။

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

ရှင်းလင်းချက်

ပေါင်းလဒ် 0 ရှိသည့် sub-array မရှိပါ။

algorithm

  1. a) ကြေညာပါ အစုံ.
  2. စတငျ ငှေပေါငျး 0 သို့။
  3. စဉ်ခင်းကျင်းဖြတ်သန်း i <n (အခင်းကျင်း၏အရှည်) ။
    1. sum ကို arr [i] သို့ထည့်ပြီး sum သို့သိမ်းပါ။
    2. အောက်ပါအခြေအနေများမှတစ်ခုခုမှန်မမှန်စစ်ဆေးပါ။
      1. ပေါင်းလဒ် == 0 / arr [i] == 0 / သတ်မှတ်မည်ပေါင်းလဒ်၏တန်ဖိုးပါရှိသည်လျှင်။
      2. မှန်လျှင်, true ကိုပြန်သွားပါ။
    3. ပေါင်းလဒ်ကို Set ကိုထည့်ပါ။
  4. return false ။

ရှင်းလင်းချက်

ကျွန်တော်တို့မှာ sub- ခင်းကျင်းမှုရှိသလား 0 နဲ့ညီမျှတဲ့ပေါင်းလဒ်တစ်ခုရှိသလားဆိုတာရှာဖို့ပြproblemနာကြေညာချက်ရတယ်။ ဒီပြsolveနာကိုဖြေရှင်းဖို့ဒီပြproblemနာကိုဖြေရှင်းဖို့ Set ကိုသုံးမယ်။ ပေးထားသောခင်းကျင်းခြင်း၏အစိတ်အပိုင်းများကို Set ထဲသို့သိမ်းဆည်းမည်။ ထို့နောက်တန်ဖိုးကိုပေါင်းလဒ်ထဲသို့တစ်ပြိုင်နက်ထည့်ပါ။ အစုထဲရှိလက်ရှိစုစုပေါင်းနှင့်ထပ်တူခင်းကျင်းမှုရှိမရှိရှိမရှိစစ်ဆေးပါသို့မဟုတ်ပေါင်းလဒ်ကိုယ်တိုင် ၀ ၀ နှင့်ညီသည်လားစစ်ဆေးပါ။ မှန်ပါတယ်

sub-arrays များမှ sum သည် 0 မရှိလျှင်ကျွန်ုပ်တို့သည် loop မှ false ကိုပြန်သွားပါမည်။ ထို့အပြင်တစ်ခုရှိသေးသည်။ အကယ်၍ element တစ်ခုမှ 0 ရှိခဲ့လျှင်၎င်းသည် element တစ်ခုတည်း၏ sub-array ကြောင့်၎င်းသည် true သို့ပြန်သွားပါမည်။ ဆိုလိုတာကကျွန်တော်တို့ဟာ sub- ခင်းကျင်းတစ်ခုတွေ့ခဲ့တယ်။

ဒီကုဒ်မှာ Boolean function ကိုကြေငြာတယ်၊ sub-array ကိုတွေ့ရင်၊ return ပြန်မယ်၊ ဒါမှမဟုတ် false ပြန်ပေးမယ်။

ဥပမာတစ်ခုကိုသုံးသပ်ကြည့်ကြစို့။

နမူနာ

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

ဒီနေရာတွင်ကုဒ်ထဲမှာကျနော်တို့ကခင်းကျင်းဖြတ်သန်းနှင့်ပေါင်းထည့်သွင်းခြင်းနှင့် arr [i] နှင့်ပေါင်းလဒ်သို့သိမ်းဆည်းထားလိမ့်မည်နှင့် sum == 0 သို့မဟုတ် arr [i] သည် 0 နှင့်ညီလျှင်သို့မဟုတ်သတ်မှတ်လျှင်ပေါင်းလဒ်၏တန်ဖိုးပါရှိသည်လျှင်စစ်ဆေးပြီးနောက်, ပေးထားသောအခြေအနေတစ်ခုခုမှကျေနပ်မှုရှိပါကကျွန်ုပ်တို့သည် true သို့ပြန်သွားပြီး sum ထဲသို့ Set သို့ထည့်မည်။

အကယ်၍ sub- ခင်းကျင်းတစ်ခုမျှမတွေ့ပါကကျွန်ုပ်တို့သည် false သို့ပြန်သွားမည်။

ပေါင်းလဒ် = 0, သတ်မှတ်မည် = {}

ဈ = 0, ဆိုက်ရောက် [i] = -3

ပေါင်းလဒ် = ပေါင်းလဒ် + arr [i] => 0 + - 3 = -3

sum == 0 or arr [i] သည် 0 နှင့်ညီလျှင်သို့မဟုတ် Set တွင် sum ၏တန်ဖိုးပါရှိလျှင်၎င်းတို့အနက်မှသုံးခုသည် false ဖြစ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်ဤနေရာတွင်ဘာမျှမလုပ်ပါ၊ -3 ကို Set ထဲသို့ထည့်ပါ။

ဈ = 1, ဆိုက်ရောက် [i] = 2

ပေါင်းလဒ် = ပေါင်းလဒ် + ဆိုက်ရောက် [i] => -3 + 2 = -1

sum == 0 or arr [i] သည် 0 နှင့်ညီလျှင်သို့မဟုတ် Set တွင် sum ၏တန်ဖိုးပါရှိလျှင်၎င်းတို့အနက်မှသုံးခုသည် false ဖြစ်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်ဤနေရာတွင်ဘာမျှမလုပ်ပါ၊ -1 ကို Set ထဲသို့ထည့်ပါ။

ဈ = 2, ဆိုက်ရောက် [i] = 1

ပေါင်းလဒ် = ပေါင်းလဒ် + ဆိုက်ရောက် [i] => -1 + 1 = 0

sum == 0 အခြေအနေကဒီမှာကျေနပ်တယ်ဆိုလျှင် true ပြန်လာလျှင်၊ sum သုည 0 ပါတဲ့ sub-ခင်းကျင်းကိုတွေ့တယ်။

ပေါင်းလဒ် 0 ၀ င်တဲ့ sub-ခင်းကျင်းမှုရှိသည်။

ကုဒ်

subarray ရှိလျှင် 0 sum နှင့်ရှာရန် C ++ code

#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

Subarray ရှိလျှင် 0 sum နှင့်ရှာရန် Java code

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” သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ ဤအရာအားလုံးသည် H (H) အချိန်တွင်ထည့်သွင်းခြင်း၊ ရှာဖွေခြင်း၊ ဖျက်ခြင်းကိုပြုလုပ်ရန်ခွင့်ပြုထားသောကြောင့် HashSet ကိုအသုံးပြုခြင်းကြောင့်ဖြစ်နိုင်သည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘယ်မှာ “ n” သည် array ထဲရှိ element အရေအတွက်ဖြစ်သည်။ created hash set တွင်အများဆုံး n n element များရှိနိုင်သောကြောင့် space space သည်ရှုပ်ထွေးသည်။