current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 4 down vote favorite
2

Puzzle Description

Given \$N\$ numbers, \$N <= 10^5\$, count the total pairs of numbers \$(N_i, N_j)\$ that have a difference of \$K = N_i - N_j\$ where \$0 < K < 10^9\$.

Input Format:

  • 1st line contains \$N\$ and \$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 number of pairs of numbers that have a difference \$K\$.

Time limit is 5 seconds.

Sample Input : 5 2 
               1 5 3 4 2
Sample Output: 3

First I've tried using ArrayLists and later tried using arrays. The code is bad and does not at all follow 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:

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());
    }
}
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 2

up vote 4 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 4 down vote accepted

Other than comparing the numbers as they are given (in order), sorting them and comparing would take fewer cycles and run 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.