ಶೂನ್ಯ ಮೊತ್ತದೊಂದಿಗೆ ಎಲ್ಲಾ ತ್ರಿವಳಿಗಳನ್ನು ಹುಡುಕಿ


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

“ಶೂನ್ಯ ಮೊತ್ತದೊಂದಿಗೆ ಎಲ್ಲಾ ತ್ರಿವಳಿಗಳನ್ನು ಹುಡುಕಿ” ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ಧನಾತ್ಮಕ ಮತ್ತು negative ಣಾತ್ಮಕ ಸಂಖ್ಯೆಯನ್ನು ಹೊಂದಿರುವ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ತ್ರಿವಳಿ ಮೊತ್ತವನ್ನು 0 ಗೆ ಸಮನಾದ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ.

ಶೂನ್ಯ ಮೊತ್ತದೊಂದಿಗೆ ಎಲ್ಲಾ ತ್ರಿವಳಿಗಳನ್ನು ಹುಡುಕಿ

ಉದಾಹರಣೆ

arr[] = {0,-2,1,3,2,-1}
(-2 -1  3) (-2 0  2) (-1 0  1)

ವಿವರಣೆ

ಇವುಗಳ ಮೊತ್ತವು ತ್ರಿವಳಿಗಳಾಗಿವೆ.

(-2 + -1 + 3 = 0) (-2 + 0 + 2 = 0) (-1+ 0 + 1 = 0)

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

ವಿವರಣೆ

ಇವುಗಳ ತ್ರಿವಳಿಗಳ ಸಂಖ್ಯೆಗಳ ಮೊತ್ತ 0 ⇒ -5 + 2 + 3 = 0

ಕ್ರಮಾವಳಿ

  1. ವಿಂಗಡಿಸಿ ಕೊಟ್ಟಿರುವ ರಚನೆ.
  2. ಹೊಂದಿಸಿ ಬೂಲಿಯನ್ ವೇರಿಯಬಲ್ ಸಿಕ್ಕಿದೆ ಸುಳ್ಳು.
  3. I = 0 ರಿಂದ i ಗೆ ಲೂಪ್ ಮಾಡಲಾಗುತ್ತಿದೆ
    1. ಹೊಂದಿಸಿ fir = i + 1, sec = n-1 ಮತ್ತು ಮತ್ತೊಂದು ವೇರಿಯಬಲ್ x ಪ್ರಸ್ತುತ ರಚನೆಯ ಅಂಶಕ್ಕೆ.
    2. ಫರ್ ಮಾಡುವಾಗ
      1. ಮೂರು ಅಂಶಗಳು ಒಟ್ಟಾಗಿ 0 ಮೊತ್ತವನ್ನು ಹೊಂದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ.
        1. ನಿಜವಾಗಿದ್ದರೆ, ಎಲ್ಲಾ ಮೂರು ಸಂಖ್ಯೆಯನ್ನು ಮುದ್ರಿಸಿ ಮತ್ತು isFound to true ಎಂದು ಹೊಂದಿಸಿ.
      2. ಮೂರು ಅಂಶಗಳ ಮೊತ್ತ (ಪ್ರಸ್ತುತ ರಚನೆಯ ಅಂಶಗಳು) 0 ಕ್ಕಿಂತ ಕಡಿಮೆಯಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ.
        1. ನಿಜವಾಗಿದ್ದರೆ, ಫರ್ ಮೌಲ್ಯವನ್ನು 1 ರಿಂದ ಹೆಚ್ಚಿಸಿ.
      3. ಮೂರು ಅಂಶಗಳ ಮೊತ್ತ 0 ಕ್ಕಿಂತ ಹೆಚ್ಚಿದ್ದರೆ ಬೇರೆ ಪರಿಶೀಲಿಸಿ.
          1. ನಿಜವಾಗಿದ್ದರೆ, ಸೆಕೆಂಡಿನ ಮೌಲ್ಯವನ್ನು 1 ರಷ್ಟು ಕಡಿಮೆ ಮಾಡಿ.
  4. IsFound ಸುಳ್ಳಾಗಿ ಉಳಿದಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ, ಅಂದರೆ ಯಾವುದೇ ತ್ರಿವಳಿಗಳನ್ನು ರಚಿಸಲಾಗುವುದಿಲ್ಲ.

ವಿವರಣೆ

