0

我一直在尝试为与此处相同的问题找到正确的解决方案， 但在 Java 中，并且由于应该返回计数而稍作修改。

我想出了以下解决方案：

public static int count(int n) {
    // check for 0 or smaller
    if (n <= 0) {
        return -1;
    }

    // find root of N
    int root = (int) Math.ceil(Math.sqrt(n));
    int count = 0;
    for (int i = 1; i < root; i++) {
        if (n % i == 0) {
            // calculate bit_rev(i)
            int reverse = bit_rev(i);

            // calculate bit_rev(N/i)
            int reverseDiv = bit_rev((int)Math.floor(n/i));

            // check whether i * bit_rev(i) == N or i == bit_rev(N/i)
            if (reverse*i == n
                    || i == reverseDiv) {
                System.out.println(String.format("Found reverse (N = %d, i = %d, bit_rev(i) = %d, bit_rev(i) * i = %d, bit_rev(N/i) = %d)", n, i, reverse, reverse*i, reverseDiv));
                count++;
            } else {
                System.out.println(String.format("N = %d mod i = %d == 0, but no match (bit_rev(i) = %d, bit_rev(i) * i = %d, bit_rev(N/i) = %d)", n, i, reverse, reverse*i, reverseDiv));
            }
        }
    }


    if (count == 0) {
        // didn't match -> return -1
        return -1;
    } else {
        // return whatever the count was
        return count;
    }
}

public static int bit_rev(int n) {
    String string = Integer.toBinaryString(n);
    String reverseString = new StringBuffer(string).reverse().toString();
    int reverse = Integer.parseInt(reverseString, 2);
    return reverse;
}

在参考样本中，N = 3245 的解应该是 count = 55。

但是，我的解决方案发现count = 1 (i = 55, bit_rev(i) = 59).

其他参考样品是：

-) N = 50 -> count = 1
-) N = 286 -> count = 2

我知道找到 bit_rev() 的解决方案不是最好的（最有效的），但我不认为这是错误的，是吗？

这里是否还有其他错误，或者 N = 3245 的参考样本是否错误？

4

1 回答 1

1

我认为你误读了这个问题，或者参考答案是错误的。如果它与http://algorithmsforever.blogspot.com/2011/12/integer-binary-roots.html?m=1上的问题类似，那么您需要返回最小的二进制根，而不是二进制根的数量。

无论如何，我认为您的实施正在正确地解决它们。55 确实是 3245 的最小二进制根（不是根数）。

于 2012-08-22T06:23:23.817 回答