1 ಸೆ ಎಣಿಕೆ ಹೊಂದಿರುವ ಅತಿ ಉದ್ದದ ಸಬ್‌ರೇ 0 ಸೆ ಎಣಿಕೆಗಿಂತ ಒಂದು ಹೆಚ್ಚು


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಸೆಂಚರ್ ಅಮೆಜಾನ್ ಡಿಇ ಶಾ ಸ್ಯಾಮ್ಸಂಗ್
ಅರೇ ಹ್ಯಾಶ್

ನಾವು ಒಂದು ನೀಡಿದ್ದೇವೆ ಸರಣಿ ಪೂರ್ಣಾಂಕಗಳ. ಒಂದು ಶ್ರೇಣಿಯು 1 ಮತ್ತು 0 ಗಳನ್ನು ಮಾತ್ರ ಒಳಗೊಂಡಿದೆ. 1 ರ ಅಂಕಿಯ ಪ್ರಮಾಣವನ್ನು ಹೊಂದಿರುವ ಉಪ-ಶ್ರೇಣಿಯಲ್ಲಿನ 0 ರ ಎಣಿಕೆಗಿಂತ ಕೇವಲ ಒಂದು ಹೆಚ್ಚು ಇರುವ ಉದ್ದದ ಉಪ-ರಚನೆಯ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಮಸ್ಯೆ ಹೇಳಿಕೆಯು ಕೇಳುತ್ತದೆ.

ಉದಾಹರಣೆ

ಇನ್ಪುಟ್:

arr [] = {1,0,1,1,0,0,0}

ಔಟ್ಪುಟ್:

5

ವಿವರಣೆ:

0 ರಿಂದ 4 ಸೂಚ್ಯಂಕ, {1, 0, 1, 1, 0}, ಮೂರು ಇವೆ 1 ಮತ್ತು ಎರಡು 0 ಗಳು. 1 ಕ್ಕಿಂತ 0 ರ ಒಂದು ಎಣಿಕೆ.

ಇನ್ಪುಟ್:

arr [] = {1,0,1,0,0}

ಔಟ್ಪುಟ್:

3

ವಿವರಣೆ:

0 ರಿಂದ 2 ಸೂಚ್ಯಂಕ, {1, 0, 1}, ಎರಡು 1 ಮತ್ತು ಒಂದು 0 ಗಳಿವೆ. 1 ಕ್ಕಿಂತ 0 ರ ಒಂದು ಎಣಿಕೆ.

ಕ್ರಮಾವಳಿ

  1. ನಕ್ಷೆಯನ್ನು ಘೋಷಿಸಿ.
  2. ಮೊತ್ತ ಮತ್ತು output ಟ್‌ಪುಟ್ ಉದ್ದವನ್ನು 0 ಗೆ ಹೊಂದಿಸಿ.
  3. ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗಿರಿ, ಆದರೆ ನಾನು = 0 ರಿಂದ i <n.
    1. ನಿಜವಾಗಿದ್ದರೆ arr [i] 0 ಗೆ ಸಮನಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ ನಂತರ ಮೊತ್ತಕ್ಕೆ -1 ಸೇರಿಸಿ.
    2. ಬೇರೆ ಮೊತ್ತಕ್ಕೆ +1 ಸೇರಿಸಿ.
    3. ಎಂದು ಪರಿಶೀಲಿಸಿ ಮೊತ್ತವು ಸಮಾನವಾಗಿರುತ್ತದೆ 1 ಕ್ಕೆ, ನಂತರ output ಟ್‌ಪುಟ್ ಉದ್ದದ ಮೌಲ್ಯವನ್ನು 1 ರಿಂದ ಹೆಚ್ಚಿಸಿ.
    4. ಬೇರೆ, ಒಂದು ನಕ್ಷೆಯು ನಿಜವಾಗಿದ್ದರೆ ಮೊತ್ತವನ್ನು ಹೊಂದಿಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸಿ ನಂತರ ಮೊತ್ತದ ಜೊತೆಗೆ i ನ ಮೊತ್ತ ಮತ್ತು ಪ್ರಸ್ತುತ ಮೌಲ್ಯವನ್ನು ನಕ್ಷೆಗೆ ಇರಿಸಿ.
    5. ನಕ್ಷೆಯಲ್ಲಿ (ಮೊತ್ತ -1) ಇದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ.
    6. L ಟ್ಪುಟ್ ಉದ್ದವು ಐ-ಸೂಚ್ಯಂಕಕ್ಕಿಂತ ಕಡಿಮೆಯಿದ್ದರೆ (ನಕ್ಷೆಯಲ್ಲಿನ ಮೊತ್ತದ ಮೌಲ್ಯ).
      1. ನಿಜವಾಗಿದ್ದರೆ, -ಟ್‌ಪುಟ್ ಉದ್ದವನ್ನು ಐ-ಇಂಡೆಕ್ಸ್‌ಗೆ ನವೀಕರಿಸಿ.
  4. Output ಟ್ಪುಟ್ ಉದ್ದವನ್ನು ಹಿಂತಿರುಗಿ.

