Find all the numbers within a range whose digits add up to a certain target

Question

In an interview I was asked the following problem:

Given a range of numbers (0 - 100) or (0 - 1000), find all the numbers whose digit add up to 5.

I started off with a brute force way to iterate over all the numbers and filter out numbers whose digits do not add up to 5. The numbers remaining will be the answer.

It seems like that wasn't the desired solution. After thinking about the problem a little bit I realized another approach would be to use recursion to generate all the numbers until a particular "digit-size".

For example, if we are asked to generate all the numbers that between 0 and 100 that add up to 5, we can generate all numbers from 'digit-size=1' to 'digit-size=3' that add up to 5.

It will be great if this approach could be reviewed.

    public class FindAllNumbersWithCertainDigitSum {
       public List<Integer> getAllNumbersThatSumToTarget(int digitSize, int target) {
          List<Integer> candidates = new ArrayList<>();
          int accumulatedSum = 0;
          helper(digitSize, target, candidates, accumulatedSum);
          return candidates; 
     }

     private void helper(int digitSize, int target, List<Integer> candidates, int accumulatedSum) {
         //Base case: No more digits to consider and nothing else to add
         if(digitSize == 0 && target == 0) {
             candidates.add(accumulatedSum);
         } 
       //There is nothing else to add but there are more digits to consider that will be multiples of 10
       else if(digitSize != 0 && target == 0) {
             helper(digitSize - 1, target, candidates, accumulatedSum * 10);
         } 
      //The digits did not add up to the target, return without doing anything 
      else if(digitSize == 0 && target != 0) {
             return;
         } else {
            //Iterate from target down to zero and recursively get the remaining digits if the first digit is the target.
             for(int current = target; current >= 0; current--) {
                 helper(digitSize - 1, target - current, candidates, accumulatedSum*10 + current);
             }
         }

      }

     public static void main(String[] args) {
        FindAllNumbersWithCertainDigitSum s = new FindAllNumbersWithCertainDigitSum();
        //Get all numbers from 0 - 999(maxDigitSize == 3) that add up to 5
        s.getAllNumbersThatSumToTarget(3, 5)
         .stream()
         .forEach(System.out::println);
      } 
}

Answer 1

I started off with a brute force way to iterate over all the numbers and filter out numbers whose digits do not add up to 5. The numbers remaining will be the answer. It seems like that wasn't the desired solution.

These questions try to test how you translate problem information into your solution. Brute force, while sometimes the practical answer, is rarely a good interview answer.

The recursive approach is a good way to go about it: the solution is simple and efficient in terms of operations performed.

As an interviewer, I would be content with the code given. I would, however, ask about two things, just to probe:

• What would you need to change to handle the target sum-of-digits being 10 or greater?
• Can you think of an approach that does not require storing all numbers? (think callbacks)

About the code: helper is perhaps more involved than it needs to be. We can merge some conditions:

private void helper(int digitSize, int target, List<Integer> candidates, int accumulatedSum) {
    if ( digitSize == 0 && target == 0 ) {
        // >>> [B] We can merge this ...
        candidates.add(accumulatedSum);
    }
    else if ( digitSize != 0 && target == 0 ) {
        // >>> [A] Don't need this ...
        helper(digitSize - 1, target, candidates, accumulatedSum * 10);
    } 
    else if ( digitSize == 0 && target != 0 ) {
        // <<< [B] ... with this.
        return;
    } else {
        // <<< [A] ... because covered by this (target == 0).
        for ( int current = target; current >= 0; current-- ) {
            helper(digitSize - 1, target - current, candidates, accumulatedSum*10 + current);
        }
    }
}

... leading to (for example) :

private void helper(int digitSize, int target, List<Integer> candidates, int accumulatedSum) {
    if ( target == 0 ) {
        accumulatedSum *= Math.pow(10, digitSize);
        candidates.add(accumulatedSum);
    } else if ( digitSize != 0 ) {
        for ( int current = target; current >= 0; current-- ) {
            helper(digitSize - 1, target - current, candidates, accumulatedSum*10 + current);
        }
    }
}

---

Would it be possible for you to elaborate on the approach of using callbacks to sidestep storing all the numbers and handle sum of digits greater than 10?

Handling 10 or more is a matter of limiting your recursive steps:

private void helper(int digitSize, int target, List<Integer> candidates, int accumulatedSum) {
    if ( target == 0 ) {
        accumulatedSum *= Math.pow(10, digitSize);
        candidates.add(accumulatedSum);
    } else if ( digitSize != 0 ) {
        for ( int current = Math.min(9, target); current >= 0; current-- ) { // <<< add Math.min(9, -)
            helper(digitSize - 1, target - current, candidates, accumulatedSum*10 + current);
        }
    }
}

As for callbacks: the only method you're using on your output list is List.add, which we can pull out as a method handle.

private void helper(int digitSize, int target, IntConsumer candidateSink, int accumulatedSum) {
    if ( target == 0 ) {
        accumulatedSum *= Math.pow(10, digitSize);
        candidateSink.accept(accumulatedSum); // <<< becomes .accept
    } else if ( digitSize != 0 ) {
        for ( int current = Math.min(9, target); current >= 0; current-- ) {
            helper(digitSize - 1, target - current, candidateSink, accumulatedSum*10 + current);
        }
    }
}

Now we can call your method with List::add for the previous behavior, or we can do our own things with it:

List<Integer> candidates = new ArrayList<>();
getAllNumbersThatSumToTarget(5, 3, candidates::add); // previous behavior
getAllNumbersThatSumToTarget(8, 15, System.out::println); // no need to store, so no memory issues

Answer 2

Just a idea...

There are 7 sets of digits that can constuct numbers that add up to 5.

a = [1, 1, 1, 1, 1]
b = [2, 1, 1, 1]
c = [2, 2, 1]
d = [3, 1, 1]
e = [3, 2]
f = [4, 1]
g = [5]

Then: let r be the sets in (a...g) that has size < log(max)

Pad each set in r with zeroes so that all set sizes are log(max)

The answer is permutations of the sets that are in the range min - max.

Answer 3

Just a thought but this might just work fine. Select the minimum number from the range that satisfies the condition. Now start adding 9. You can notice that the sum of digits is maintained no matter how far you go.

Now other question rises is whether its just one time sum or repetitive sum until its a single digit. i.e 59 -- 5+9 =14 -- 1+4 =5 or just 59 -- 5+9 =14

If its the first case there is no need to be any more cautious, the trick will do the work. Now if its the second case we can just add a constraint saying don't print if sumofdigits>10.