Find the number of elements X such that X + K also exists in the array
Given an array a[] and an integer k, find the number of elements x in this array such that the sum of x and k is also present in the array.
Examples:
Input: { 3, 6, 2, 8, 7, 6, 5, 9 } and k = 2
Output: 5
Explanation:
Elements {3, 6, 7, 6, 5} in this array have x + 2 value that is
{5, 8, 9, 8, 7} present in this array.
Input: { 1, 2, 3, 4, 5} and k = 1
Output: 4
Explanation:
Elements {1, 2, 3, 4} in this array have x + 2 value that is
{2, 3, 4, 5} present in this array.
The problem is similar to finding the count of pairs with a given sum in an Array.
Brute Force Approach:
- Initialize a counter variable to 0 to keep track of the number of elements that satisfy the given condition.
- Use nested loops to iterate over all possible pairs of elements in the array.
- For each pair, check if their sum is equal to k plus any element in the array. If it is, increment the counter by 1.
- After all pairs have been checked, return the counter variable as the output.
Below is the implementation of the above approach:
C++
// C++ implementation of find number // of elements x in this array // such x+k also present in this array. #include <bits/stdc++.h> using namespace std; // Function to return the // count of element x such that // x+k also lies in this array int count_element( int N, int K, int * arr) { int count = 0; for ( int i=0; i<N; i++){ for ( int j=0; j<N; j++){ if (arr[j] == arr[i] + K){ count++; break ; } } } return count; } // Driver code int main() { // array initialisation int arr[] = { 3, 6, 2, 8, 7, 6, 5, 9 }; // size of array int N = sizeof (arr) / sizeof (arr[0]); // initialise k int K = 2; cout << count_element(N, K, arr); return 0; } |
Java
import java.util.Arrays; public class Main { // Function to return the count of element x such that x+k also lies in this array public static int count_element( int N, int K, int [] arr) { int count = 0 ; for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) { if (arr[j] == arr[i] + K) { count++; break ; } } } return count; } // Driver code public static void main(String[] args) { // array initialization int [] arr = { 3 , 6 , 2 , 8 , 7 , 6 , 5 , 9 }; // size of array int N = arr.length; // initialize k int K = 2 ; System.out.println(count_element(N, K, arr)); } } |
Python3
# Python3 implementation of find number # of elements x in this array # such x+k also present in this array. # array initialization arr = [ 3 , 6 , 2 , 8 , 7 , 6 , 5 , 9 ] # Function to return the count of element x such that # x+k also lies in this array def count_element(N: int , K: int , arr: list ) - > int : count = 0 for i in range (N): for j in range (N): if arr[j] = = arr[i] + K: count + = 1 break return count # size of array N = len (arr) # initialize k K = 2 print (count_element(N, K, arr)) |
C#
using System; class GFG { // Function to return the count of element x // such that x+k also lies in this array public static int count_element( int N, int K, int [] arr) { int count = 0; for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) { if (arr[j] == arr[i] + K) { count++; break ; } } } return count; } // Driver code public static void Main( string [] args) { // array initialization int [] arr = { 3, 6, 2, 8, 7, 6, 5, 9 }; // size of array int N = arr.Length; // initialize k int K = 2; Console.WriteLine(count_element(N, K, arr)); } } // Contributed by phasing17 |
Javascript
// Function to return the // count of element x such that // x+k also lies in this array function count_element(N, K, arr) { let count = 0; for (let i=0; i<N; i++){ for (let j=0; j<N; j++){ if (arr[j] == arr[i] + K){ count++; break ; } } } return count; } // Driver code const arr = [3, 6, 2, 8, 7, 6, 5, 9]; // size of array const N = arr.length; // initialise k const K = 2; console.log(count_element(N, K, arr)); //This code is written by Sundaram |
5
Time Complexity: O(N^2)
Auxiliary Space: O(1)
Efficient Approach:
The efficient approach to solve the problem is to use a HashMap, the key in map will act as the unique element in this array and the corresponding value will tell us the frequency of this element.
Iterate over this map and find for each key x in this map whether the key x + k exists in the map or not, if exist then add this frequency to the answer i.e for this element x we have x+k in this array. Finally, return the answer.
Below is the implementation of the above approach:
C++
// C++ implementation of find number // of elements x in this array // such x+k also present in this array. #include <bits/stdc++.h> using namespace std; // Function to return the // count of element x such that // x+k also lies in this array int count_element( int N, int K, int * arr) { // Key in map will store elements // and value will store the // frequency of the elements map< int , int > mp; for ( int i = 0; i < N; ++i) mp[arr[i]]++; int answer = 0; for ( auto i : mp) { // Find if i.first + K is // present in this map or not if (mp.find(i.first + K) != mp.end()) // If we find i.first or key + K in this map // then we have to increase in answer // the frequency of this element answer += i.second; } return answer; } // Driver code int main() { // array initialisation int arr[] = { 3, 6, 2, 8, 7, 6, 5, 9 }; // size of array int N = sizeof (arr) / sizeof (arr[0]); // initialise k int K = 2; cout << count_element(N, K, arr); return 0; } |
Java
// Java implementation of find number // of elements x in this array // such x+k also present in this array. import java.util.*; class GFG{ // Function to return the // count of element x such that // x+k also lies in this array static int count_element( int N, int K, int [] arr) { // Key in map will store elements // and value will store the // frequency of the elements HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); for ( int i = 0 ; i < N; ++i) if (mp.containsKey(arr[i])){ mp.put(arr[i], mp.get(arr[i])+ 1 ); } else { mp.put(arr[i], 1 ); } int answer = 0 ; for (Map.Entry<Integer,Integer> i : mp.entrySet()) { // Find if i.first + K is // present in this map or not if (mp.containsKey(i.getKey() + K) ) // If we find i.first or key + K in this map // then we have to increase in answer // the frequency of this element answer += i.getValue(); } return answer; } // Driver code public static void main(String[] args) { // array initialisation int arr[] = { 3 , 6 , 2 , 8 , 7 , 6 , 5 , 9 }; // size of array int N = arr.length; // initialise k int K = 2 ; System.out.print(count_element(N, K, arr)); } } // This code is contributed by Princi Singh |
Python3
# Python3 implementation of find number # of elements x in this array # such x+k also present in this array. # Function to return the # count of element x such that # x+k also lies in this array def count_element(N, K, arr): # Key in map will store elements # and value will store the # frequency of the elements mp = dict () for i in range (N): mp[arr[i]] = mp.get(arr[i], 0 ) + 1 answer = 0 for i in mp: # Find if i.first + K is # present in this map or not if i + K in mp: # If we find i.first or key + K in this map # then we have to increase in answer # the frequency of this element answer + = mp[i] return answer # Driver code if __name__ = = '__main__' : # array initialisation arr = [ 3 , 6 , 2 , 8 , 7 , 6 , 5 , 9 ] # size of array N = len (arr) # initialise k K = 2 print (count_element(N, K, arr)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation of find number // of elements x in this array // such x+k also present in this array. using System; using System.Collections.Generic; public class GFG{ // Function to return the // count of element x such that // x+k also lies in this array static int count_element( int N, int K, int [] arr) { // Key in map will store elements // and value will store the // frequency of the elements Dictionary< int , int > mp = new Dictionary< int , int >(); for ( int i = 0; i < N; ++i) if (mp.ContainsKey(arr[i])){ mp[arr[i]] = mp[arr[i]]+1; } else { mp.Add(arr[i], 1); } int answer = 0; foreach (KeyValuePair< int , int > i in mp) { // Find if i.first + K is // present in this map or not if (mp.ContainsKey(i.Key + K) ) // If we find i.first or key + K in this map // then we have to increase in answer // the frequency of this element answer += i.Value; } return answer; } // Driver code public static void Main(String[] args) { // array initialisation int []arr = { 3, 6, 2, 8, 7, 6, 5, 9 }; // size of array int N = arr.Length; // initialise k int K = 2; Console.Write(count_element(N, K, arr)); } } // This code contributed by Princi Singh |
Javascript
<script> // Javascript implementation of find number // of elements x in this array // such x+k also present in this array. // Function to return the // count of element x such that // x+k also lies in this array function count_element(N, K, arr) { // Key in map will store elements // and value will store the // frequency of the elements let mp = new Map(); for (let i = 0; i < N; ++i) if (mp.has(arr[i])) { mp.set(arr[i], mp.get(arr[i]) + 1) } else { mp.set(arr[i], 1) } let answer = 0; for (let i of mp) { // Find if i.first + K is // present in this map or not if (mp.has(i[0] + K)) // If we find i.first or key + K in this map // then we have to increase in answer // the frequency of this element answer += i[1]; } return answer; } // Driver code // array initialisation let arr = [3, 6, 2, 8, 7, 6, 5, 9]; // size of array let N = arr.length; // initialise k let K = 2; document.write(count_element(N, K, arr)); // This code is contributed by gfgking </script> |
5
Time Complexity: O(N log N), where N is the size of the input array
Space Complexity: O(N)