Como encontrar o menor número com apenas 0 e 1, que é dividido por um determinado número?

Cada inteiro positivo divide um número cuja representação (base 10) contém apenas zeros e uns.

Pode-se provar que:

Considere os números 1, 11, 111, 1111, etc. até 111 … 1, em que o último número tem n + 1 dígitos. Chame esses números m 1 , m 2 , …, m n + 1 . Cada um tem um resto quando dividido por n, e dois desses remanescentes devem ser os mesmos. Porque há n + 1 deles, mas apenas n valores que um resto pode levar. Esta é uma aplicação do famoso e útil “princípio do escaninho”;

Suponha que os dois números com o mesmo resto sejam m i e m j , com i <j. Agora subtraia o menor do maior. O número resultante, m i −m j , consistindo de j – i ones seguido por i zeroes, deve ser um múltiplo de n.

Mas como encontrar a menor resposta? e effciently?

Boa pergunta. Eu uso o BFS para resolver essa questão com meet-in-the-middle e algumas outras podas. Agora meu código pode resolver n <10 9 em um tempo razoável.

#include  #include  class BIT { private: int x[40000000]; public: void clear() {memset(x, 0, sizeof(x));} void setz(int p, int z) {x[p>>5]=z?(x[p>>5]|(1<<(p&31))):(x[p>>5]&~(1<<(p&31)));} int bit(int p) {return x[p>>5]>>(p&31)&1;} } bp, bq; class UNIT { private: int x[3]; public: int len, sum; void setz(int z) {x[len>>5]=z?(x[len>>5]|(1<<(len&31))):(x[len>>5]&~(1<<(len&31)));} int bit(int p) {return x[p>>5]>>(p&31)&1;} } u; class MYQUEUE { private: UNIT x[5000000]; int h, t; public: void clear() {h = t = 0;} bool empty() {return h == t;} UNIT front() {return x[h];} void pop() {h = (h + 1) % 5000000;} void push(UNIT tp) {x[t] = tp; t = (t + 1) % 5000000;} } p, q; int n, md[100]; void bfs() { for (int i = 0, tp = 1; i < 200; i++) tp = 10LL * (md[i] = tp) % n; u.len = -1; u.sum = 0; q.clear(); q.push(u); bq.clear(); while (1) { u = q.front(); if (u.len >= 40) break; q.pop(); u.len++; u.setz(0); q.push(u); u.setz(1); u.sum = (u.sum + md[u.len]) % n; if (!bq.bit(u.sum)) {bq.setz(u.sum, 1); q.push(u);} if (!u.sum) { for (int k = u.len; k >= 0; k--) printf("%d", u.bit(k)); puts(""); return; } } u.len = 40; u.sum = 0; p.clear(); p.push(u); bp.clear(); while (1) { u = p.front(); p.pop(); u.len++; u.setz(0); p.push(u); u.setz(1); u.sum = (u.sum + md[u.len]) % n; if (!bp.bit(u.sum)) {bp.setz(u.sum, 1); p.push(u);} int bf = (n - u.sum) % n; if (bq.bit(bf)) { for (int k = u.len; k > 40; k--) printf("%d", u.bit(k)); while (!q.empty()) { u = q.front(); if (u.sum == bf) break; q.pop(); } for (int k = 40; k >= 0; k--) printf("%d", u.bit(k)); puts(""); return; } } } int main(void) { // 0 < n < 10^9 while (~scanf("%d", &n)) bfs(); return 0; } 

A questão é igual a usar 10 i mod n (para cada i, pode ser usado no máximo uma vez) para obter uma sum m de n. É como um problema de mochila ou um problema de sum de subconjuntos. Desta forma, a programação dinâmica fará a tarefa.

Na programação dinâmica, a complexidade é O(k*n) . k é o número de dígitos na resposta. Para n <10 5 , esse código funciona perfeitamente.

Código:

 #include  #define NUM 2000 int main(int argc, char* argv[]) { signed long pow[NUM],val[NUM],x,num,ten; int i,j,count; for(num=2; numpow[x%num]-1)printf("0"); count=pow[x%num]-1; printf("1"); x=(num+x-val[pow[x%num]])%num; } while(count-->0)printf("0"); } printf("\n"); } } 