ನಮಗೆ ಒಂದು ಶ್ರೇಣಿಯನ್ನು ನೀಡಲಾಗಿದೆ. ನಂತರ ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಕೊಟ್ಟಿರುವ ಸಂಖ್ಯೆಗಳೊಂದಿಗೆ ರಚಿಸಬಹುದಾದ ತ್ರಿವಳಿಗಳನ್ನು ನಿರ್ಧರಿಸಲು ನಮ್ಮನ್ನು ಕೇಳಲಾಗುತ್ತದೆ. ಇದರ ಮೊತ್ತ 0 ಆಗಿದೆ. ನಾವು ನೆಸ್ಟೆಡ್ ಲೂಪ್ ಅನ್ನು ಬಳಸಲಿದ್ದೇವೆ. ಈ ಅಲ್ಗಾರಿದಮ್ ಸ್ಥಿರ ಜಾಗದಲ್ಲಿ ಕೆಲಸ ಮಾಡುತ್ತದೆ. ಮೊದಲಿಗೆ, ನಾವು ರಚನೆಯನ್ನು ವಿಂಗಡಿಸಲು ಹೋಗುತ್ತೇವೆ. ಈ ರೀತಿಯಲ್ಲಿ ನಾವು ಎರಡು-ಪಾಯಿಂಟರ್ ತಂತ್ರವನ್ನು ಬಳಸಬಹುದು. ನಾವು ಒಂದು ಬೂಲಿಯನ್ ವೇರಿಯೇಬಲ್ ಅನ್ನು ಘೋಷಿಸುತ್ತೇವೆ ಮತ್ತು ಅದರ ಮೌಲ್ಯವನ್ನು ಮೊದಲಿಗೆ ತಪ್ಪು ಎಂದು ಹೊಂದಿಸುತ್ತೇವೆ. 0, ಅಂಶಗಳ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವ ಯಾವುದೇ ತ್ರಿವಳಿಗಳನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯುವುದಿಲ್ಲವೇ ಎಂದು ಖಚಿತಪಡಿಸಿಕೊಳ್ಳಲು ಇದು ಸಿಕ್ಕಿದೆ ಸುಳ್ಳು ಎಂದು ಉಳಿದಿದೆ. ನಾವು ತ್ರಿವಳಿ ಕಂಡುಕೊಂಡಾಗಲೆಲ್ಲಾ ಅದನ್ನು ನಿಜ ಎಂದು ನವೀಕರಿಸಲಿದ್ದೇವೆ. ಆದ್ದರಿಂದ ಇದರೊಂದಿಗೆ, ಯಾವುದೇ ತ್ರಿವಳಿ ಕಂಡುಬರುವುದಿಲ್ಲ ಎಂದು ನಾವು ತೀರ್ಮಾನಿಸಬಹುದು.

ನಾವು ಮೊದಲು ರಚನೆಯನ್ನು ನೆಸ್ಟೆಡ್ ಲೂಪ್‌ನಲ್ಲಿ ವಿಂಗಡಿಸುತ್ತೇವೆ. ನಂತರ ನಾವು ರಚನೆಯನ್ನು n-1 ವರೆಗೆ ಸಾಗಿಸುತ್ತೇವೆ. ನಾವು ಆರಂಭಿಕ ಮೌಲ್ಯವನ್ನು i + 1, ಕೊನೆಯ ಮೌಲ್ಯವನ್ನು n-1, ಮತ್ತು x ಅನ್ನು ಹೊರಗಿನ ಲೂಪ್‌ನಲ್ಲಿ ಪ್ರಸ್ತುತ ಮೌಲ್ಯಕ್ಕೆ ಹೊಂದಿಸುತ್ತೇವೆ. ಆಂತರಿಕ ಲೂಪ್‌ನಲ್ಲಿ ನಾವು ಒಂದು ಶ್ರೇಣಿಯ ಮೌಲ್ಯಗಳನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಎಲ್ಲಾ ಮೂರು ಅಂಶಗಳ (x + arr [fir] + arr [sec]) ಮೊತ್ತವು 0 ಗೆ ಸಮನಾಗಿವೆಯೇ ಅಥವಾ ಇಲ್ಲವೇ ಎಂದು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಅದು 0 ಎಂದು ಕಂಡುಬಂದಲ್ಲಿ, ಇದರರ್ಥ ನಾವು ಮೊದಲ ಜೋಡಿಯನ್ನು ಕಂಡುಕೊಂಡಿದ್ದೇವೆ ಮತ್ತು ರಚನೆಯ ಎಲ್ಲಾ ಪ್ರಸ್ತುತ ಮೌಲ್ಯಗಳನ್ನು ಮುದ್ರಿಸುತ್ತೇವೆ ಮತ್ತು isFound ಮೌಲ್ಯವನ್ನು true ಗೆ ಹೊಂದಿಸಿ.

