时间戳

首页 > 解决方案 > 找到“平衡数”的算法 - 相同数量的偶数和奇数除法器

java - 找到“平衡数”的算法 - 相同数量的偶数和奇数除法器

问题描述

我们将平衡数定义为具有相同数量的偶数和奇数除法器的数，例如（2 和 6 是平衡数）。我试图为波兰 SPOJ 做任务，但我总是超过时间。任务是找到大于输入给定的最小余额数。有示例输入：

2 (amount of data set)
1
2

输出应该是：

2
6

这是我的代码：

import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
    private static final BigDecimal TWO = new BigDecimal("2");

    public static void main(String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);
        int numberOfAttempts = in.nextInt();
        for (int i = 0; i < numberOfAttempts; i++) {
            BigDecimal fromNumber = in.nextBigDecimal();
            findBalancedNumber(fromNumber);
        }
    }

    private static boolean isEven(BigDecimal number){
        if(number.remainder(new BigDecimal("2")).compareTo(BigDecimal.ZERO) != 0){
            return false;
        }
        return true;
    }

    private static void findBalancedNumber(BigDecimal fromNumber) {
        BigDecimal potentialBalancedNumber = fromNumber.add(BigDecimal.ONE);
        while (true) {
            int evenDivider = 0;
            int oddDivider = 1; //to not start from 1 as divisor, it's always odd and divide potentialBalancedNumber so can start checking divisors from 2
            if (isEven(potentialBalancedNumber)) {
                evenDivider = 1;
            } else {
                oddDivider++;
            }
            for (BigDecimal divider = TWO; (divider.compareTo(potentialBalancedNumber.divide(TWO)) == -1 || divider.compareTo(potentialBalancedNumber.divide(TWO)) == 0); divider = divider.add(BigDecimal.ONE)) {
                boolean isDivisor = potentialBalancedNumber.remainder(divider).compareTo(BigDecimal.ZERO) == 0;
                if(isDivisor){
                    boolean isEven = divider.remainder(new BigDecimal("2")).compareTo(BigDecimal.ZERO) == 0;
                    boolean isOdd = divider.remainder(new BigDecimal("2")).compareTo(BigDecimal.ZERO) != 0;
                    if (isDivisor && isEven) {
                        evenDivider++;
                    } else if (isDivisor && isOdd) {
                        oddDivider++;
                    }
                }
            }
            if (oddDivider == evenDivider) { //found balanced number
                System.out.println(potentialBalancedNumber);
                break;
            }
            potentialBalancedNumber = potentialBalancedNumber.add(BigDecimal.ONE);
        }
    }
}

它似乎工作正常，但太慢了。你能帮忙找到优化它的方法吗，我错过了什么吗？

标签： javaalgorithmmathoptimizationrefactoring

解决方案

正如@MarkDickinson 建议的那样，答案是：

private static void findBalancedNumberOptimized(BigDecimal fromNumber) { //2,6,10,14,18,22,26...
        if(fromNumber.compareTo(BigDecimal.ONE) == 0){
            System.out.println(2);
        }
        else {
            BigDecimal result = fromNumber.divide(new BigDecimal("4")).setScale(0, RoundingMode.HALF_UP).add(BigDecimal.ONE);
            result = (TWO.multiply(result).subtract(BigDecimal.ONE)).multiply(TWO); //2(2n-1)
            System.out.println(result);
        }
    }

最后是绿色的，谢谢马克！

推荐阅读