PS: Esta sequência no OEIS .

Existe uma solução O (n) -time (operações aritméticas mod n, realmente), que é mais eficiente que a resposta aceita atualmente. A idéia é construir um grafo nos vértices 0..n-1 onde o vértice i tem conexões para (i * 10)% n e (i * 10 + 1)% n, então use a pesquisa em largura para encontrar o menos lexicograficamente caminho de 1 a 0.

 def smallest(n): parents = {} queue = [(1 % n, 1, None)] i = 0 while i < len(queue): residue, digit, parent = queue[i] i += 1 if residue in parents: continue if residue == 0: answer = [] while True: answer.append(str(digit)) if parent is None: answer.reverse() return ''.join(answer) digit, parent = parents[parent] parents[residue] = (digit, parent) for digit in (0, 1): queue.append(((residue * 10 + digit) % n, digit, residue)) return None 

Aqui está uma solução readable usando o BFS em java. A abordagem é semelhante à de David, com algumas melhorias.

Você constrói uma tree de decisão para append um 0 ou 1 e executar o BFS para encontrar o menor desses múltiplos válidos do número de input.

Essa solução também aproveita o módulo (do número de input) para calcular resultados realmente grandes. Descrição completa disponível nos comentários do código.

Você também pode acessar o mesmo snippet de código no ideone .

 import java.util.ArrayDeque; import java.util.Arrays; import java.util.HashSet; import java.util.Queue; import java.util.Scanner; import java.util.Set; public class Main { // Return the smallest multiple of the number (as a string) consisting only of digits 0 and 1 // // All possible digits that can be constructed using the digits 0/1 can be represented // as a tree, where at each level, appending a 0 is one branch and appending a 1 is another // // If we perform BFS on this tree, the first number we see which is an exact multiple of the input // number will be the result (since it will be the smallest). Make sure to consider left // branch (ie 0) before considering the right branch (ie 1) // // The 2 paths we take at each level when the current number is num: // (num * 10) // (num * 10) + 1 // // Since the result can grow huge quite easily, it might not be possible to store the result in a // 32 or even a 64 bit int/long variable. // // One alternative is to use BigNumber, but a simpler alternative exists if we leverage modulo. // // The operations we perform above (ie multiplications and additions) will retain the useful part // of the result when using modulo. We use the given number itself as the modulo, and when we see a // result of 0, it means we have found a number which is an exact multiple of the input number. // // To reconstruct the number, we need to store the parent nodes of each node, when adding the node // in the queue (similar to using BFS for computing shortest path) // // We will also need to know if we appended a 0 or a 1 at each step, and so we add this information // as part of the node data structure as well. // // Re-visiting nodes is unecessary since we have seen this modulo result (ie value % num) already. // Any additional digits we add from now will only make the number longer and we already are tracking // the path for this same modulo result we've seen earlier. // public static String multiple(int num) { if (num < 0) { throw new IllegalArgumentException("Invalid args"); } String result = "0"; if (num > 0) { // An array to mark all the visited nodes boolean[] isVisited = new boolean[num]; Arrays.fill(isVisited, false); // The queue used by BFS Queue queue = new ArrayDeque<>(); // Add the first number 1 and mark it visited queue.add(new Node(true, 1 % num, null)); isVisited[1 % num] = true; // The final destination node which represents the answer Node destNode = null; while (!queue.isEmpty()) { // Get the next node from the queue Node currNode = queue.remove(); if (currNode.val == 0) { // We have reached a valid multiple of num destNode = currNode; break; } else { // Visit the next 2 neighbors // Append 0 - (currNode.val * 10) // Append 1 - (currNode.val * 10) + 1 // Append a '0' int val1 = (currNode.val * 10) % num; if (!isVisited[val1]) { queue.add(new Node(false, val1, currNode)); isVisited[val1] = true; } // Append a '1' int val2 = (val1 + 1) % num; if (!isVisited[val2]) { queue.add(new Node(true, val2, currNode)); isVisited[val2] = true; } } } // Trace the path from destination to source if (destNode == null) { throw new IllegalStateException("Result should not be null"); } else { StringBuilder reverseResultBuilder = new StringBuilder(); Node currNode = destNode; while (currNode != null) { reverseResultBuilder.append(currNode.isDigitOne ? '1' : '0'); currNode = currNode.parent; } result = reverseResultBuilder.reverse().toString(); } } return result; } // Node represents every digit being appended in the decision tree private static class Node { // True if '1', false otherwise (ie '0') public final boolean isDigitOne; // The number represented in the tree modulo the input number public final int val; // The parent node in the tree public final Node parent; public Node(boolean isDigitOne, int val, Node parent) { this.isDigitOne = isDigitOne; this.val = val; this.parent = parent; } } public static void main(String[] args) { int num = new Scanner(System.in).nextInt(); System.out.println("Input number: " + num); System.out.println("Smallest multiple using only 0s and 1s as digits: " + Main.multiple(num)); } } 

Eu acho que esta é uma questão justa e interessante.

Por favor, note que embora o que você descreva seja uma prova de que sempre existe tal número, o número encontrado nem sempre será mínimo.

A única solução que consigo imaginar é calcular os restos das potências de 10 módulos do n dado e então tentar construir uma sum que dê o resto 0 módulo n usando no máximo um de cada um desses poderes. Você nunca precisará de mais do que poderes diferentes (o que prova sua pergunta).

Esta é uma maneira rápida de obter as primeiras 792 respostas. Def o código mais simples:

 __author__ = 'robert' from itertools import product def get_nums(max_length): assert max_length < 21 #Otherwise there will be over 2 million possibilities for length in range(1, max_length + 1): for prod in product("10", repeat=length): if prod[0] == '1': yield int("".join(prod)) print list(get_nums(4)) [1, 11, 10, 111, 110, 101, 100, 1111, 1110, 1101, 1100, 1011, 1010, 1001, 1000] nums = sorted(get_nums(20)) print len(nums) solution = {} operations = 0 for factor in range(1, 1000): for num in nums: operations += 1 if num % factor == 0: solution[factor] = num break print factor, operations if factor not in solution: print "no solution for factor %s" % factor break print solution[787] max_v = max(solution.values()) for factor, val in solution.items(): if val == max_v: print factor, max_v [1, 11, 10, 111, 110, 101, 100, 1111, 1110, 1101, 1100, 1011, 1010, 1001, 1000] 1048575 1 1 2 3 3 10 4 14 5 16 6 30 7 39 8 47 9 558 10 560 11 563 12 591 13 600 14 618 15 632 16 648 17 677 18 1699 19 1724 20 1728 .. .. 187 319781 188 319857 .. .. 791 4899691 792 5948266 no solution for factor 792 10110001111 396 11111111111111111100 

Aqui está uma solução C # usando linked list

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; using System.Collections; namespace ConsoleApplication1 { class Program { public static void print(LinkedList lst) { foreach(int i in lst) { Console.Write(i); } } static void Main(string[] args) { int number = Convert.ToInt32(Console.ReadLine()); int product; LinkedList list = new LinkedList(); bool Istrue = true; int range = 1; while (range <= 10) { Istrue = true; product = number * range; while (product > 0) { list.AddFirst(product % 10); product /= 10; } foreach (int i in list) { if (i > 1) Istrue = false; } if (Istrue) { print(list); break; } else { list.Clear(); } range++; } Console.WriteLine("Done"); string s = Console.ReadLine(); } } } 

Meu algoritmo será: –

1) Construa a tree ordenada de n números possíveis (digamos que n seja inicialmente 10). Portanto, neste exemplo, ele conterá 1,10,11,100,101,110,111 ….

