Number Formation

An answer to this question on Stack Overflow.

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

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