ನಾವು ಜೋಡಿಗಳಲ್ಲಿ ಒಂದನ್ನು ಕಂಡುಕೊಂಡಿದ್ದೇವೆ ಎಂದು ಇದು ಸೂಚಿಸುತ್ತದೆ. ತ್ರಿವಳಿ ಮೊತ್ತವು 0 ಕ್ಕೆ ಸಮನಾಗಿರದಿದ್ದರೆ, ಮೂರು ಪ್ರಸ್ತುತ ಅಂಶಗಳ ಮೊತ್ತವು 0 ಕ್ಕಿಂತ ಕಡಿಮೆಯಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ಮೊತ್ತವು 0 ಕ್ಕಿಂತ ಕಡಿಮೆಯಿದ್ದರೆ ನಾವು ಫರ್ ಅನ್ನು ಹೆಚ್ಚಿಸುತ್ತೇವೆ, ಅಂದರೆ ನಮ್ಮ ಆರಂಭಿಕ ಮೌಲ್ಯವು ಹೆಚ್ಚಾಗಿದೆ. ಪರಿಸ್ಥಿತಿ ತೃಪ್ತಿ ಹೊಂದಿಲ್ಲದಿದ್ದರೆ. ಮೊತ್ತವು 0 ಕ್ಕಿಂತ ಹೆಚ್ಚಿದೆಯೇ ಎಂದು ನಾವು ಪರಿಶೀಲಿಸುತ್ತೇವೆ. ನಿಜವಾಗಿದ್ದರೆ, ಇಳಿಕೆ ಸೆಕೆಂಡು.

ಈ ರೀತಿಯಾಗಿ, 0 ಗೆ ಮೊತ್ತವಾಗಬಹುದಾದ ಎಲ್ಲಾ ತ್ರಿವಳಿಗಳನ್ನು ನಾವು ಕಂಡುಹಿಡಿಯಲಿದ್ದೇವೆ.

ಶೂನ್ಯ ಮೊತ್ತದೊಂದಿಗೆ ಎಲ್ಲಾ ತ್ರಿವಳಿಗಳನ್ನು ಕಂಡುಹಿಡಿಯಲು ಸಿ ++ ಕೋಡ್

#include<iostream>
#include<algorithm>

using namespace std;

void getTripletZero(int arr[], int n)
{
    bool isFound = false;
    sort(arr, arr+n);

    for (int i=0; i<n-1; i++)
    {
        int fir = i + 1;
        int sec = n - 1;
        int x = arr[i];
        while (fir < sec)
        {
            if (x + arr[fir] + arr[sec] == 0)
            {
                cout<<"("<<x<<" "<<arr[fir]<<" "<< arr[sec]<<")"<<endl;
                fir++;
                sec--;
                isFound = true;
            }
            else if (x + arr[fir] + arr[sec] < 0)
                fir++;
            else
                sec--;
        }
    }
    if (isFound == false)
        cout << " There is no triplet can be formed..!" << endl;
}
int main()
{
    int arr[] = {0,-2,1,3,2,-1};
    int n = sizeof(arr)/sizeof(arr[0]);
    getTripletZero(arr, n);
    return 0;
}
(-2 -1 3)
(-2 0 2)
(-1 0 1)

ಶೂನ್ಯ ಮೊತ್ತದೊಂದಿಗೆ ಎಲ್ಲಾ ತ್ರಿವಳಿಗಳನ್ನು ಹುಡುಕಲು ಜಾವಾ ಕೋಡ್

import java.util.Arrays;

class TripletSumzero
{
    public static void getTripletZero(int arr[], int n)
    {
        boolean isFound = false;

        Arrays.sort(arr);

        for (int i=0; i<n-1; i++)
        {
            int fir = i + 1;
            int sec = n - 1;
            int x = arr[i];
            while (fir < sec)
            {
                if (x + arr[fir] + arr[sec] == 0)
                {
                    System.out.println("(" + x + " "+arr[fir]+ " "+" "+arr[sec]+")");
                    fir++;
                    sec--;
                    isFound = true;
                }
                else if (x + arr[fir] + arr[sec] < 0)
                    fir++;
                else
                    sec--;
            }
        }
        if (isFound == false)
            System.out.println(" There is no triplet can be formed..!");
    }
    public static void main (String[] args)
    {
        int arr[] = {0,-2,1,3,2,-1};
        int n =arr.length;
        getTripletZero(arr, n);
    }
}
(-2 -1  3)
(-2 0  2)
(-1 0  1)

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

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

ಒ (ಎನ್2) ಅಲ್ಲಿ “ಎನ್”  ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ನಾವು ಒ (ಎನ್) ಸಮಯಕ್ಕೆ ಕೊಡುಗೆ ನೀಡುವ ಎರಡು ಪಾಯಿಂಟರ್ ತಂತ್ರವನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ. ಆದರೆ ತಂತ್ರವನ್ನು ಸ್ವತಃ ಒ (ಎನ್) ಸಮಯಕ್ಕೆ ಬಳಸಲಾಗುತ್ತದೆ. ಹೀಗೆ ಅಲ್ಗಾರಿದಮ್ O (n ^ 2) ಸಮಯದಲ್ಲಿ ಚಲಿಸುವಂತೆ ಮಾಡುತ್ತದೆ.

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

ಒ (1) ಯಾವುದೇ ಹೆಚ್ಚುವರಿ ಸ್ಥಳದ ಅಗತ್ಯವಿಲ್ಲ.