Skip to main content
added 47 characters in body
Source Link
alexpfx
  • 524
  • 3
  • 15

Your optimized method alone took 12 seconds in the first iteration. Even if in the subsequent iterations it taken about 0 millisecons (and will not!)if the subsequent inputs are all covered by the numbers in map, it would only tie the game after about 6K iterations!

Your optimized method alone took 12 seconds in the first iteration. Even if in the subsequent iterations it taken about 0 millisecons (and will not!), it would only tie the game after about 6K iterations!

Your optimized method alone took 12 seconds in the first iteration. Even if in the subsequent iterations it taken about 0 millisecons if the subsequent inputs are all covered by the numbers in map, it would only tie the game after about 6K iterations!

Source Link
alexpfx
  • 524
  • 3
  • 15

I did a little modification in the class DivisorPrint and in the class Solution if you run both again you will understand why the first is slower.

I change the scanner instantiation to do the process automatically without the need to enter the numbers manually.

public static final Scanner sc = new Scanner(new ByteArrayInputStream("3\n50000000\n60000000\n70000000\n".getBytes()));

So it will run both the programs asking by 3 numbers, that will be: 50.000.000, 60.000.000, 70.000.000.

I put a time counter in your fillPrimes method to compare it with the time taken by the entire execution of Solution program.

If you run this version of DivisorPrint you will get something like:


DivisorPrint.java:

Time to fillPrimes (iteration 0): 13 seconds
63
Time to fillPrimes (iteration 1): 4 seconds
128
Time to fillPrimes (iteration 2): 4 seconds
112

Solution.java:

63
128
112
time to run the entire program: 2 milliseconds

So... the Solution.java algorithm solve the problem in about 2 milliseconds.

Your optimized method alone took 12 seconds in the first iteration. Even if in the subsequent iterations it taken about 0 millisecons (and will not!), it would only tie the game after about 6K iterations!

The problem is what this type of optimization don't work very well in this context: in the Solution.java code the programmer has used only primitive types and keep the calculation very simple. That map and lists you've used and the related operations, all the autoboxing and unboxing needed, are to much expensive compared to the use of the purest java.


The test codes:

import java.io.ByteArrayInputStream;
import java.sql.Time;
import java.util.*;
import java.util.concurrent.TimeUnit;

public class DivisorPrint {

//    public static final Scanner sc = new Scanner(System.in);
    public static final Scanner sc = new Scanner(new ByteArrayInputStream("3\n50000000\n60000000\n70000000\n".getBytes()));
    public static List<Integer> primes = new ArrayList<>();
    public static Map<Integer, Integer> factorsOccur = new HashMap<>();
    public static List<Integer> factors = new ArrayList<>();

    public static void main(String... arrgs) {

        int t = sc.nextInt(), i;

        for (i = 0; i < t; i++) {
            int n = sc.nextInt(), temp;
            int k = 0, l = 0;

            long beforeFillPrimes = System.currentTimeMillis();
            fillPrimes(n);
            System.out.println(String.format("Time to fillPrimes (iteration %d): %d seconds", i, TimeUnit.MILLISECONDS.toSeconds(System.currentTimeMillis() - beforeFillPrimes)));

            int curr = primes.get(k);

            if (n % 2 != 0) {
                System.out.println(0);
            } else {
                // checking if curr is  factor
                while (curr <= n) {
                    temp = n;
                    while (temp != 0) {
                        if (temp % curr == 0) {
                            l++;
                            temp /= curr;
                        } else
                            break;
                    }

                    if (l != 0) {
                        factorsOccur.put(curr, l);
                        factors.add(curr);
                    }

                    k++;
                    l = 0;

                    if (k >= primes.size())
                        break;
                    else
                        curr = primes.get(k);
                }

                // now we have the list of primes
                Collections.sort(factors);

                if (n == 2) {
                    System.out.println(1);
                } else {
                    int occurTwo = factorsOccur.get(factors.get(0));
                    int total = 0;

                    if (factors.size() == 1) {
                        total = occurTwo;
                    } else {
                        total = 1;
                        for (int r = 1; r < factors.size(); r++) {
                            total *= (factorsOccur.get(factors.get(r)) + 1);
                        }

                        total *= occurTwo;
                    }

                    System.out.println(total);

                }

            }
            factorsOccur.clear();
            factors.clear();
        }
    }


    public static void fillPrimes(int n) {
        int f = primes.size();
        if (f == 0) {
            // there are no primes
            primes.add(2);
            f++;
        }

        // get all prime numbers up to the value of n
        if (primes.get(f - 1) <= n) {

            int check = 0;
            if (primes.get(f - 1) == 2) {
                check = 3;
            } else {
                check = primes.get(f - 1) + 2;
            }
            boolean isPrime = true;
            while (check <= n) {
                for (int i = 0; primes.get(i) * primes.get(i) <= check; i++) {
                    if (check % primes.get(i) == 0) {
                        isPrime = false;
                        break;
                    }
                }

                if (isPrime)
                    primes.add(check);

                isPrime = true;
                check += 2;
            }
        }

    }
}

import java.io.ByteArrayInputStream;
import java.util.Scanner;

public class Solution {

//    public static final Scanner sc = new Scanner(System.in);
    public static final Scanner sc = new Scanner(new ByteArrayInputStream("3\n50000000\n60000000\n70000000\n".getBytes()));

    public static void main(String... arrgs) {
        int t = sc.nextInt(), n, total, opp;
        long before = System.currentTimeMillis();


        for (int i = 0; i < t; i++) {
            n = sc.nextInt();


            total = 0;

            if (n % 2 != 0)
                System.out.println(0);
            else {

                for (int j = 2; j * j <= n; j++) {

                    if (j * j == n) {
                        total++;
                    } else {
                        if (n % j == 0) {
                            if (j % 2 == 0)
                                total++;

                            opp = n / j;
                            if (n % opp == 0 && opp % 2 == 0) {
                                total++;
                            }
                        }
                    }
                }
                total++;
                System.out.println(total);
            }

        }

        System.out.println(String.format("time to run the entire program: %d milliseconds", (System.currentTimeMillis() - before)));
    }

}