ನೀಡಿರುವ ಸಂಖ್ಯೆಗೆ ಸಮಾನವಾದ ಉತ್ಪನ್ನದೊಂದಿಗೆ ತ್ರಿವಳಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸಿ


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

“ಕೊಟ್ಟಿರುವ ಸಂಖ್ಯೆಗೆ ಸಮನಾದ ಉತ್ಪನ್ನದೊಂದಿಗೆ ತ್ರಿವಳಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸು” ಎಂಬ ಸಮಸ್ಯೆ ನಮಗೆ ಒಂದು ಪೂರ್ಣಾಂಕ ರಚನೆ ಮತ್ತು ಸಂಖ್ಯೆಯನ್ನು ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ m. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ಉತ್ಪನ್ನದ ಒಟ್ಟು ತ್ರಿವಳಿಗಳ ಸಂಖ್ಯೆಯನ್ನು m ಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಎಂದು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ.

ಉದಾಹರಣೆ

arr[] = {1,5,2,6,10,3}
m=30
3

ವಿವರಣೆ

ಮೀಗೆ ಸಮಾನವಾದ ಉತ್ಪನ್ನವನ್ನು ರೂಪಿಸಿದ ತ್ರಿವಳಿಗಳು (1,5,6), (5,2,3) ಮತ್ತು (1,3,10)

ನೀಡಿರುವ ಸಂಖ್ಯೆಗೆ ಸಮಾನವಾದ ಉತ್ಪನ್ನದೊಂದಿಗೆ ತ್ರಿವಳಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸಿ

arr[] = {2,4,5,1,10}
m=20
2

ವಿವರಣೆ

ಮೀಗೆ ಸಮಾನವಾದ ಉತ್ಪನ್ನವನ್ನು ರೂಪಿಸಿದ ತ್ರಿವಳಿಗಳು (2,1,10), (4,5,1)

