Sort by

recency

|

1256 Discussions

|

  • + 0 comments

    Sort the array then use binary search

    1. Time Complexity: O(nlog(n))
    2. Space Complexity: O(1)
    bool binary_search(int* arr, int target, int l, int r){
        while(l <= r){
            int mid = l + (r-l)/2;
            if (arr[mid] == target){
                return true;
            }
            else if (arr[mid] > target){
                r = mid-1;
            }
            else{
                l = mid+1;
            }
        }
        return false;
    }
    
    void swap(int* a, int* b){
        int temp = *a;
        *a = *b;
        *b = temp;
    }
    
    int partition(int* arr, int l, int r){
        int pivot = arr[r];
        int start_idx = l;
        int bigger_idx = l;
        for (int i = start_idx; i<r; i++){
            if (arr[i] < pivot){
                swap(&arr[i], &arr[bigger_idx]);
                bigger_idx ++;
            }
        }
        swap(&arr[r], &arr[bigger_idx]);
        return bigger_idx;
    }
    
    int* my_q_sort(int* arr, int l, int r){
        if (l < r){
            int idx = partition(arr, l, r);
            my_q_sort(arr, l, idx-1);
            my_q_sort(arr, idx+1, r);
        }
        return arr;
    }
    
    int pairs(int k, int arr_count, int* arr) {
        int res_count = 0;
        arr = my_q_sort(arr, 0, arr_count-1);
        for (int i = 0; i<arr_count-1; i++){
            bool find_pair = binary_search(arr, arr[i]+k, 0, arr_count-1);
            if (find_pair == true){
                res_count ++;
            } 
        }
        return res_count;
    }
    
  • + 0 comments
    function pairs(k, arr) {
        // Write your code here
        let map = arr.reduce((acc, id) => {
            acc.set(id, (acc.get(id) || 0) + 1);
            return acc;
        }, new Map());
        let count = 0;
        for(let [key, val] of map) {
            if(map.has(key-k)) count += val*map.get(key-k);
        }
        return count;
    }
    
  • + 0 comments
    import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;
    
    public class Solution {
    
        public static void main(String[] args) throws Exception  {
    
    		//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    		Scanner inr = new Scanner (System.in);
    		int n = inr.nextInt();
    		int k = inr.nextInt();
    		int num[] = new int[n];
    		for(int i=0;i<n;i++){
    			num[i] = inr.nextInt();
    		}
    		Arrays.sort(num);
    		int count = 0;
    		for(int i=0;i<n;i++){
    			for(int j=i+1;j<n;j++){
    				if(num[j] - num[i] == k || num[i] - num[j] == k){
    					count++;
    				}
    				else if(num[j] - num[i] > k || num[i] - num[j] > k){
    					break;
    				}
    			}
    		}
    		System.out.println(count);
    	}
    
    }
    
  • + 0 comments

    Java:

    public static int pairs(int k, List<Integer> arr) {
        int pairsCount =0;
        Set<Integer> arrSet = arr.stream().collect(Collectors.toSet());
        for (Integer item : arr) {
            if (arrSet.contains(item+k)) {
                pairsCount++;
            }
        }
        return pairsCount;
    }
    
  • + 0 comments

    def pairs(k, arr): arr_set = set(arr) return len({x + k for x in arr_set} & arr_set)