Le plus petit multiple d'un nombre donné avec les chiffres 0 et 1.

Question

On vous donne un nombre entier N. Vous devez trouver le plus petit multiple de N qui se compose uniquement des chiffres 0 et 1. Comme ce multiple peut être grand, renvoyez-le sous la forme d'une chaîne de caractères.

La chaîne retournée ne doit pas contenir de zéros en tête.

Par exemple,

Pour N = 55, 110 est le plus petit multiple constitué des chiffres 0 et 1. Pour N = 2, 10 est la réponse.

J'ai vu plusieurs problèmes connexes, mais je n'ai pas pu trouver le problème avec mon code. Voici mon code qui donne TLE dans certains cas, même après avoir utilisé map au lieu de set.

#define ll long long
int getMod(string s, int A)
{
    int res=0;
    for(int i=0;i<s.length();i++)
    {
        res=res*10+(s[i]-'0');
        res%=A;
    }
    return res;
}
string Solution::multiple(int A) {
    if(A<=1)
    return to_string(A);

    queue<string>q;
    q.push("1");
    set<int>st;
    string s="1";

    while(!q.empty())
    {
        s=q.front();
        q.pop();
        int mod=getMod(s,A);
        if(mod==0)
        {
            return s;
        }
        else if(st.find(mod)==st.end())
        {
            st.insert(mod);
            q.push(s+"0");
            q.push(s+"1");
        }
    }

}

Answer 1

Voici une mise en œuvre en Raku.

my $n = 55;
(1 .. Inf).map( *.base(2) ).first( * %% $n );

(1 .. Inf) est un paresseux liste de un à l'infini. L'"étoile quelconque" * établit une fermeture et représente l'élément actuel dans le fichier map .

base est une méthode de Rakus Num qui renvoie une représentation en chaîne d'un nombre donné dans la base souhaitée, ici une chaîne binaire.

first renvoie l'élément courant lorsque la fermeture "whatever star" est vraie pour lui.

En %% est le divisible by il convertit implicitement son côté gauche en Int .

Oh, et pour couronner le tout. C'est facile a paralléliser pour que votre code puisse utiliser plusieurs cœurs de processeurs :

 (1 .. Inf).race( :batch(1000), :degree(4) ).map( *.base(2) ).first( * %% $n );

Answer 2

Comme mentionné dans la référence "mathématique", le résultat est lié à la congruence de la puissance de 10 modulo A .

Si

n = sum_i a[i] 10^i

puis

n modulo A = sum_i a[i] b[i]

Où le a[i] sont égaux à 0 ou 1, et les b[i] = (10^i) modulo A

Le problème est alors de trouver le minimum a[i] séquence, telle que la somme est égale à 0 modulo A .

D'un point de vue graphique, nous devons trouver le plus court chemin vers zéro modulo A.

Une BFS est généralement bien adaptée pour trouver un tel chemin. Le problème est l'augmentation exponentielle possible du nombre de noeuds à visiter. Ici, on est sûr d'obtenir un nombre de nœuds inférieur à A en rejetant les nœuds dont la somme (modulo A ) a déjà été obtenu (voir le vecteur used dans le programme). Notez que ce rejet est nécessaire afin d'obtenir le nombre minimum à la fin.

Voici un programme en C++. La solution étant assez simple, elle devrait être facile à comprendre même par ceux qui ne sont pas familiers avec le C++.

#include <iostream>
#include <string>
#include <vector>

struct node {
    int sum = 0;
    std::string s;
};

std::string multiple (int A) {
    std::vector<std::vector<node>> nodes (2);
    std::vector<bool> used (A, false);
    int range = 0;
    int ten = 10 % A;
    int pow_ten = 1;

    if (A == 0) return "0";
    if (A == 1) return "1";

    nodes[range].push_back (node{0, "0"});
    nodes[range].push_back (node{1, "1"});
    used[1] = true;

    while (1) {
        int range_new = (range + 1) % 2;
        nodes[range_new].resize(0);
        pow_ten = (pow_ten * ten) % A;

        for (node &x: nodes[range]) {
            node y = x;
            y.s = "0" + y.s;
            nodes[range_new].push_back(y);
            y = x;
            y.sum = (y.sum + pow_ten) % A;
            if (used[y.sum]) continue;
            used[y.sum] = true;
            y.s = "1" + y.s;
            if (y.sum == 0) return y.s;
            nodes[range_new].push_back(y);
        }
        range = range_new;
    }
}