ಕ್ರಮಾವಳಿ

  1. ಎ ಘೋಷಿಸಿ ನಕ್ಷೆ.
  2. ಪ್ರತಿ ಅಂಶದ ಸೂಚಿಯನ್ನು ನಕ್ಷೆಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ ಸರಣಿ.
  3. Output ಟ್ಪುಟ್ ಅನ್ನು 0 ಗೆ ಹೊಂದಿಸಿ.
  4. ನೆಸ್ಟೆಡ್ ಲೂಪ್ ಬಳಸಿ ಮತ್ತೆ ಶ್ರೇಣಿಯನ್ನು ಹಾದುಹೋಗುತ್ತದೆ:
    1. ((Arr [i] * arr [j] <= m) && (arr [i] * arr [j]! = 0) && (m% (arr [i] * arr [j]) == 0 )).
      1. ಇದು ನಿಜವೆಂದು ಕಂಡುಬಂದಲ್ಲಿ, m / (arr [i] * arr [j]) ಅನ್ನು ಕಂಡುಹಿಡಿಯಿರಿ ಮತ್ತು ಅದನ್ನು ನಕ್ಷೆಯಲ್ಲಿ ಹುಡುಕಿ.
    2. ಇದಕ್ಕಾಗಿ ಸಹ ಪರಿಶೀಲಿಸಿ, ನಾವು ಕಂಡುಕೊಂಡ ಮೂರನೇ ಅಂಶವು ಪ್ರಸ್ತುತ ಎರಡು ಅಂಶಗಳಿಗೆ (arr [i] ಮತ್ತು arr [j] ಗೆ ಸಮನಾಗಿರುವುದಿಲ್ಲ.
      1. ಸ್ಥಿತಿಯು ತೃಪ್ತಿಪಡಿಸಿದರೆ, ನಂತರ output ಟ್‌ಪುಟ್‌ನ ಸಂಖ್ಯೆಯನ್ನು 1 ಹೆಚ್ಚಿಸಿ.
  5. ರಿಟರ್ನ್ .ಟ್‌ಪುಟ್.

ವಿವರಣೆ

ಕೊಟ್ಟಿರುವ ಸಂಖ್ಯೆ m ಗೆ ಸಮನಾಗಿರಬೇಕು ಎಂಬ ತ್ರಿವಳಿಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ನಮ್ಮ ಕಾರ್ಯ. ಈ ಪ್ರಶ್ನೆಯನ್ನು ಪರಿಹರಿಸಲು ನಾವು ನಿಷ್ಕಪಟ ವಿಧಾನವನ್ನು ಬಳಸಲು ಹೋಗುವುದಿಲ್ಲ, ಇದು ನಮಗೆ ಹೆಚ್ಚು ಸಮಯ ಖರ್ಚಾಗುತ್ತದೆ. ತ್ರಿವಳಿಗಳ ಪ್ರತಿಯೊಂದು ಅಂಶವನ್ನು ಆರಿಸುವುದಕ್ಕಿಂತ ಹೆಚ್ಚಾಗಿ, ನಾವು ಬಳಸುತ್ತೇವೆ ಹ್ಯಾಶಿಂಗ್.

ನಾವು ಕೊಟ್ಟಿರುವ ವ್ಯೂಹವನ್ನು ಹಾದುಹೋಗುತ್ತೇವೆ ಮತ್ತು ಪ್ರತಿ ರಚನೆಯ ಅಂಶದ ಸೂಚಿಯನ್ನು ನಿರ್ದಿಷ್ಟ ಶ್ರೇಣಿಯ ಅಂಶದೊಂದಿಗೆ ನಕ್ಷೆಯಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ಇದನ್ನು ಮಾಡಲಾಗುತ್ತಿದೆ ಏಕೆಂದರೆ ನಂತರ, ನಾವು ಕಂಡುಕೊಂಡ ಅಂಶವನ್ನು ಪುನರಾವರ್ತಿಸಬಾರದು ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಲಿದ್ದೇವೆ. ಅಂಶವು ಒಂದೇ ಸೂಚಿಯನ್ನು ಹೊಂದಿದ್ದರೆ. ಇದರರ್ಥ ನಾವು ಒಂದೇ ಶ್ರೇಣಿಯ ಅಂಶವನ್ನು ತ್ರಿವಳಿಗಾಗಿ ಎರಡು ಬಾರಿ ಎಣಿಸುವುದಿಲ್ಲ.

ರಚನೆಯ ಅಡ್ಡಾದಿಡ್ಡಿಯ ನಂತರ, ನಾವು ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್‌ನಲ್ಲಿ ಮೌಲ್ಯಗಳನ್ನು ಹೊಂದಿದ್ದೇವೆ. Output ಟ್‌ಪುಟ್‌ನ ಮೌಲ್ಯವನ್ನು 0 ಗೆ ಹೊಂದಿಸಿ. ಈಗ, ನಾವು ನೆಸ್ಟೆಡ್ ಲೂಪ್ ಅನ್ನು ಬಳಸಲಿದ್ದೇವೆ. ಇದರಲ್ಲಿ ನಾವು ಹೊರಗಿನ ಲೂಪ್‌ನಲ್ಲಿ ಒಂದು ಅಂಶವನ್ನು ತೆಗೆದುಕೊಳ್ಳುತ್ತೇವೆ ಮತ್ತು ಆಂತರಿಕ ಲೂಪ್‌ನಲ್ಲಿ ಮುಂದಿನ ಅಂಶವನ್ನು ಆರಿಸಿಕೊಳ್ಳಿ. ನಂತರ ನಾವು ಮೂರನೇ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಲಿದ್ದೇವೆ. ಮೂರನೆಯ ಅಂಶವನ್ನು ಕಂಡುಹಿಡಿಯಲು 'if statement' ನಲ್ಲಿರುವ ಎಲ್ಲಾ ಸ್ಥಿತಿಯನ್ನು ಬಳಸಲಾಗುತ್ತದೆ. Arr [i] * arr [j] ಮಾಡಿದ ನಂತರ ನಾವು ಕಂಡುಹಿಡಿಯಬೇಕಾಗಿರುವುದು ಮೂರನೆಯ ಅಂಶವಾಗಿದೆ. ಆದ್ದರಿಂದ ಸರಳ ಟಿಪ್ಪಣಿಯಲ್ಲಿ, a * b * c = m if ಆಗಿದ್ದರೆ c = m / a * b.

ನಂತರ ಮೂರನೇ ಅಂಶವನ್ನು ಪರಿಶೀಲಿಸಿ, ಅದು ನಕ್ಷೆಯಲ್ಲಿ ಪ್ರಸ್ತುತಪಡಿಸಿದರೆ, ನಾವು ಅದನ್ನು ಕಂಡುಕೊಂಡಿದ್ದೇವೆ ಎಂದರ್ಥ. ನಾವು ಕಂಡುಕೊಂಡ ಅಂಶವು ತ್ರಿವಳಿಗಳ ಪ್ರಸ್ತುತ ಎರಡು ಅಂಶಗಳಿಗೆ ಸಮನಾಗಿರಬಾರದು ಎಂದು ನಾವು ಪರಿಶೀಲಿಸಬೇಕಾಗಿದೆ. ಅಲ್ಲದೆ, ಪ್ರಸ್ತುತ ಸೂಚ್ಯಂಕವನ್ನು ಮೊದಲು ಪುನರಾವರ್ತಿಸಬಾರದು. ಎಲ್ಲಾ ಷರತ್ತುಗಳು ತೃಪ್ತಿ ಹೊಂದಿದ್ದರೆ ನಾವು output ಟ್‌ಪುಟ್‌ನ ಸಂಖ್ಯೆಯನ್ನು 1 ರಿಂದ ಹೆಚ್ಚಿಸುತ್ತೇವೆ. ಇದರರ್ಥ ನಾವು ಒಂದು ಅಥವಾ ಹೆಚ್ಚಿನ ತ್ರಿವಳಿಗಳನ್ನು ಹೊಂದಿದ್ದೇವೆ. ನಂತರ ಕೊನೆಗೆ ಸುಮ್ಮನೆ return ಟ್‌ಪುಟ್ ನೀಡಿ.

ಕೊಟ್ಟಿರುವ ಸಂಖ್ಯೆಗೆ ಸಮಾನವಾದ ಉತ್ಪನ್ನದೊಂದಿಗೆ ತ್ರಿವಳಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸಲು ಸಿ ++ ಕೋಡ್

#include<iostream>
#include<unordered_map>
using namespace std;

int getProductTriplets(int arr[], int n, int m)
{
    unordered_map<int, int> numindex;
    for (int i = 0; i < n; i++)
        numindex[arr[i]] = i;

    int output = 0;

    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0) && (m % (arr[i] * arr[j]) == 0))
            {
                int third = m / (arr[i] * arr[j]);
                auto it = numindex.find(third);

                if (third != arr[i] && third != arr[j]&& it != numindex.end() && it->second > i&& it->second > j)
                    output++;
            }
        }
    }
    return output;
}
int main()
{
    int arr[] = {1,5,2,6,10,3};
    int n = sizeof(arr) / sizeof(arr[0]);
    int m = 30;

    cout <<"Total product triplets are: "<<getProductTriplets(arr, n, m);
    return 0;
}
Total product triplets are: 3

