2
\$\begingroup\$

Given a natural number \$n\$ (\$1 \le n \le 500000\$), please output the summation of all its proper divisors.

Definition: A proper divisor of a natural number is the divisor that is strictly less than the number.

e.g. number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

Input

An integer stating the number of test cases (equal to about 200000), and that many lines follow, each containing one integer between 1 and 500000 inclusive.

Output

One integer each line: the divisor summation of the integer given respectively.

My solution:

It solved the problem in 1.63 seconds, which seems suboptimal considering its 3-second limit.

import java.util.ArrayList;
import java.util.Scanner;

public class Main
{
    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        int testcases = reader.nextInt();
        reader.nextLine();
        ArrayList<Integer> values = new ArrayList<Integer>();
        for(int i = 0; i<testcases; i++){
            values.add(reader.nextInt());
            reader.nextLine();
        }
        reader.close();
        for(int i = 0; i<testcases; i++){
            int sum = 1;
            int testcase = values.get(i);
            double lim = Math.sqrt(testcase);
            for(int k = 2; k<=lim; k++){
                if(testcase%k==0){
                    sum+=k;
                    int z = testcase/k;
                    if(k != z)
                        sum+=z;
                }
            }
            if(testcase==1)
                sum=0;
            if(i<testcases-1)
                System.out.println(sum);
            else
                System.out.print(sum);
        }
    }
}

EDIT: Updated code, which ran in a more respectable 0.22 seconds.

Taking out reader.nextLine(); improved the runtime by around 0.2 seconds.

Adding a special treatment to perfect squares seemed to have no noticable impact on speed (might depend on test cases?).

It turned out using BufferedReader and BufferedWriter had an immense impact on IO speed, reducing runtime to 0.22 seconds.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main
{
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
        int testcases = Integer.parseInt(in.readLine());
        int[] values = new int[testcases];
        for(int i = 0; i<testcases; i++){
            values[i]=Integer.parseInt(in.readLine());
            }
        for(int i = 0; i<testcases; i++){
            int sum = 1;
            int testcase = values[i];
            double lim = Math.sqrt(testcase);
            for(int k = 2; k<lim; k++){
                if(testcase % k == 0){
                    sum += k + testcase / k;
                }
            }
            int intLim = (int) lim;
            if (intLim * intLim == testcase) {
                sum += lim;
            }
            if(testcase == 1)
                sum=0;
            out.write(sum + "\n");
        }
        out.flush();
    }
}
\$\endgroup\$
  • \$\begingroup\$ I tested this locally, and most of the time is due to IO: running in Eclipse with 200.000 random numbers (producing 6.2MB output) it takes 4.7 seconds, on the commandline 2.9 seconds, and on the commandline redirecting stdout to a file it takes 1 second. Without printing any output the algorithm takes 120ms. \$\endgroup\$ – Kenney Oct 31 '15 at 20:16
  • \$\begingroup\$ @Kenney Interesting. How could I decrease IO time? \$\endgroup\$ – user3050748 Oct 31 '15 at 22:01
  • \$\begingroup\$ I tried buffering all output and do a System.out.write but that doesn't speed things up. The only way that I know is to output to a file instead of stdout, as this bypasses the OS rendering terminals and such. Btw, your algorithm will miss some output: for example sqrt(20) is about 4.47 so you will miss divisors 5 and 10. \$\endgroup\$ – Kenney Oct 31 '15 at 22:08
  • \$\begingroup\$ This may not have a big impact, but Scanner is a beast, performance-wise. Use a BufferedReader and Integer.parseInt(). --- Also, you are wasting time building an ArrayList<Integer>, boxing all the values and building up the list. Just perform your logic as you read the values. --- You should move the inside of the for loop to a method that returns the sum, and print in the caller. This will allow adding unit tests to your code, and isolates the logic from the I/O, for a better structured program. \$\endgroup\$ – Andreas Nov 1 '15 at 3:33
  • \$\begingroup\$ @Andreas using BufferedReader and BufferedWriter indeed had quite a big impact on IO speed. The code ran in 0.22 seconds. I also used an integer array instead of an ArrayList. \$\endgroup\$ – user3050748 Nov 1 '15 at 13:55
2
\$\begingroup\$

In the innermost for loop, you have a condition to check in every cycle if k is the square root. But most of the time it's not equal to the square root. It would be more optimal to rework that, and add a special treatment for square numbers once, after the loop:

for (int k = 2; k < lim; k++) {
    if (testcase % k == 0) {
        sum += k + testcase / k;
    }
}
int intLim = (int) lim;
if (intLim * intLim == testcase) {
    sum += lim;
}

You don't need the reader.nextLine() calls in this code, you can safely remove them. You can also remove the reader.close(), no need to close System.in.

int testcases = reader.nextInt();
//reader.nextLine();
List<Integer> values = new ArrayList<>();
for (int i = 0; i < testcases; i++) {
    values.add(reader.nextInt());
    //reader.nextLine();
}
//reader.close();

Is it really important to not print a newline at the end? If it's not important, then you can rewrite the loop as a for-each loop:

for (int testcase : values) {
    // ...
    System.out.println(sum);
}

Minor things:

  • It's better to declare variables with interface types when possible, so instead of ArrayList<Integer> values = ..., use List<Integer> values = ...
  • As of Java 7, use the diamond operator <> when creating parameterized types, for example List<Integer> values = new ArrayList<>()
  • Always use braces even with single-statement if/else/for
  • Put spaces around operators and parentheses, for example instead of if(testcase%k==0){ write as if (testcase % k == 0) {
\$\endgroup\$
0
\$\begingroup\$
        for(int i = 0; i<testcases; i++){
            int sum = 1;
            int testcase = values.get(i);

You never use i outside these three lines, so you could just as well write

        for (int testcase : values) {
            int sum = 1;

I would consider either renaming testcase to value, or renaming testcases to testcaseCount and values to testcases. I would prefer the latter, mostly because I prefer plural variable names to refer to collections.

Before that, you might want to add

        int lastValue = values.remove(values.size() - 1);

Then you can replace

            if(i<testcases-1)
                System.out.println(sum);
            else
                System.out.print(sum);

with just

            System.out.println(sum);

and handle the last value separately.

\$\endgroup\$

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.