Finding n and n^2 in a collection of digits

Question

I need to find the biggest $n$ and $n^2$ given a collection of digits. I need to use every digit.

For example the biggest $n$ in the collection

{ 1, 0, 0, 1, 0, 0 }

is $10$, because $10^2 = 100 = 00100$ (leading zeroes are allowed). How can I do this efficiently?

The length of the collection is always divisible by 3.

Additional examples:

{ 4, 2, 0 } => 2^2 = 04
{ 5, 2, 6, 1, 4, 3, 7, 8, 9 } => 567^2 = 321489

What do you mean with "efficiently"? In a programming language or what? Send a larger string — Raffaele, Nov 05 '17 at 13:16
@Raffaele I'll ultimately have to do it programatically, but simply brute-forcing the solution is too slow. — Bálint, Nov 05 '17 at 13:18
@Hagen I need to use every digit (added to the question), and leading zeroes are allowed — Bálint, Nov 05 '17 at 13:22
IMHO there is no way to avoid the brute force. In the last string there are also $7^2=49,;961=31^2,;25=5^2,;36=6^2$ but who knows how many squares are there in the $9!$ "anagrams" of the string? or in the other many many substrings? — Raffaele, Nov 05 '17 at 13:34

score 1 · Answer 1 · answered Nov 05 '17 at 13:50

We can make some beforehand observations: We know the digit sum, i.e., the remainder modulo $9$ of $n$ and $n^2$ togerther, i.e., we know $n\cdot(n+1)\bmod 9$. Then $n\bmod 9$ can only have two possible values. But as a feasible general approach, I would take backtracking while building $n$ from the least to most significant digit. The following works, provided $n$ and $n^2$ fit into your int type.

int stock[10]; // contains the number of occurences of digits

void backtrack(int digits,int n,int power,bool final) {
  if (digits==0) {
    Found a solution n;
    return;
  }
  if (!final) for (int d=0; d<10; d++) if (stock[d]>0) {
    --stock[d];
    n += d*power;
    int dd = ((n*n)/power) % 10;
    if (stock[dd]>0) {
      --stock[dd];
      backtrack(digits-2,n,10*power,final);
      ++stock[dd];
    }
    n -= d*power;
    ++stock[d];
  }
  int dd = ((n*n)/power) % 10;
  if (stock[dd]>0) {
    --stock[dd];
    backtrack(digits-1,n,10*power,true);
    ++stock[dd];
  }
}

main() {
  int digits = 0;
  for (i=0; i<10; i++) stock[i]=0;
  for each digit d in the input {
    ++stock[d];
    ++digits;
  }
  backtrack(digits,0,1,false);
}

Finding n and n^2 in a collection of digits

1 Answers1