int main() {
    std::cout << "input number: ";
    int n;
    std::cin >> n;
    std::cout << "Result = " << multiple(n) << "\n";
    return 0;
}

EDIT

Le programme ci-dessus utilise une sorte de mémorisation afin d'accélérer le processus, mais pour les entrées importantes, la mémoire devient trop importante. Comme indiqué dans un commentaire par exemple, il ne peut pas gérer le cas N = 60000007.

J'ai amélioré un peu la vitesse et la portée avec les modifications suivantes :

• Une fonction ( reduction ) a été créé pour simplifier la recherche lorsque le nombre d'entrée est divisible par 2 ou 5.
• Pour la mémorisation des nœuds ( nodes ), un seul tableau est utilisé maintenant au lieu de deux
• Une sorte de procédure de rencontre entre les deux est utilisée : dans un premier temps, une fonction mem_gen mémorise toutes les séquences 01 pertinentes jusqu'à N_DIGIT_MEM (=20) chiffres. Ensuite, la procédure principale multiple2 génère des séquences 01 valides "après les 20 premiers chiffres" et recherche ensuite dans la mémoire une "séquence complémentaire" telle que la concaténation des deux soit une séquence valide

Avec ce nouveau programme, le cas N = 60000007 donne le bon résultat (100101000001001010011110111, 27 chiffres) en environ 600ms sur mon PC.

EDIT 2

Au lieu de limiter le nombre de chiffres pour la mémorisation dans la première étape, j'utilise maintenant un seuil sur la taille de la mémoire, car cette taille ne dépend pas seulement du nombre de chiffres mais aussi du nombre d'entrée. Notez que la valeur optimale de ce seuil dépendrait du nombre de chiffres en entrée. Ici, j'ai choisi un seuil de 50k comme compromis. Avec un seuil de 20k, pour 60000007, j'obtiens le bon résultat en 36 ms. Par ailleurs, avec un seuil de 100k, le pire cas 99999999 est résolu en 5s.

J'ai fait différents tests avec des valeurs inférieures à 10^9. Dans presque tous les cas testés, le résultat est fourni en moins d'une seconde. Cependant, j'ai rencontré un cas particulier N=99999999, pour lequel le résultat consiste en 72 "1" consécutifs. Dans ce cas particulier, le programme prend environ 6,7s. Pour 60000007, le bon résultat est obtenu en 69ms.

Voici le nouveau programme :

    #include <iostream>
    #include <string>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <chrono>
    #include <cmath>
    #include <algorithm>

    std::string reverse (std::string s) {
        std::string res {s.rbegin(), s.rend()};
        return res;
    }

    struct node {
        int sum = 0;
        std::string s;
        node (int sum_ = 0, std::string s_ = ""): sum(sum_), s(s_) {};
    };

//  This function simplifies the search when the input number is divisible by 2 or 5
    node reduction (int &X, long long &pow_ten) {
        node init {0, ""};
        while (1) {
            int digit = X % 10;
            if (digit == 1 || digit == 3 || digit == 7 || digit == 9) break;
            switch (digit) {
                case(0):
                    X /= 10;
                    break;
                case(2):
                case(4):
                case(6):
                case(8):
                    X = (5*X)/10;
                    break;
                case(5):
                    X = (2*X)/10;
                    break;
            }
            init.s.push_back('0');
            pow_ten = (pow_ten * 10) % X;
        }       
        return init;
    }

const int N_DIGIT_MEM = 30;     // 20
const int threshold_size_mem = 50000;

//  This function memorizes all relevant 01 sequences up to N_DIGIT_MEM digits
bool gene_mem (int X, long long &pow_ten, int index_max, std::map<int, std::string> &mem, node &result) {

    std::vector<node> nodes;
    std::vector<bool> used (X, false);
    bool start = true;

    for (int index = 0; index < index_max; ++index){
        if (start) {
                node x = {int(pow_ten), "1"};
                nodes.push_back (x);
        } else {
            for (node &x: nodes) {
                x.s.push_back('0');
            }
            int n = nodes.size();

            for (int i = 0; i < n; ++i) {
                node y = nodes[i];
                y.sum = (y.sum + pow_ten) % X;
                y.s.back() = '1';
                if (used[y.sum]) continue;
                used[y.sum] = true;
                if (y.sum == 0) {
                    result = y;
                    return true;
                }
                nodes.push_back(y);
            }   
        }
        pow_ten = (10 * pow_ten) % X;
        start = false;
        int n_mem = nodes.size();
        if (n_mem > threshold_size_mem) {
            break;
        }
    }
    for (auto &x: nodes) {
        mem[x.sum] = x.s;
    }
    //std::cout << "size mem = " << mem.size() << "\n";
    return false;
}
//  This function generates valid 01 sequences "after the 20 first digits" and then in the memory 
//  looks for a "complementary sequence" such that the concatenation of both is a valid sequence
    std::string multiple2 (int A) {
        std::vector<node> nodes;
        std::map<int, std::string> mem;
        int ten = 10 % A;
        long long pow_ten = 1;
        int digit;

        if (A == 0) return "0";
        int X = A;
        node init = reduction (X, pow_ten);

        if (X != A) ten = ten % X;

        if (X == 1) {
            init.s.push_back('1');
            return reverse(init.s);
        }
        std::vector<bool> used (X, false);
        node result;
        int index_max = N_DIGIT_MEM;
        if (gene_mem (X, pow_ten, index_max, mem, result)) {
            return reverse(init.s + result.s);
        }   

        node init2 {0, ""};
        nodes.push_back(init2);

        while (1) {
            for (node &x: nodes) {
                x.s.push_back('0');
            }
            int n = nodes.size();
            for (int i = 0; i < n; ++i) {
                node y = nodes[i];
                y.sum = (y.sum + pow_ten) % X;
                if (used[y.sum]) continue;
                used[y.sum] = true;
                y.s.back() = '1';
                if (y.sum != 0) {
                    int target = X - y.sum;
                    auto search = mem.find(target);
                    if (search != mem.end()) {
                        //std::cout << "mem size 2nd step = " << nodes.size() << "\n";
                        return reverse(init.s + search->second + y.s);
                    }
                }
                nodes.push_back(y);
            }
            pow_ten = (pow_ten * ten) % X;
        }
    }

    int main() {
        std::cout << "input number: ";
        int n;
        std::cin >> n;
        std::string res;

        auto t1 = std::chrono::high_resolution_clock::now();
        res = multiple2(n),
        std::cout << "Result = " << res << "  ndigit = " << res.size() << std::endl;
        auto t2 = std::chrono::high_resolution_clock::now();
        auto duration2 = std::chrono::duration_cast<std::chrono::microseconds>( t2 - t1 ).count();
        std::cout << "time = " << duration2/1000 << " ms" << std::endl;

        return 0;
    }

Answer 3

Pour les personnes plus familières avec Python, voici une version convertie du code de @Damien. L'idée importante de Damien est de réduire fortement l'arbre de recherche, en profitant du fait que chaque somme partielle ne doit être étudiée qu'une seule fois, à savoir la première fois qu'elle est rencontrée.

Le problème est également décrit à l'adresse suivante Casse-tête mathématique mais là, ils se concentrent surtout sur l'existence nécessaire d'une solution. Il y a aussi du code mentionné à la encyclopédie en ligne des séquences d'entiers . Le site sage version semble être quelque peu similaire.

J'ai fait quelques changements :

• Commencer par une liste vide permet de résoudre correctement A=1 tout en simplifiant le code. La multiplication par 10 est déplacée à la fin de la boucle. En faisant la même chose pour 0 semble être difficile, car log10(0) es minus infinity .
• Au lieu d'alterner entre nodes[range] y nodes[new_range] deux listes différentes sont utilisées.

• Comme Python prend en charge les entiers de précision arbitraire, les résultats partiels pourraient être stockés sous forme de nombres décimaux ou binaires au lieu de chaînes de caractères. Ceci n'est pas encore fait dans le code ci-dessous.

  from collections import namedtuple

  node = namedtuple('node', 'sum str')

  def find_multiple_ones_zeros(A): nodes = [node(0, "")] used = set() pow_ten = 1 while True: new_nodes = [] for x in nodes: y = node(x.sum, "0" + x.str) new_nodes.append(y) next_sum = (x.sum + pow_ten) % A y = node((x.sum + pow_ten) % A, x.str) if next_sum in used: continue used.add(next_sum) y = node(next_sum, "1" + x.str) if next_sum == 0: return y.str new_nodes.append(y) pow_ten = (pow_ten * 10) % A nodes = new_nodes