ವಿವರಣೆ

ನಾವು ಎ ಎಂದು ಘೋಷಿಸುತ್ತೇವೆ ನಕ್ಷೆ. ಆ ನಕ್ಷೆಯಲ್ಲಿ, ಷರತ್ತು ತೃಪ್ತಿಪಡಿಸಿದರೆ ನಾವು ಮೊತ್ತದ ಮೌಲ್ಯ ಮತ್ತು ಸೂಚ್ಯಂಕದ ಪ್ರಸ್ತುತ ಮೌಲ್ಯವನ್ನು ಸಂಗ್ರಹಿಸಲಿದ್ದೇವೆ. ಎರಡು ಅಸ್ಥಿರಗಳನ್ನು ತೆಗೆದುಕೊಂಡು ಮೊತ್ತವನ್ನು 0 ಗೆ ಮತ್ತು output ಟ್‌ಪುಟ್ ಉದ್ದವನ್ನು 0 ಗೆ ಹೊಂದಿಸಿ. ರಚನೆಯ ಮೂಲಕ ಸಾಗುವಾಗ, ನಾವು ಒಂದು ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಆರಿಸಿಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು arr [i] 0 ಗೆ ಸಮನಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ಅದು ಸಮಾನವೆಂದು ಕಂಡುಬಂದಲ್ಲಿ, ನಾವು ಸೇರಿಸುತ್ತೇವೆ -1 ಮೊತ್ತಕ್ಕೆ ಮತ್ತು ಅದನ್ನು ಮೊತ್ತಕ್ಕೆ ಸಂಗ್ರಹಿಸಿ, ಇಲ್ಲದಿದ್ದರೆ ನಾವು 0 ಎಂದು ಕಂಡುಬಂದಿಲ್ಲವಾದರೆ, ನಾವು ಧನಾತ್ಮಕ 1 ಅನ್ನು ಮೊತ್ತಕ್ಕೆ ಸೇರಿಸುತ್ತೇವೆ ಮತ್ತು ಅದನ್ನು ಮೊತ್ತಕ್ಕೆ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ.

ಆ negative ಣಾತ್ಮಕ 1 ಮತ್ತು ಧನಾತ್ಮಕ 1 ರ ಹಿಂದಿನ ಕಾರಣವೆಂದರೆ, ನಾವು ಎಲ್ಲಾ 0 ಗಳನ್ನು -1 ರಿಂದ ನಟಿಸುತ್ತಿದ್ದೇವೆ ಮತ್ತು ಅವುಗಳನ್ನು 1 ರೊಂದಿಗೆ ಸೇರಿಸುತ್ತೇವೆ, ಆದ್ದರಿಂದ ನಾವು ಯಾವಾಗಲೂ 0 ಅನ್ನು ಪಡೆಯುತ್ತೇವೆ. ಆದರೆ ನಾವು ಧನಾತ್ಮಕ 1 ಮೊತ್ತವನ್ನು ಪರಿಶೀಲಿಸುತ್ತೇವೆ, ಅದು ನಮಗೆ ಒಂದು ಹೆಚ್ಚುವರಿ 1 ಅನ್ನು ಹೊಂದಿರುತ್ತದೆ ಮತ್ತು ನಂತರ 0 ರ ಎಣಿಕೆ ಎಂದು ಸೂಚಿಸುತ್ತದೆ.

