N ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿರುವ ಎಲ್ಲಾ ಜೋಡಿಗಳ ಮೇಲೆ f (a [i], a [j]) ಮೊತ್ತ  


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಸಿಸ್ಕೋ ಫೇಸ್ಬುಕ್ ಪಾದಯಾತ್ರೆ ಪಬ್ಲಿಸಿಸ್ ಸೇಪಿಯಂಟ್
ಅರೇ ಹ್ಯಾಶ್ ಮಠ

ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆಯು ಎಲ್ಲಾ ಜೋಡಿಗಳ ಮೇಲೆ n ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿರುವ f (a [i], a [j]) ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಕೇಳುತ್ತದೆ, ಈ ರೀತಿಯಲ್ಲಿ 1 <= i <j <= n ನಮಗೆ ಒದಗಿಸಲಾಗಿದೆ ಎಂದು ಪರಿಗಣಿಸಿ ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿ.

N ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿರುವ ಎಲ್ಲಾ ಜೋಡಿಗಳ ಮೇಲೆ f (a [i], a [j]) ಮೊತ್ತಪಿನ್

ಉದಾಹರಣೆ  

arr[] = {1, 2, 3, 1, 3}
4

ವಿವರಣೆ

ಕೇವಲ 3,1 ಮತ್ತು 3,1 ಜೋಡಿಗಳನ್ನು ಜೋಡಿಸಿ.

arr[]={2, 2, 1, 1, 3}
4

ವಿವರಣೆ

ಇಲ್ಲಿ ಸಹ, ಎರಡು ಜೋಡಿಗಳು (1, 3) ಇವೆ.

ಕ್ರಮಾವಳಿ  

  1. ಎ ಘೋಷಿಸಿ ನಕ್ಷೆ ಮತ್ತು ಹೊಂದಿಸಿ ಔಟ್ಪುಟ್ ಗೆ 0 ಮತ್ತು ಚೆಕ್ಸಮ್ 0 ಗೆ.
  2. ಪ್ರಾರಂಭವಾಗುವ ರಚನೆಯನ್ನು ಹಾದುಹೋಗಿರಿ i = 0 ಗೆ i = n,
    1. Output ಟ್ಪುಟ್ ಮಾಡಿ + = (i * a [i]) - ಚೆಕ್ಸಮ್ ಮತ್ತು ಚೆಕ್ಸಮ್ + = a [i];
    2. ನಕ್ಷೆಯಲ್ಲಿ [i] -1 ಕೀಲಿಯಾಗಿ ಇದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ.
      1. ನಿಜವಾಗಿದ್ದರೆ, ನಕ್ಷೆಯ [i] -1 ಮೌಲ್ಯವನ್ನು .ಟ್‌ಪುಟ್‌ಗೆ ಸೇರಿಸುವ ಮೂಲಕ output ಟ್‌ಪುಟ್ ಅನ್ನು ನವೀಕರಿಸಿ.
      2. ನಕ್ಷೆಯಲ್ಲಿ [i] +1 ಕೀಲಿಯಾಗಿ ಇದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ. ನಿಜವಾಗಿದ್ದರೆ, ನಕ್ಷೆಯ [i] +1 ಮೌಲ್ಯವನ್ನು .ಟ್‌ಪುಟ್‌ಗೆ ಸೇರಿಸುವ ಮೂಲಕ output ಟ್‌ಪುಟ್ ಅನ್ನು ನವೀಕರಿಸಿ.
    3. ಯಾವುದೇ ಸ್ಥಿತಿಯು ತೃಪ್ತಿಪಡದಿದ್ದರೆ, ಅರೇ ಅಂಶದ ಆವರ್ತನವನ್ನು ನಕ್ಷೆಯಲ್ಲಿ ಎಣಿಸಿ ಮತ್ತು ಸಂಗ್ರಹಿಸಿ.
  3. ರಿಟರ್ನ್ .ಟ್‌ಪುಟ್.

ವಿವರಣೆ

