All numbers with specific difference

JavaView on GFG

Time: O(n)

Space: O(n)

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?