ನಾವು 1 ಅನ್ನು -0 ಎಂದು ನಟಿಸುತ್ತಿದ್ದರೆ ನಾವು 1, 0, 1 ಅನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತೇವೆ ಎಂದು ಭಾವಿಸೋಣ, ನಾವು ಆ 0 ಅನ್ನು ಮೊದಲ 2 ಸಂಖ್ಯೆಗಳೊಂದಿಗೆ ಪಡೆಯುತ್ತೇವೆ ಮತ್ತು ಮೂರನೆಯ ಸಂಖ್ಯೆಯೊಂದಿಗೆ, ನಮ್ಮ ಸ್ಥಿತಿಯು ಈಡೇರಿದೆ ಎಂದು ನಾವು ಕಂಡುಕೊಳ್ಳಬಹುದು. 1 ಮತ್ತು 0 ರ ಉಪ-ಶ್ರೇಣಿಯನ್ನು ನಾವು 1 ಕ್ಕಿಂತ 0 ಹೆಚ್ಚುವರಿ ಎಣಿಕೆಯೊಂದಿಗೆ ಪಡೆದುಕೊಂಡಿದ್ದೇವೆ. ನಮ್ಮ ಸ್ಥಿತಿಯನ್ನು ನಾವು ತೃಪ್ತಿಪಡಿಸುತ್ತೇವೆ. ಅದಕ್ಕಾಗಿಯೇ ಅಲ್ಗಾರಿದಮ್‌ನ ಮುಂದಿನ ಹಂತದಲ್ಲಿ ಮೊತ್ತವು 1 ಕ್ಕೆ ಸಮನಾಗಿರುತ್ತದೆಯೇ ಮತ್ತು output ಟ್‌ಪುಟ್‌ನ ಉದ್ದವನ್ನು ನವೀಕರಿಸುತ್ತೇವೆಯೇ ಎಂದು ನಾವು ಹುಡುಕುತ್ತೇವೆ. ಕೊನೆಯದಾಗಿ, ಹೇಳಿಕೆಯು, ನಾವು ಹೊಸ output ಟ್‌ಪುಟ್ ಉದ್ದವನ್ನು ಪಡೆದರೆ, ಹಿಂದಿನದನ್ನು ಪ್ರಸ್ತುತ output ಟ್‌ಪುಟ್ ಉದ್ದದೊಂದಿಗೆ ನವೀಕರಿಸಬೇಕಾಗಿದೆ ಮತ್ತು ನಾವು output ಟ್‌ಪುಟ್ ಉದ್ದವನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ.

ಅನುಷ್ಠಾನ

ಉದ್ದದ ಸಬ್‌ರೇರ್‌ಗಾಗಿ ಸಿ ++ ಪ್ರೋಗ್ರಾಂ 1 ಸೆ ಎಣಿಕೆ 0 ಸೆ ಎಣಿಕೆಗಿಂತ ಹೆಚ್ಚು

#include <iostream>
#include<unordered_map>

using namespace std;

int getLongestLen(int arr[], int n)
{
    unordered_map<int, int> MAP;
    int sum = 0, outputLength= 0;

    for (int i = 0; i < n; i++)
    {

        if(arr[i] == 0)
            sum += -1;
        else
            sum += 1;


        if (sum == 1)
        {
            outputLength = i + 1;
        }
        else if (MAP.find(sum) == MAP.end())
        {
            MAP[sum] = i;
        }

        if (MAP.find(sum - 1) != MAP.end())
        {
            if (outputLength < (i - MAP[sum - 1]))
                outputLength = i - MAP[sum - 1];
        }
    }
    return outputLength;
}
int main()
{
    int arr[] = {1,0,1,1,0,0,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Length of the longest Sub-Array : "<<getLongestLen(arr, n);
    return 0;
}
Length of the longest Sub-Array : 5

1 ಸೆ ಎಣಿಕೆ ಹೊಂದಿರುವ ಉದ್ದದ ಸಬ್‌ರೇರಿಗಾಗಿ ಜಾವಾ ಪ್ರೋಗ್ರಾಂ 0 ಸೆ ಎಣಿಕೆಗಿಂತ ಹೆಚ್ಚು

import java.util.HashMap;

class longestSubArray01
{
    public static int getLongestLen(int arr[], int n)
    {
        HashMap<Integer, Integer> MAP = new HashMap<Integer,Integer>();
        int sum = 0, outputLength = 0;

        for (int i = 0; i < n; i++)
        {
            if(arr[i] == 0)
                sum += -1;
            else
                sum += 1;

            if (sum == 1)
                outputLength = i + 1;
            else if (!MAP.containsKey(sum))
                MAP. put(sum, i);


            if (MAP.containsKey(sum - 1))
            {
                if (outputLength < (i - MAP.get(sum - 1)))
                    outputLength = i - MAP.get(sum - 1);
            }
        }
        return outputLength;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,0,1,1,0,0,0};
        int n = arr.length;
        System.out.println("Length of the longest Sub-Array : " +getLongestLen(arr, n));
    }
}
Length of the longest Sub-Array : 5

1 ಸೆ ಎಣಿಕೆ ಹೊಂದಿರುವ ಉದ್ದದ ಸಬ್‌ರೇರ್‌ಗಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ 0 ಸೆ ಎಣಿಕೆಗಿಂತ ಒಂದು ಹೆಚ್ಚು

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್”  ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್”  ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ.