# Program to calculate smallest number with permutations divisible by a set of numbers

(EDIT: here is the follow up question)

I have written a small program in C to calculate the smallest number where any of its permutations or the number itself is divisible by a set of given numbers. It works great when the number is only 4-5 digits but then it becomes very slow. Do you have any suggestions on optimizations when it comes to speed (or any optimization really)?

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

void swap(char *, char *);
int icontains(int *, int, int);
int contains(char **, int, char *);
void permute(char **, char *, int, int, int *);
unsigned int factorial(unsigned int);

int main() {
unsigned int i, j, k, l, m, n, len;
char num_ints[10];
char input[128];
char str[7];
char **family;
char **ints;
char *pch;
unsigned int *flags;
fgets(num_ints, 10, stdin);
fgets(input, 128, stdin);
len = strlen(input);
pch = strtok(input," ");
ints = calloc(atoi(num_ints), sizeof(char*));
flags = calloc(atoi(num_ints),sizeof(unsigned int));
for(i=0;i<atoi(num_ints);i++) {
ints[i] = malloc(strlen(pch)+1);
strcpy(ints[i], pch);
pch = strtok(NULL, " ");
}
for(k=1;;k++) {
snprintf(str, 6, "%d", k);
l = 0;
n = strlen(str);
len = factorial(n);
family = calloc(len, sizeof(char*));
if(n>=2) {
permute(family, str, 0, n-1, &len);
}else {
family[0] = malloc(n+1);
strcpy(family[0], str);
}
for(i=0;i<len;i++) {
for(j=0;j<atoi(num_ints);j++) {
if(atoi(family[i]) % atoi(ints[j]) == 0) {
if(!icontains(flags, l+1, atoi(ints[j]))) {
flags[l++] = atoi(ints[j]);
if(l>=atoi(num_ints)) goto done;
}
continue;
}
}
}
for(i=0;i<len;i++) {
free(family[i]);
}
free(family);
}
done:
fprintf(stdout,"%d\n",k);
for(i=0;i<len;i++) {
free(family[i]);
}
free(family);
for(i=0;i<atoi(num_ints);i++) {
free(ints[i]);
}
free(ints);
free(flags);
}

void swap(char *x, char *y) {
char temp;
temp = *x;
*x = *y;
*y = temp;
}

int icontains(int *array, int len, int a) {
int i;
for(i=0;i<len;i++) {
if(array[i]==a) {
return 1;
}
}
return 0;
}

int contains(char **array, int len, char *a) {
int i;
for(i=0;i<len;++i) {
if(!array[i] || !strcmp(array[i], a)) {
return 1;
}
}
return 0;
}

void permute(char **result, char *a, int l, int r, int *len) {
int i;
if(l==0) *len = 0;
if(l == r) {
if(a[0] == '0') return;
if(!contains(result, *len, a)) {
result[*len] = malloc(strlen(a)+1);
strcpy(result[(*len)++], a);
}
}else {
for(i=l;i<=r;i++) {
swap((a+l), (a+i));
permute(result, a, l+1, r, len);
swap((a+l), (a+i)); //backtrack
}
}
}

unsigned int factorial(unsigned int n) {
if(n==0)
return 1;
else
return(n*factorial(n-1));
}


I compile it with gcc 5.2.0 with the following flags

-g -O2 -std=gnu99 -static -lm


Here are two sample input respectively outputs

Input:

5
3 5 7 9 11


Output:

459


Input:

7
164 278 293 382 483 598 23


Output:

102246


(EDIT: Here is my faster version, however it is still quite slow if you run it on my second example of input:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

void swap(char *, char *);
int icontains(int *, int, int);
void permute(unsigned int **, char *, int, int, int *);

int main() {
unsigned int i, j, k, l, m, n, len, nints;
char num_ints[10];
char input[128];
char str[10];
char *pch;
unsigned int *flags, *ints, *family;
fgets(num_ints, 10, stdin);
fgets(input, 128, stdin);
nints = atoi(num_ints);
len = strlen(input);
pch = strtok(input," ");
ints = calloc(nints, sizeof(ints));
flags = calloc(nints, sizeof(flags));
family = calloc(10, sizeof(family));
for(i=0;i<nints;i++) {
ints[i] = atoi(pch);
pch = strtok(NULL, " ");
}
for(k=1;;k++) {
snprintf(str, 10, "%d", k);
l = 0;
n = strlen(str);
len = 1;
if(n>=2) {
permute(&family, str, 0, n-1, &len);
}else {
family[0] = k;
}
for(i=0;i<len;i++) {
for(j=0;j<nints;j++) {
if(family[i] % ints[j] == 0) {
if(!icontains(flags, l+1, ints[j])) {
flags[l++] = ints[j];
if(l>=nints) goto done;
}
continue;
}
}
}
}
done:
fprintf(stdout,"%d\n",k);
free(family);
free(ints);
free(flags);
}

void swap(char *x, char *y) {
char temp;
temp = *x;
*x = *y;
*y = temp;
}

int icontains(int *array, int len, int a) {
int i;
for(i=0;i<len;i++) {
if(array[i]==a) {
return 1;
}
}
return 0;
}

void permute(unsigned int **result, char *a, int l, int r, int *len) {
static int buflen = 10;
int *new_result;
int i, aint;
if(l == 0) *len = 0;
if(l == r) {
if(a[0] == '0') return;
aint = atoi(a);
if(!icontains(*result, *len, aint)) {
if(*len > buflen) {
buflen = *len;
new_result = realloc(*result, buflen * sizeof(*result));
if(new_result != NULL) {
*result = new_result;
}else {
fprintf(stderr, "Couldn't allocate memory for buffer.");
}
}
(*result)[(*len)++] = aint;
}
}else {
for(i=l;i<=r;i++) {
swap((a+l), (a+i));
permute(result, a, l+1, r, len);
swap((a+l), (a+i)); //backtrack
}
}
}


)

(EDIT2: I realized I don't how to check for duplicates of permutations because that is slow. Here is the even faster version:

#include <string.h>
#include <stdlib.h>
#include <stdio.h>

void swap(char *, char *);
int icontains(int *, int, int);
void permute(unsigned int **, char *, int, int, int *);

int main() {
unsigned int i, j, k, l, m, n, len, nints;
char num_ints[10];
char input[128];
char str[10];
char *pch;
unsigned int *flags, *ints, *family;
fgets(num_ints, 10, stdin);
fgets(input, 128, stdin);
nints = atoi(num_ints);
len = strlen(input);
pch = strtok(input," ");
ints = calloc(nints, sizeof(ints));
flags = calloc(nints, sizeof(flags));
family = calloc(10, sizeof(family));
for(i=0;i<nints;i++) {
ints[i] = atoi(pch);
pch = strtok(NULL, " ");
}
for(k=1;;k++) {
snprintf(str, 10, "%d", k);
l = 0;
n = strlen(str);
len = 1;
if(n>=2) {
permute(&family, str, 0, n-1, &len);
}else {
family[0] = k;
}
for(i=0;i<len;i++) {
for(j=0;j<nints;j++) {
if(family[i] % ints[j] == 0) {
if(!icontains(flags, l+1, ints[j])) {
flags[l++] = ints[j];
if(l>=nints) goto done;
}
continue;
}
}
}
}
done:
fprintf(stdout,"%d\n",k);
free(family);
free(ints);
free(flags);
}

void swap(char *x, char *y) {
char temp;
temp = *x;
*x = *y;
*y = temp;
}

int icontains(int *array, int len, int a) {
int i;
for(i=0;i<len;i++) {
if(array[i]==a) {
return 1;
}
}
return 0;
}

void permute(unsigned int **result, char *a, int l, int r, int *len) {
static int buflen = 10;
int *new_result;
int i, aint;
if(l == 0) *len = 0;
if(l == r) {
if(a[0] == '0') return;
aint = atoi(a);
if(*len > buflen) {
buflen = (int)(((float)*len)*1.5f);
new_result = realloc(*result, buflen * sizeof(*result));
if(new_result != NULL) {
*result = new_result;
}else {
fprintf(stderr, "Couldn't allocate memory for buffer.");
}
}
(*result)[(*len)++] = aint;
}else {
for(i=l;i<=r;i++) {
swap((a+l), (a+i));
permute(result, a, l+1, r, len);
swap((a+l), (a+i)); //backtrack
}
}
}

)

• Perhaps the latest version as a separate post? Any ideas applied to that take away from the answers to the earlier versions. – chux Oct 21 '15 at 3:39
• @chux Here is the latest version. – Linus Oct 21 '15 at 5:37

# Bug

You write to flags, but you never allocate any space for it. If you had turned on full compiler warnings, it would have warned you about that.

# Use ints, not strings

Part of the reason your program is so slow is that you keep all of your values in strings instead of ints. Then you use atoi() to convert the same strings over and over. Just convert your numbers once and then keep them in int format for later reuse.

# Massive allocations

Your program also allocates one string per permutation (i.e. the family array). You never use the old permutations, so you should just have one permutation buffer and overwrite it instead of allocating new buffers all the time.

• Thanks for the tips, regarding the bug I accidently removed that line of code because it was wrong and never put it back, but I fixed it now :) – Linus Oct 15 '15 at 8:12
• Performance

It is very slow because you build all permutations. It is unnecessary. You need just one, that which has digits in the increasing order (careful with leading 0).

• Algorithm

main is massive and must be refactored into more functions doing clearly defined jobs.
factorial will break at about n == 13 with integer overflow.