Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 2 down vote favorite
2
 
    import java.util.Scanner;

public class k_diff {

    public int process() {
        Scanner scanner = new Scanner(System.in);
        int total_nums = scanner.nextInt();
        int diff = scanner.nextInt();
        int ary_nums[] = new int[total_nums];
        for (int i = 0; i < total_nums; i++) {
            ary_nums[i] = scanner.nextInt();
        }
        int len = ary_nums.length;
        int count = 0;
        for (int j = 0; j < len - 1; j++) {
            for (int k = j + 1; k < len; k++) {
                if (Math.abs(ary_nums[j] - ary_nums[k]) == diff) {
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String args[]) {
        k_diff kdiff = new k_diff();
        System.out.println(kdiff.process());
    }
}

Puzzle Description

Given N numbers, [N<=10^5] we need to count the total pairs of numbers that have a difference of K. [K>0 and K<1e9]

Input Format:

  • 1st line contains N & K (integers).

  • 2nd line contains N numbers of the set. All the N numbers are assured to be distinct.

Output Format:

  • One integer saying the no of pairs of numbers that have a diff K.

How can I improve the above code, to make it faster.

  1. Time limit is 5secs
  2. Given N numbers N<=10^5
Sample Input : 5 2 
               1 5 3 4 2
Sample Output: 3

First I've tried using ArrayLists, later tried using arrays. Code written is bad and not at all followed normal conventions of java, but I'm not looking at that, because execution time doesn't depend on it, right? But to achieve the puzzle description I couldn't see any better logic than this.

share|improve this question
What is N and K in your sample? – Michael K Dec 30 '11 at 17:09
First two nums - 5(N) 2(K) – cypronmaya Dec 30 '11 at 17:15

2 Answers

up vote 2 down vote

Some things which just jump into my eyes (even if not asked, I'll tell you anyway):

  • Whitespaces: Use whitespaces were appropriate, f.e. for(int i=0;i<nums;i++) is harder to rad then for(int i = 0; i < nums; i++).
  • Meaningful names: Name your variables after what they are, not what type they are. This especially includes simple for loops. It might be taught or standard to use i, but I consider it bad practice because you never know what exactly i is at first glance. Give your variables meaningful names, please, they deserve love too! Same goes for your classes.
  • Split up where appropriate: if you've got only one function (main) you're most likely doing something wrong. Split it into Input, Processing and Output.
share|improve this answer
up vote 1 down vote accepted

Other than comparing the numbers as they are given (in order) sorting them and comparing would take less cycles and runs much faster.

So the above code can be optimized to this

Arrays.sort(ary_nums);

for (int i = total_nums - 1; i > 0; i--) {
    for (int j = i - 1; j >= 0; j--) {
        if (ary_nums[i] - ary_nums[j] == diff) {
            count++;
            j = 0;
        }
    }
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.