ನಿರಂತರ ಅರೇ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ MakeMyTrip ಮಾರ್ಗನ್ ಸ್ಟಾನ್ಲಿ ಪೇಟ್ಮ್
ಹ್ಯಾಶಿಂಗ್ ಸ್ಲೈಡಿಂಗ್ ವಿಂಡೋ

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

ಉದಾಹರಣೆ

ಇನ್ಪುಟ್

arr = [0,1,0,1,0,0,1]

ಔಟ್ಪುಟ್

6

ವಿವರಣೆ

ಉದ್ದವಾದ ಪರಸ್ಪರ ಉಪ-ರಚನೆ ಕೆಂಪು ಬಣ್ಣದಲ್ಲಿ ಗುರುತಿಸಲಾಗಿದೆ [0,1,0,1,0,0,1] ಮತ್ತು ಅದರ ಉದ್ದ 6 ಆಗಿದೆ.

ಕ್ರಮಾವಳಿ

  1. ಮ್ಯಾಕ್ಸ್ಲೆನ್ ಮೌಲ್ಯವನ್ನು 0 ಗೆ ಹೊಂದಿಸಿ.
  2. ಎರಡು ಲೂಪ್‌ಗಳನ್ನು ಬಳಸಿ, ಮೊದಲ ಲೂಪ್‌ನಲ್ಲಿ er ೆರ್_ಕೌಂಟ್ ಅನ್ನು 0 ಗೆ, ಒಂದು_ಕೌಂಟ್ ಅನ್ನು 0 ಗೆ ಹೊಂದಿಸಿ.
  3. ಒಂದು ವೇಳೆ ಮೌಲ್ಯ ನಿರ್ದಿಷ್ಟ ಸೂಚ್ಯಂಕದಲ್ಲಿ ರಚನೆ 0 ಎಂದು ಕಂಡುಬಂದ ನಂತರ ಶೂನ್ಯ_ ಸಂಖ್ಯೆಯನ್ನು 1 ರಿಂದ ಹೆಚ್ಚಿಸಿ.
  4. ಬೇರೆ ನವೀಕರಿಸಿ ಮತ್ತು ಒನ್_ಕೌಂಟ್ ಅನ್ನು 1 ಹೆಚ್ಚಿಸಿ.
  5. ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯ ಪರಿಶೀಲನೆಯಲ್ಲಿ ಶೂನ್ಯ_ಕೌಂಟ್ ಒಂದು_ಕೌಂಟ್ಗೆ ಸಮನಾಗಿದೆಯೇ, ಸಮಾನವಾಗಿದ್ದರೆ, ನಂತರ ದೊಡ್ಡದನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ (ಮ್ಯಾಕ್ಸ್ಲೆನ್ ಮತ್ತು ಜೆ-ಐ + 1)
  6. ರಿಟರ್ನ್ ಮ್ಯಾಕ್ಸ್ಲೆನ್

ವಿವರಣೆ

ನಮ್ಮ ಮುಖ್ಯ ಆಲೋಚನೆಯೆಂದರೆ, ಶೂನ್ಯ ಮತ್ತು ಒಬ್ಬರ ಏಕೈಕ ಉದ್ದವನ್ನು ಹೊಂದಿರುವ ಅತಿ ಉದ್ದದ ಸಬ್‌ಅರೇನ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು, ಆದ್ದರಿಂದ ನಮ್ಮ ಮುಖ್ಯ ಗಮನವು ಆ ಉದ್ದವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು.

ಆದ್ದರಿಂದ, ನಾವು ಲೂಪ್ಗಾಗಿ ನೆಸ್ಟೆಡ್ ಅನ್ನು ಬಳಸಲಿದ್ದೇವೆ. ಹೊರಗಿನ ಲೂಪ್‌ನಲ್ಲಿ, ನಾವು ಶೂನ್ಯ_ಕೌಂಟ್ ಮತ್ತು ಒಂದು_ಕೌಂಟ್‌ನ ಮೌಲ್ಯವನ್ನು 0 ಗೆ ಪ್ರಾರಂಭಿಸುತ್ತೇವೆ, ಏಕೆಂದರೆ ಪ್ರತಿ ಪುನರಾವರ್ತನೆಯ ನಂತರ ಅದು ಆಂತರಿಕ ಲೂಪ್‌ನಿಂದ ಹೊರಬಂದಾಗ ನಮಗೆ ಮತ್ತೆ ಶೂನ್ಯ_ಕೌಂಟ್ ಮತ್ತು ಒಂದು_ಕೌಂಟ್‌ನ ಹೊಸ ಮೌಲ್ಯಗಳು ಬೇಕಾಗುತ್ತವೆ. ರಚನೆಯ ಉದ್ದವನ್ನು ತಲುಪುವವರೆಗೆ ನಾವು ಲೂಪ್ ಮೇಲೆ ಪುನರಾವರ್ತಿಸುತ್ತೇವೆ.