2) Em seguida, percorra a lista e execute em cada não x% GivenNo, se for o menor possível

3) Caso contrário, repita o passo 3 com outros 10 números

 using System; using System.Collections.Generic; using System.Diagnostics; using System.Linq; using System.Text; using System.Threading.Tasks; namespace ConsoleApplication2 { class Class1 { public static void Main() { List possibleCombination = new List(); for (int i = 2; i < 10000; i++) { possibleCombination.Add(Convert.ToString(i, 2)); } var input = Console.ReadLine(); long output = 0; foreach (var item in possibleCombination) { if (Convert.ToInt64(item) % Convert.ToInt64(i) == 0) { output = Convert.ToInt64(item); break; } } Console.WriteLine(output); Console.ReadLine(); } } } 

Aqui está o código c # completo em O (n) usando a abordagem graph e bfs.

 using System; using System.Collections.Generic; using System.Collections; using System.Security.Cryptography; using System.Linq; using System.Runtime.InteropServices; class Solution { public class Edge : IComparable { public int From { get; set; } public int To { get; set; } public int Weight { get; set; } public bool IsDirected { get; set; } public Edge(int from, int to, bool isDirected = false, int weight = 0) { this.From = from; this.To = to; this.Weight = weight; this.IsDirected = isDirected; } public int CompareTo(object obj) { if (obj is Edge) { var comparingTo = obj as Edge; return this.Weight.CompareTo(comparingTo.Weight); } return 0; //TODO:what should we return? } } public class AdjNode { public int EdgeWeight { get; set; } public int Id { get; set; } public AdjNode(int id) { this.Id = id; this.EdgeWeight = 0; } public AdjNode(int id, int weight) { this.Id = id; this.EdgeWeight = weight; } } public class GraphAdj { public int V { get; set; } public List[] adj { get; set; } public List Edges { get; set; } public GraphAdj(int v) { this.V = v; this.adj = new List[this.V]; for (int i = 0; i < this.V; i++) { this.adj[i] = new List(); //allocate actual memory } this.Edges = new List(); } public void AddDirectedEdge(int from, int to) { adj[from].Add(new AdjNode(to)); this.Edges.Add(new Edge(from,to,true)); } public void AddDirectedEdge(int from, int to, int weight) { adj[from].Add(new AdjNode(to,weight)); this.Edges.Add(new Edge(from, to, true, weight)); } } public string multiple(int A) { int n = A; GraphAdj directedGraphForNumber = new GraphAdj(n); Queue queueForNumbers = new Queue(); string result = String.Empty; bool[] visitedForNumbers = new bool[directedGraphForNumber.V]; int[] suffixes = new int[2] { 0, 1 }; //we will start from 1st node out of n node queueForNumbers.Enqueue(1); visitedForNumbers[1] = true; while (true) { int from = queueForNumbers.Dequeue(); if (from == 0) break; for (int i = 0; i < suffixes.Length; i++) { int toNode = from * 10 + suffixes[i]; int reminder = toNode % n; if (visitedForNumbers[reminder] == false) { visitedForNumbers[reminder] = true; queueForNumbers.Enqueue(reminder); directedGraphForNumber.AddDirectedEdge(from, reminder,suffixes[i]); } } } //Do BFS traversal with edges until zero th node encounters bool[] visitedForBfs = new bool[directedGraphForNumber.V]; Queue queueForBfs = new Queue(); int[] parent = new int[directedGraphForNumber.V]; int source = 1; visitedForBfs[source] = true; queueForBfs.Enqueue(source); parent[source] = -1; while (queueForBfs.Count > 0) { int currentVertex = queueForBfs.Dequeue(); foreach (var adjacentVertex in directedGraphForNumber.adj[currentVertex]) { if (visitedForBfs[adjacentVertex.Id] == false) { queueForBfs.Enqueue(adjacentVertex.Id); parent[adjacentVertex.Id] = currentVertex; visitedForBfs[adjacentVertex.Id] = true; } if (adjacentVertex.Id == 0) // we reach zero th node { queueForBfs.Clear(); //break out of bfs } } } //now time to find path all the way to start from zero using parent List pathListUsingParent = new List(); int current = 0; pathListUsingParent.Add(0); // add zero while (current!=1) { pathListUsingParent.Add(parent[current]); current = parent[current]; } //reverse path to make number using edges pathListUsingParent.Reverse(); result += "1"; //start node //now read edges for (int i = 0; i < pathListUsingParent.Count-1; i++) { int from = pathListUsingParent[i]; int to = pathListUsingParent[i + 1]; result += directedGraphForNumber.adj[from].FirstOrDefault(adj => adj.Id == to).EdgeWeight; } return result; } }