HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaMinor

Project Euler 40: directly calculate digits of Champernowne's constant

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
constantdigitsprojectchampernownecalculatedirectlyeuler

Problem

I implemented Project Euler problem 40 in Java. It works correctly, producing the correct answer.

During the course of implementing this program, I wrote a method that directly calculates a digit of Champernowne's constant, as opposed to the obvious brute-force approach. While brute-force is fast, this method takes under 1ms. In terms of speed, this is good code.

However, the method has a lot of repetition that I would like to get rid of, but I am not sure how. This may be a case of different code structures having similar attributes (those inner if blocks) that are not able to be combined, or any such optimization would introduce so many other complexities that it makes the code less clear.

Notes:

-
This method is long, too long. If there is no way to simplify this, I will split it into multiple methods on the top-level if statements. I have it all in one method in the meantime while looking for a way to refactor the code to be more concise.

-
I could refactor it to have multiple return statements, and I know that everyone has their own preference on this. I implemented it this way (final return variable and exceptions) to fail fast. It cannot compile if I forget a code path, and the exceptions kill the program in case of a logic error.

-
This is written in Java 8, so pretty much any language feature is fair game (e.g. lambdas).

The code:

```
private static int getDigit(int d) {
/* This algorithm does the following:
*
* 1. Based on the requested digit, find which group of digits it belongs
* to. A digit group is determined by how many digits each number has: for
* example, all two-digit numbers are part of the two-digit group.
*
* 2. Find the number that contains the requested digit. This can be easily
* calculated because the size of each group is well-defined, and since all
* numbers in the group have the same number of digits, we can easily
* calculate which number contains the requested digit.

Solution

The boundaries of where the number of digits increases can be generated and looped over:

int n=0, nDigits;
for(nDigits=1; n < d; nDigits++){
    n+= nDigits*(pow10(nDigits)-pow10(nDigits-1));
}


pow10(n) is a helper function to create the nth power of 10.

The big if-else can also be simplified and generalized a bit:

if (digit == 0) {
    number--;
    digit = nDigits;
  }

  result = ((number + 1) / pow10(nDigits-digit)) % 10;

Code Snippets

int n=0, nDigits;
for(nDigits=1; n < d; nDigits++){
    n+= nDigits*(pow10(nDigits)-pow10(nDigits-1));
}
if (digit == 0) {
    number--;
    digit = nDigits;
  }

  result = ((number + 1) / pow10(nDigits-digit)) % 10;

Context

StackExchange Code Review Q#107104, answer score: 4

Revisions (0)

No revisions yet.