ಈಗ ಅದು ರಚನೆಯ ಪ್ರತಿಯೊಂದು ಮೌಲ್ಯವನ್ನು ಪರಿಶೀಲಿಸಲಿದೆ, ಅರ್ [ಸೂಚ್ಯಂಕ] 0 ಅಥವಾ 1 ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದ್ದರೆ ಅದು 0 ಗೆ ಸಮನಾದ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದ್ದರೆ ನವೀಕರಿಸಿ ಮತ್ತು ಶೂನ್ಯ_ಕೌಂಟ್ ಮೌಲ್ಯವನ್ನು 1 ರಿಂದ ಹೆಚ್ಚಿಸಿ ಅಥವಾ ಅರ್ [ಸೂಚ್ಯಂಕ] 1 ಎಂದು ಕಂಡುಕೊಂಡರೆ, ಅದು ಒಂದು_ಕೌಂಟ್‌ನ ಮೌಲ್ಯವನ್ನು 1 ರಿಂದ ನವೀಕರಿಸುತ್ತದೆ ಮತ್ತು ಹೆಚ್ಚಿಸುತ್ತದೆ.

ಈಗ, ಮುಂದಿನ ಬ್ಲಾಕ್ ಬ್ಲಾಕ್ ಶೂನ್ಯ_ಕೌಂಟ್ ಒಂದು_ಕೌಂಟ್ಗೆ ಸಮನಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಲು ಹೋಗುತ್ತಿದ್ದರೆ, ಸಮಾನವಾಗಿದ್ದರೆ, ಮ್ಯಾಕ್ಸ್ಲೆನ್ ಮತ್ತು ಜೆ-ಐ +1 ನಡುವಿನ ದೊಡ್ಡ ಸಂಖ್ಯೆಯನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ ಮತ್ತು ದೊಡ್ಡ ಸಂಖ್ಯೆಯನ್ನು ಮ್ಯಾಕ್ಸ್ಲೆನ್ನಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತದೆ.

ಉದಾಹರಣೆ

ರಚನೆಯನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಭಾವಿಸೋಣ: arr [] = 1,0,0,1,0,1,0 XNUMX}

ಶೂನ್ಯ_ಕೌಂಟ್ = 0, ಒಂದು_ಕೌಂಟ್ = 0, ಮ್ಯಾಕ್ಸ್ಲೆನ್ = 0

i = 0, => j = i ನಲ್ಲಿ

j = 0

arr [j] ನಲ್ಲಿ 0 ಗೆ ಸಮನಾಗಿರುವುದಿಲ್ಲ, ನಂತರ ಒಂದು_ಕೌಂಟ್ ++, ಅಂದರೆ ಒಂದು_ಕೌಂಟ್ = 1

j = 1

Ar [j] ನಲ್ಲಿ 0 ಗೆ ಸಮ, ನಂತರ ಶೂನ್ಯ_ಕೌಂಟ್ ++, ಅಂದರೆ ಶೂನ್ಯ_ಕೌಂಟ್ = 1

ಬ್ಲಾಕ್ ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಿದರೆ ಮುಂದಿನ ಈ ಸ್ಥಳದಲ್ಲಿ, ಇದು ಮ್ಯಾಕ್ಸ್ಲೆನ್ ಮತ್ತು ಜೆ-ಐ +1 ನಡುವೆ ದೊಡ್ಡದನ್ನು ನೀಡುವುದಿಲ್ಲ ಮತ್ತು ಮ್ಯಾಕ್ಸ್ಲೆನ್ನಲ್ಲಿ 2 ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ

j = 2

Ar [j] ನಲ್ಲಿ 0 ಗೆ ಸಮ, ನಂತರ ಶೂನ್ಯ_ಕೌಂಟ್ ++, ಅಂದರೆ ಶೂನ್ಯ_ಕೌಂಟ್ = 2

j = 3

Ar [j] ನಲ್ಲಿ 0 ಗೆ ಸಮನಾಗಿಲ್ಲ, ನಂತರ ಒಂದು_ಕೌಂಟ್ ++, ಅಂದರೆ ಒಂದು_ಕೌಂಟ್ = 2

