You are given an array of N integers, A1, A2 ,…, AN and an integer K. Return the of count of distinct numbers in all windows of size K. Formally, return an array of size N-K+1 where i’th element in this array contains number of distinct elements in sequence Ai, Ai+1 ,…, Ai+k-1.

DNUMS.py

class Solution:
    # @param A : list of integers
    # @param B : integer
    # @return a list of integers
    def dNums(self, A, B):
        mapOfNums = {}
        count = 0
        ptr = -1
        res = []
        if B > len(A) :
            return res
        else :
            for i in range(0, len(A)):
                if mapOfNums.get(A[i], 0) == 0:
                    count = count + 1
                    mapOfNums[A[i]] = 1
                else :
                    mapOfNums[A[i]] += 1
                if i >= B :
                    ptr += 1
                    mapOfNums[A[ptr]] -= 1
                    if mapOfNums[A[ptr]] == 0 :
                        count -= 1
                if i >= B - 1:
                    res.append(count)
        return res
                

class Solution:
# @param A : list of integers
# @return a list of integers
def solve(self, A):
mapOfNums = {}
count = 0
ptr = -1
res = []
if B > len(A) :
return res
else :
for i in range(0, len(A)):
if mapOfNums.get(A[i], 0) == 0:
count = count + 1
mapOfNums[A[i]] = 1
else :
mapOfNums[A[i]] += 1
if i >= B :
ptr += 1
mapOfNums[A[ptr]] -= 1
if mapOfNums[A[ptr]] == 0 :
count -= 1
if i >= B - 1:
res.append(count)
return res

#include <stdio.h>

int countDistinctPairs(int a[], int n, int k) {
int count = 0;

int freq[5000001] = {0}; // Considering the maximum value of a[i] as 10^9 and k as 5*10^9

// Count the frequency of each element in array a and find distinct pairs
for (int i = 0; i < n; i++) {
    int complement = k - a[i];
    
    // Increment count if complement exists and is different from a[i]
    if (complement >= 0 && complement <= 5000000 && freq[complement] > 0 && a[i] != complement) {
        count++;
    }
    
    freq[a[i]]++; // Increment frequency of current element
}

return count;

}

int main() {
int n;
scanf("%d", &n);

int a[n];
for (int i = 0; i < n; i++) {
    scanf("%d", &a[i]);
}

int k;
scanf("%d", &k);

int distinctPairs = countDistinctPairs(a, n, k);

printf("%d\n", distinctPairs);

return 0;

}