CODEWITHSUNDEEP
javaalgorithmperformanceperfect-numbers
Valakor
Valakor

Reputation: 3

Perfect Number Performance

I have a solution for the Kattis Problem https://open.kattis.com/problems/almostperfect. The solution is accepted, but the runtime is too long (>1.00s). I tried everything to solve this issue. What can I do to further improve the performance of my code?

import java.io.FileInputStream;
import java.util.Scanner;

import java.io.*;
import java.util.*;

public class almostperfect {

public static int perfect(int number){
    // 2 = perfect
    // 1 = almost perfect
    // 0 = not perfect
    int sum = 0;
    int b = 0;
    for(int i=1;i<number;i++)
    {
        if(number%i==0)
        {
            sum = sum + i;
        }
    }
    if(sum == number){
        b = 2;
    } else if(Math.abs(sum-number)<=2){
        b = 1;
    }

    return b;

}


public static void main(String[] args) 
{
    Scanner scan = new Scanner(System.in);
    ArrayList<Integer> input = new ArrayList<Integer>();
    int a;
    int status;
    while(scan.hasNextLong()){
        input.add((int) scan.nextLong());
    }
    for(int i=0; i<input.size(); i++){
    a = input.get(i);
    status = perfect(a);
    if(status==2){
        System.out.println(a+" perfect");
    } else if (status==1){
        System.out.println(a+" almost perfect");
    } else {
        System.out.println(a+" not perfect");
        }
    }

}}

Upvotes: 0

Views: 601

Answers (2)

Durandal
Durandal

Reputation: 20069

Your code is fine, what is not fine is the method of finding the factors for the number it implements. You need to be smarter than brute force checking every possible number smaller than number if it is a factor.

First, obviously 1 is always a factor, since any number divides by 1 without a remainder. Also, by definition the number itself is not a factor. This restricts factors to be found to the range (2 ... n-1).

Second, if you find a divisor, then the dividend is also a divisor:

dividend = number / divisor -> implies: dividend is also a divisor

This means divisors are always found in pairs (dividend is also a divisor, making the pair). The one exception that must be accounted for is that dividend may be the same as dividend (e.g. number = 9, divisor = 3 -> dividend = 3). This can be exploited, leading to:

Third, when starting testing from the smallest possible divisor (2), the first dividend you find is the largest divisor possible, with dividends decreasing steadily while you increase the tested divisor. This means there is no need to explicitly check for divisors that are found as dividend. That means the upper testing limit would be where divisor and dividend become equal, in other words the root of number.

As stated for the problem in the link, numbers may be in range 1 ... 1E9. Your brute force method needs 1 billion tests for 1E9, while the smart version exploiting above properties, only needs 31621. Thats about factor 30000 faster!

Upvotes: 1

TDG
TDG

Reputation: 6161

When you calculate the divisors of number, you don't have to loop from 1 to number, but to the square root of number. Take 100 for example - if 2 is a dividor of 100, so is 100/2. 

int sum = 1;   //1 is always a divisor
int b = 0;
int sqr = (int)Math.sqrt(number);
for(int i=2;i< sqr;i++)
{
    if(number%i==0)
    {
        sum = sum + i;
        sum = sum + number/i;
    }
}
//Check what happens for sqr - if it's a divisor, add it only once
if (sqr * sqr == number)
    sum += sqr;

Upvotes: 2

Related Questions