ಬ್ಲಾಕ್ ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಿದರೆ ಮುಂದಿನ ಈ ಸ್ಥಳದಲ್ಲಿ, ಇದು ಮ್ಯಾಕ್ಸ್ಲೆನ್ ಮತ್ತು ಜೆ-ಐ + 1 ನಡುವೆ ದೊಡ್ಡದನ್ನು ನೀಡುವುದಿಲ್ಲ ಮತ್ತು ಮ್ಯಾಕ್ಸ್ಲೆನ್ನಲ್ಲಿ 4 ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ.

j = 4

Ar [j] ನಲ್ಲಿ 0 ಗೆ ಸಮ, ನಂತರ ಶೂನ್ಯ_ಕೌಂಟ್ ++, ಅಂದರೆ ಶೂನ್ಯ_ಕೌಂಟ್ = 3

j = 5

Ar [j] ನಲ್ಲಿ 0 ಗೆ ಸಮನಾಗಿಲ್ಲ, ನಂತರ ಒಂದು_ಕೌಂಟ್ ++, ಅಂದರೆ ಒಂದು_ಕೌಂಟ್ = 3

ಬ್ಲಾಕ್ ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಿದರೆ ಮುಂದಿನ ಈ ಸ್ಥಳದಲ್ಲಿ, ಇದು ಮ್ಯಾಕ್ಸ್ಲೆನ್ ಮತ್ತು ಜೆ-ಐ + 1 ನಡುವೆ ದೊಡ್ಡದನ್ನು ನೀಡುವುದಿಲ್ಲ ಮತ್ತು ಮ್ಯಾಕ್ಸ್ಲೆನ್ನಲ್ಲಿ 6 ಅನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ.

j = 6

Ar [j] ನಲ್ಲಿ 0 ಗೆ ಸಮ, ನಂತರ ಶೂನ್ಯ_ಕೌಂಟ್ ++, ಅಂದರೆ ಶೂನ್ಯ_ಕೌಂಟ್ = 4

ಮತ್ತು ಎಲ್ಲಾ ಷರತ್ತುಗಳು ವಿಫಲಗೊಳ್ಳುವವರೆಗೆ ಅದು ಲೂಪ್ ಅನ್ನು ಪುನರಾವರ್ತಿಸುತ್ತದೆ.

ಮತ್ತು ಮ್ಯಾಕ್ಸ್ಲೆನ್ ಅನ್ನು 6 ಎಂದು ಹಿಂತಿರುಗಿ.

ಅನುಷ್ಠಾನ

ನಿರಂತರ ಅರೇಗಾಗಿ ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <iostream>
using namespace std;
int contiguous_Array(int arr[], int n)
{
    int i,j,maxlen=0;
    for( i = 0 ; i < n ; i++)
    {
        int zero_count=0,one_count=0;
        for(j = i ; j < n ; j++)
        {
            if( arr[j] == 0 )
            {
                zero_count++;
            }
            else
            {
                one_count++;
            }
            if(zero_count==one_count)
            {
                maxlen=std::max(maxlen,j-i+1);
            }
        }
    }
    return maxlen;
}
int main()
{
    int arr[]= {1,0,0,1,0,1,0};
    int n=sizeof(arr)/sizeof(arr[0]);
    cout <<contiguous_Array(arr,n)<< endl;
    return 0;
}
6

ಕಾಂಟಿಗಿಯಸ್ ಅರೇಗಾಗಿ ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

public class Contiguous_Array {

  public static int solution(int[] arr) {

    int maxlen = 0;

    for (int i = 0; i<arr.length; i++) {

      int zero_count = 0, one_count = 0;

      for (int j = i; j<arr.length; j++) {

        if (arr[j] == 0) {
          zero_count++;
        } else {
          one_count++;
        }
        if (zero_count == one_count) {

          maxlen = Math.max(maxlen, j - i + 1);

        }
      }
    }
    return maxlen;
  }
  public static void main(String args[]) {

    int[] arr = new int[] {
      0, 1, 0, 1, 0, 0, 1
    };

    System.out.println(solution(arr));

  }
}
6

ನಿರಂತರ ಅರೇಗಾಗಿ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಎನ್ * ಎನ್) ಅಲ್ಲಿ N ಕೊಟ್ಟಿರುವ ರಚನೆಯ ಗಾತ್ರ.

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

ಒ (1) ಏಕೆಂದರೆ ನಾವು ಇಲ್ಲಿ ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಸ್ಥಳವನ್ನು ಬಳಸುವುದಿಲ್ಲ.

ರೆಫರೆನ್ಸ್