ನಮಗೆ ಒಂದು ಸಿಕ್ಕಿತು ಸರಣಿ ಪೂರ್ಣಾಂಕ, ಮೇಲಿನ ಸ್ಥಿತಿಯನ್ನು ಪೂರೈಸುವ ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿರುವ ಎಲ್ಲಾ ಜೋಡಿಗಳ ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯುವುದು ನಮ್ಮ ಕಾರ್ಯ. ಯಾವುದೇ ಜೋಡಿಗಳು ನಿರ್ದಿಷ್ಟ ಸ್ಥಿತಿಯನ್ನು ಪೂರೈಸದಿದ್ದರೆ ನಾವು 0 ಅನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ. ಇದನ್ನು ಪರಿಹರಿಸಲು ನಾವು a ಅನ್ನು ಬಳಸುತ್ತೇವೆ ನಕ್ಷೆ ಮತ್ತು ಏಕಕಾಲದಲ್ಲಿ ಪ್ರತಿ ರಚನೆಯ ಅಂಶದಲ್ಲಿ ಎಲ್ಲಾ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಮಾಡುವುದು ಮತ್ತು ನಮ್ಮ output ಟ್‌ಪುಟ್ ಅನ್ನು ನವೀಕರಿಸುವುದು ಮತ್ತು ನಮ್ಮ ನಕ್ಷೆಯಲ್ಲಿ ಪರಿಶೀಲಿಸುವುದು. ನಮ್ಮ ನೈಜ ಉತ್ಪಾದನೆಯ ಮೇಲೆ ಕಣ್ಣಿಡುವ ಹೆಚ್ಚುವರಿ ವೇರಿಯಬಲ್ ಅನ್ನು ನಾವು ತೆಗೆದುಕೊಳ್ಳಲಿದ್ದೇವೆ, ಅದನ್ನು ನಾವು ಚೆಕ್ಸಮ್ ಎಂದು ಕರೆಯಬಹುದು. ನಾವು output ಟ್‌ಪುಟ್ ಮತ್ತು ಚೆಕ್‌ಸಮ್ ಅನ್ನು 0 ಗೆ ಹೊಂದಿಸುತ್ತೇವೆ. ಮತ್ತು ನಾವು n ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಎಲ್ಲಾ ಜೋಡಿಗಳ ಮೇಲೆ f (a [i], a [j]) ಅನ್ನು ಹೇಗೆ ಕಾಣುತ್ತೇವೆ.

ಸಹ ನೋಡಿ
ಸಣ್ಣ ಎಲಿಮೆಂಟ್ ನಿಖರವಾಗಿ ಕೆ ಟೈಮ್ಸ್ ಪುನರಾವರ್ತಿಸಲಾಗಿದೆ

ನಾವು ಒಂದು ಉದಾಹರಣೆಯನ್ನು ಪರಿಗಣಿಸೋಣ:

ಉದಾಹರಣೆ

ಅರ್ [] = {1, 2, 3, 1, 3}, put ಟ್‌ಪುಟ್: 0, ಚೆಕ್ಸಮ್: 0

  • ನಾವು 0 ನೇ ಸೂಚ್ಯಂಕ ಅಂಶವನ್ನು ಆರಿಸುತ್ತೇವೆ ಮತ್ತು ನಂತರ ಅದರ ಸೂಚ್ಯಂಕದಿಂದ ಗುಣಿಸಿ, ಮತ್ತು ಚೆಕ್‌ಸಮ್ ಅನ್ನು ಕಳೆಯುತ್ತೇವೆ ಮತ್ತು ಅದನ್ನು output ಟ್‌ಪುಟ್‌ಗೆ ಸೇರಿಸುತ್ತೇವೆ,

Put ಟ್ಪುಟ್: 0, ಚೆಕ್ಸಮ್: 1

ನಕ್ಷೆ {1 = 1}, ಯಾವುದೇ ಸ್ಥಿತಿಯು ತೃಪ್ತಿಪಡಿಸುವುದಿಲ್ಲ, ಆದ್ದರಿಂದ ನಾವು ಮೌಲ್ಯವನ್ನು ನಕ್ಷೆಯಲ್ಲಿ ಸೇರಿಸುತ್ತೇವೆ.

  • 1 ಗೆst ಸೂಚ್ಯಂಕ ಅಂಶ, ಅದೇ ಕಾರ್ಯಾಚರಣೆಯನ್ನು ಮಾಡಿ, ಆದರೆ ಈ ಸಮಯದಲ್ಲಿ, ಅದು ಮೊದಲ ವೇಳೆ ಹೇಳಿಕೆಯ ಸ್ಥಿತಿಯನ್ನು ಪೂರೈಸುತ್ತದೆ, ಮತ್ತು ನವೀಕರಿಸಿದ output ಟ್‌ಪುಟ್ ಪಡೆದ ನಂತರ, ನಾವು ಪಡೆಯುತ್ತೇವೆ.

ನವೀಕರಿಸಿದ put ಟ್‌ಪುಟ್: 0, ಚೆಕ್ಸಮ್: 3

ನಕ್ಷೆ {1 = 1, 2 = 1}, ಈ ಸಮಯದಲ್ಲಿ ನಾವು ಆ ಮೌಲ್ಯವನ್ನು ಅದರ ನಕ್ಷೆಯೊಂದಿಗೆ ಸೇರಿಸುತ್ತೇವೆ.

  • 2 ಗೆnd ಅಂಶ, ಮೊದಲಿನಂತೆಯೇ ಅದೇ ಕಾರ್ಯಾಚರಣೆ, ಈ ಬಾರಿ ಅದು [i] -1 ಅಂಶವನ್ನು ಕಂಡುಕೊಳ್ಳುತ್ತದೆ ಮತ್ತು ನಾವು ನವೀಕರಿಸಿದ output ಟ್‌ಪುಟ್ ಪಡೆದುಕೊಂಡಿದ್ದೇವೆ:

