All numbers with specific difference

JavaView on GFG

Time: O(n)

Space: O(n)

Problem Overview

Find all pairs in array with absolute difference equal to k.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find all pairs in array with absolute difference equal to k. Sort + two pointers or hashset lookup.

Algorithm

1Sort array. Two pointers i=0, j=1. If diff == k: record, advance both. If diff < k: j++. Else i++.

Common Pitfalls

• Handle duplicates carefully. If k=0: find all duplicate pairs. Sort + two-pointer avoids duplicates naturally.

All numbers with specific difference.java

Java

// Approach: Use a HashSet to store all elements. For each element x, check if x - k exists in the set.
// Time: O(n) Space: O(n)
class Solution {
    public int getCount(int n, int d) {
        int s = 1; // start
        int e = n; // end
        int temp = 0;

        // binary search to get that temp
        while (s <= e) {
            int mid = s + (e - s) / 2;
            if (mid - sumOfDig(mid) >= d) { // condition given
                temp = mid;
                e = mid - 1;
            } else
                s = mid + 1;
        }

        return temp == 0 ? 0 : n - temp + 1;
    }

    public int sumOfDig(int n) {
        int sum = 0;
        while (n > 0) {
            int dig = n % 10;
            sum += dig;
            n = n / 10;
        }
        
        return sum;
    }
};

Was this solution helpful?