5
\$\begingroup\$

The questions from hackerearth:

Geeko is in worry now because an exam is coming up and he has to know what rank he can get on exams. So he goes back into the the school records and finds the amazing pattern.

He finds that if a student is having a current rank \$n\$, then his rank on the final exam will be the count positive numbers between in the range \$[1,n]\$ which are relatively prime to \$n\$.

As being a geek, he became curious now and wants to calculate the rank of all his classmates on the final exam. But he finds this task a bit hard, so he asks you programmers to solve this task for him.

Input: The first line of each test file contains a integer \$t\$ denoting the number of test case. Each test case contains a numbers \$n\$ representing the current rank of each student

Output: for each test case output single integer the rank of student in final exam in new line.

Constraints:

\$1 <= t <= 2000\$

\$1 <= n < 10^6\$

My solution:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

class relative {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        ArrayList<Integer> input = new ArrayList<Integer>();

        ArrayList<Integer> result = new ArrayList<Integer>();
        // int input[] = new int[t];
        // int result[] = new int[t];
        for (int i = 0; i < t; i++) {
            int count = 1;
            int in;
            input.add(in = Integer.parseInt(br.readLine()));
            for (int j = 2; j < in; j++) {
                if (in % j == 0)
                    continue;
                else if (checkRelativePrime(j, in))
                    count++;
            }
            result.add(count);
        }
        for (int i : result)
            System.out.println(i);
    }

    static boolean checkRelativePrime(int a, int b) {
        int i = 2;
        while (a > 1) {
            if (a % i == 0) {
                {
                    if (b % i == 0)
                        return false;
                }
                a = a / i;
            } else
                i++;
        }

        return true;
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome here! The indentation of your code seems a bit weird. It is because of the site or it is the way it appears in your favorite editor as well ? \$\endgroup\$ – SylvainD Jun 16 '14 at 17:05
  • \$\begingroup\$ does this code run? \$\endgroup\$ – Malachi Jun 16 '14 at 18:02
3
\$\begingroup\$

in your checkRelativePrime method you have

static boolean checkRelativePrime(int a, int b) {
    int i = 2;
    while (a > 1) {
        if (a % i == 0) {
            {
                if (b % i == 0)
                    return false;
            }
            a = a / i;
        } else
            i++;
    }

    return true;
}
  1. you have an extra set of brackets
  2. you have a statement in purgatory.

    a = a / i;
    

    it sits in-between the ending bracket of your if statement and the else statement that is supposed to be attached to the if statement

  3. if you use brackets for one part of an if statement, you should use them for the entire if statement. I recommend using brackets even for one-liners no matter what, it's cleaner and leaves less room for mistakes.


I think you wanted to keep that if statement separate from the declaration to the a variable, but you don't need to do that(especially if you are using brackets properly)

like this

while (a > 1) {
    if (a % i == 0) {
        if (b % i == 0) {
            return false;
        }
        a = a / i;
    } else {
        i++;
    }
}

if you enter that if statement and return false then a = a /i; will never happen and your boolean method will return false

\$\endgroup\$
2
\$\begingroup\$

Extract More Methods

Right now you have a lot of code in the main method. Ideally, you want to split up your code and have many methods each only doing one thing.

Naming Conventions

Class names should always start with a capital letter! (UpperCamelCase)

Pick more meaningful names. You're using a lot of one-character variable names, try not to do that. (It's okay for loop counters though).

Nested Assignments

You have the following:

input.add(in = Integer.parseInt(br.readLine()));

Don't use these nested assignments. "While admirably terse, such expressions may be confusing, and violate the general design principle that a given construct should do precisely one thing."

Braces

Always use braces for if-statements and loops. It just makes them that much more readable.

Unnecessary code

In your main method, you have an ArrayList named 'input' that is only written to, but never read from. In other words, you're not using it and you might as well omit it.

You import java.util.Scanner but it is never used. In the Netbeans IDE you can press ctrl-shift-i to automatically sort out imports. I'm sure other IDE's have similar features.

Misc

Don't use System.out.println() if you can avoid it.

Make variables final, unless you really need them not to be.

Code to interface. Save ArrayLists as Lists, for instance. Also, you may omit the diamond brackets as follows:

List<Integer> result = new ArrayList();

instead of:

ArrayList<Integer> result = new ArrayList<Integer>();
\$\endgroup\$
-2
\$\begingroup\$
  1. Give meaningful class names to your classes, e.g. "relative" does not seem to describe anything about the data type of the object. A more meaningful name could have been "RankFinder" in the context of your problem.
  2. Always stick to Hungarian notation while naming your classes and functions. http://en.wikipedia.org/wiki/Hungarian_notation
  3. The function checkRelativePrime seems wrong to me. Simply make use of an auxiliary function to compute gcd(a, b) and check if it's one. The gcd computation function is pretty standard and can works as follows.

    function gcd(a, b)
    while b ≠ 0
        t := b;
        b := a mod b;
        a := t;
    return a
    
  4. You don't really need the array result. You can simply print the numbers in the first for loop.
\$\endgroup\$
  • 4
    \$\begingroup\$ I am not really a fan of Hungarian notation, and not many around here are. \$\endgroup\$ – Malachi Jun 16 '14 at 17:52
  • 6
    \$\begingroup\$ Hungarian notation is only advisable in untyped or weakly typed languages. Java is not one of those. \$\endgroup\$ – RubberDuck Jun 16 '14 at 18:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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