ನವೀಕರಿಸಿದ put ಟ್‌ಪುಟ್: 2, ಚೆಕ್ಸಮ್: 6

ನಕ್ಷೆ {1 = 1, 2 = 1, 3 = 1}, ಅಂಶ ಮತ್ತು ಅದರ ಆವರ್ತನವನ್ನು ಸೇರಿಸುತ್ತದೆ.

  • 3 ನೇ ಅಂಶಕ್ಕಾಗಿ, ಅದು ಎರಡನೆಯ ಹೇಳಿಕೆಯನ್ನು ತೃಪ್ತಿಪಡಿಸುತ್ತದೆ, ಅಂದರೆ ನಕ್ಷೆಯು [i] +1 ಮೌಲ್ಯವನ್ನು ಹೊಂದಿದ್ದರೆ ಅದು ಅನುಸರಿಸುತ್ತದೆ, ನಂತರ ನಾವು ನವೀಕರಿಸಿದ output ಟ್‌ಪುಟ್ ಪಡೆದ ನಂತರ:

ನವೀಕರಿಸಿದ put ಟ್‌ಪುಟ್: 0, ಚೆಕ್ಸಮ್: 7, ನಕ್ಷೆ: {1 = 2, 2 = 1, 3 = 1}

  • 4 ನೇ ಅಂಶಕ್ಕಾಗಿ, ಮೊದಲ if ಹೇಳಿಕೆಯನ್ನು ಹಾದುಹೋದ ನಂತರ.

ನವೀಕರಿಸಿದ put ಟ್‌ಪುಟ್: 4, ಚೆಕ್ಸಮ್: 10

ನಕ್ಷೆ {1 = 2, 2 = 1, 3 = 2}

ಮತ್ತು ನಾವು put ಟ್ಪುಟ್ ಅನ್ನು ಹಿಂತಿರುಗಿಸುತ್ತೇವೆ: 4

ಕೋಡ್  

N ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಎಲ್ಲಾ ಜೋಡಿಗಳ ಮೇಲೆ f (a [i], a [j]) ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಲು C ++ ಕೋಡ್

#include<iostream>
#include<unordered_map>

using namespace std;

int sum(int a[], int n)
{
    unordered_map<int, int> count;

    int output = 0, checksum = 0;
    for (int i = 0; i < n; i++)
    {
        output += (i * a[i]) - checksum;
        checksum += a[i];

        if (count[a[i] - 1])
            output -= count[a[i] - 1];

        if (count[a[i] + 1])
            output += count[a[i] + 1];

        count[a[i]]++;
    }
    return output;
}
int main()
{
    int a[] = { 1, 2, 3, 1, 3 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << sum(a, n);
    return 0;
}
4

N ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿ ಎಲ್ಲಾ ಜೋಡಿಗಳ ಮೇಲೆ f (a [i], a [j]) ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯಲು ಜಾವಾ ಕೋಡ್

import java.util.HashMap;
public class pairSum
{
    public static int sum(int a[], int n)
    {
        HashMap<Integer,Integer> count = new HashMap<Integer,Integer>();

        int output = 0, checksum = 0;
        for (int i = 0; i < n; i++)
        {
            output += (i * a[i]) - checksum;
            checksum += a[i];

            if (count.containsKey(a[i] - 1))
                output -= count.get(a[i] - 1);

            if (count.containsKey(a[i] + 1))
                output += count.get(a[i] + 1);

            if(count.containsKey(a[i]))
            {
                count.put(a[i], count.get(a[i]) + 1);
            }
            else
            {
                count.put(a[i], 1);
            }
        }
        return output;
    }
    public static void main(String args[])
    {
        int a[] = { 1, 2, 3, 1, 3 };
        int n = a.length;
        System.out.println(sum(a, n));
    }
}
4

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

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

ಓ (ಎನ್) ಅಲ್ಲಿ “ಎನ್” ರಚನೆಯ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಹ್ಯಾಶ್‌ಮ್ಯಾಪ್‌ನ ಬಳಕೆಯು ಹುಡುಕಾಟ / ಅಳಿಸುವಿಕೆ / ಒಳಸೇರಿಸುವಿಕೆಯನ್ನು ನಿರ್ವಹಿಸಲು ನಮಗೆ ಅನುಮತಿಸುತ್ತದೆ ಒ (1). ಆದ್ದರಿಂದ n ಪೂರ್ಣಾಂಕಗಳ ಒಂದು ಶ್ರೇಣಿಯಲ್ಲಿನ ಎಲ್ಲಾ ಜೋಡಿಗಳ ಮೇಲೆ f (a [i], a [j]) ಮೊತ್ತವನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸಮಯದ ಸಂಕೀರ್ಣತೆಯನ್ನು ರೇಖೀಯಕ್ಕೆ ಇಳಿಸಲಾಗುತ್ತದೆ.

ಸಹ ನೋಡಿ
ವರ್ಡ್ ಪ್ಯಾಟರ್ನ್

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

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