ನಿರ್ದಿಷ್ಟ ಸಂಖ್ಯೆಗೆ ಸಮಾನವಾದ ಉತ್ಪನ್ನದೊಂದಿಗೆ ತ್ರಿವಳಿಗಳ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸಲು ಜಾವಾ ಕೋಡ್

import java.util.HashMap;

class TripletProductPair
{
    public static int getProductTriplets(int arr[], int n, int m)
    {
        HashMap<Integer, Integer> numindex = new HashMap<Integer, Integer>(n);
        for (int i = 0; i < n; i++)
            numindex.put(arr[i], i);

        int output = 0;
        for (int i = 0; i < n - 1; i++)
        {
            for (int j = i + 1; j < n; j++)
            {

                if ((arr[i] * arr[j] <= m) && (arr[i] * arr[j] != 0) && (m % (arr[i] * arr[j]) == 0))
                {
                    int third = m / (arr[i] * arr[j]);

                    numindex.containsKey(third);
                    if (third != arr[i] && third != arr[j]&& numindex.containsKey(third) && numindex.get(third) > i && numindex.get(third) > j)
                    {
                        output++;
                    }
                }
            }
        }
        return output;
    }
    public static void main(String[] args)
    {
        int arr[] = {1,5,2,6,10,3};
        int m = 30;
        System.out.println("Total product triplets are: "+getProductTriplets(arr, arr.length, m));
    }
}
Total product triplets are: 3

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

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

ಒ (ಎನ್2ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ನಾವು ಎರಡು ನೆಸ್ಟೆಡ್ ಲೂಪ್‌ಗಳನ್ನು ಬಳಸಿದ್ದೇವೆ ಮತ್ತು ಮೂರನೇ ಅಂಶವನ್ನು ಹುಡುಕಲು ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಅನ್ನು ಬಳಸಿದ್ದೇವೆ. ಆದ್ದರಿಂದ, ಈ ಶೋಧ ಕಾರ್ಯಾಚರಣೆಯನ್ನು O (1) ನಲ್ಲಿ ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್ ಮಾಡುತ್ತಿದೆ, ಇದನ್ನು ಹಿಂದೆ O (N) ಸಮಯದಲ್ಲಿ ನಿಷ್ಕಪಟ ವಿಧಾನದಲ್ಲಿ ಮಾಡಲಾಗುತ್ತಿತ್ತು. ಹೀಶ್‌ಮ್ಯಾಪ್‌ನಿಂದಾಗಿ ಈ ವೇಗ ಹೆಚ್ಚಾಗುತ್ತದೆ.

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

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಏಕೆಂದರೆ ನಾವು ಎಲ್ಲಾ ಅಂಶಗಳನ್ನು ನಕ್ಷೆಯಲ್ಲಿ ಸಂಗ್ರಹಿಸುತ್ತೇವೆ. ಸ್ಥಳದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ.