Number Formation

Question

Given three integers x,y and z you need to find the sum of all the numbers formed by having 4 atmost x times , having 5 atmost y times and having 6 atmost z times as a digit.

NOTE: The numbers can contain only 4,5,6 as digits.

EG: 1 1 1

Output: 3675

Explanation: The ans for the input is 4+5+6+45+54+56+65+46+64+456+465+546+564+645+654=3675

I tried coming up with a DP approach similar to what we do in finding ugly numbers. But no hope?

How to solve this problem?

I think this is a super hard problem. Is it?

Answer 1

I recently posted an answer to a (somewhat) related question. With this approach the idea is, for every possible combination of sizes, you find all the possible partitions of the digit positions with those sizes:

from itertools import product

def partitions(*sizes):
    if not sizes or all(s <= 0 for s in sizes):
        yield ()
    for i_size, size in enumerate(sizes):
        if size <= 0:
            continue
        next_sizes = sizes[:i_size] + (sizes[i_size] - 1,) + sizes[i_size + 1:]
        for p in partitions(*next_sizes):
            yield (i_size,) + p

def sum_numbers(*numbers):
    values, sizes = zip(*numbers)
    total = 0
    for p in product(*map(lambda s: range(s + 1), sizes)):
        for q in partitions(*p):
            total += sum(values[idx] * (10 ** pos) for pos, idx in enumerate(q))
    return total

Example:

sum_numbers((4, 1), (5, 1), (6, 1))
>>> 3675

Explanation:

partitions is a function that returns something like "permutations without repetitions". For example, partitions(2, 3, 1) will return all possible tuples containing 2 zeros, 3 ones and 1 two (e.g. (0, 1, 0, 0, 1, 2, 1)). It does it by creating partial tuples with each possible element, decreasing the count of that element and making a recursive call. The elements of these tuples represent here your numbers (4, 5 and 6).

sum_numbers uses partitions to compute the result. If you can have 4 up to x times, 5 up to y times and 6 up to z times, it first considers all the possible combinations of sizes. For example, having zero of each, having zero 4 and 5 and one 6, etc. up to having x 4, y 5 and z 6. For each of these, it computes all the possible partitions and it uses the values in the aforementioned tuples to compute each partial result.

Answer 2

There is a simple two-part solution to this problem.

You need:

1. An algorithm for finding all distinct orderings of an array.
2. An algorithm which creates arrays in which the digits of interest are included varying numbers of times.

For (1) you can use std::next_permutation() along with unordered_set.

For (2) you could build a recursive function which constructs the array.

The following program accomplishes this:

#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

//Convert an array of digits into an integer
int VecToNumber(const std::vector<int> &to_permute){
  int num   = 0;
  int tens  = 1;
  for(int i = to_permute.size()-1;i>=0;i--,tens*=10)
    num+=to_permute[i]*tens;
  return num;
}

void Permuter(std::vector<int> to_permute, std::vector<int> &numbers_to_add){
  //Sorting is a necessary step before we can use `std::next_permutation`
  std::sort(to_permute.begin(),to_permute.end());
  //Loop through every permutation of `to_permute`
  do {
    numbers_to_add.push_back(VecToNumber(to_permute));
  } while(std::next_permutation(to_permute.begin(), to_permute.end()));
}

//Build an array to permute
void Builder(
  const std::vector<int> &values,   //Digits to use
  const std::vector<int> &counts,   //Maximum times to use each digit
  std::vector<int> &to_permute,     //Current array
  std::vector<int> &numbers_to_add, //Numbers we will be adding
  int pos                           //Digit we are currently considering
){
  //Since to_permute is used at each level of recursion, we must preserve it
  //at each level so we can reverse the effects of deeper levels of
  //recursion when moving back to shallower levels.
  const auto original_tp = to_permute;

  if(pos<values.size()){
    //Add more and more copies of a digit to the `to_permute` array, up to
    //the value specified by `counts[pos]`
    for(int i=0;i<counts[pos];i++){
      Builder(values,counts,to_permute,numbers_to_add,pos+1);
      to_permute.push_back(values[pos]);
    }
    Builder(values,counts,to_permute,numbers_to_add,pos+1);
  } else {
    //We've run out of digits to consider, now we will generate all of the
    //permutations of those digits
    Permuter(to_permute,numbers_to_add);
  }
  to_permute = original_tp;
}

int main(){
  std::vector<int> values = {{4,5,6}}; //Digits to use
  std::vector<int> counts = {{1,1,1}}; //Maximum number of times to use each digit

  std::vector<int> to_permute;     //Holds numbers we are currently permuting
  std::vector<int> numbers_to_add; //Holds numbers that we wish to add together

  //Collect all numbers we want to add together
  Builder(values,counts,to_permute,numbers_to_add,0);

  for(auto x: numbers_to_add)
    std::cout<<x<<std::endl;

  std::cout<<"Sum = "<<std::accumulate(numbers_to_add.begin(),numbers_to_add.end(),0)<<std::endl;
}

Output:

0
4
5
6
45
46
54
56
64
65
456
465
546
564
645
654
Sum = 3675