I numeri che terminano in 3 hanno almeno un multiplo con tutti quelli

Ciao Ecco un Q che è stato chiesto in Adobe Intervista.I numeri che terminano in 3 hanno almeno un multiplo con tutti quelli

Numbers ending in 3 have at least one multiple having all ones. 
for eg., 3 and 13 have amultiples like 111 and 111111 respectively. Given such 
a no. , find the smallest such multiple of that number. The multiple can 
exceed the range of int, long. You cannot use any complex data structure.

Mi potete fornire una soluzione efficiente

fonte

2013-07-02 Euler

Quindi, che cosa hai bisogno esattamente? – felknight

Una risposta esplicativa fornita [qui] (http://stackoverflow.com/a/7130063). – TheHappySloth

Possibile duplicato di [Algoritmo in C - giocando con i numeri - numero con 3 nella posizione delle unità] (https://stackoverflow.com/questions/7129855/algorithm-in-c-playing-with-numbers-number-with-3 -in-units-place) – roottraveller

avuto la risposta adesso :)

int count=1, rem=1; 
while(rem) 
{ 
rem= (rem*10+1)%n; count++; 
} 
while(count--){ cout<<"1";}

fonte

2013-07-02 18:24:37 Euler

hai appena detto che il multiplo potrebbe superare l'intervallo intero. – Aravind

@HighPerformanceMark La domanda non esclude numeri interi o interi lunghi, ma indica semplicemente che una soluzione può superare l'intervallo di tali valori. Esclude l'uso di strutture dati complesse. Non esclude l'uso dell'aritmetica modulare e delle osservazioni della relazione tra 'x mod 3' e' (x * 10 + 1) mod 3' per calcolare una stringa di caratteri che rappresenta un multiplo appropriato senza effettivamente calcolare tali multipli ... – twalberg

@Aravind sì è il conteggio è il numero di volte 1 sta accadendo nel ciclo multiplo mentre sta stampando quel numero – Euler

Ecco un tentativo di farlo in modo più efficiente che cercare 1, 11, 111, 111 .. Potrebbe questo pagare. C'è una risposta più elegante meglio di provare i numeri uno alla volta?

Scrivere i numeri 1, 11, 111, ... come (10^k - 1)/9, dove è noto che la divisione è esatta. Dato un numero bersaglio nella forma 10x + 3 vogliamo trovare il più piccolo k solving (10^k - 1)/9 = Y (10x + 3) dove Y è un numero intero. Cerca piccole soluzioni di 10^k = 1 mod 9 (10x + 3). Questo è http://en.wikipedia.org/wiki/Discrete_logarithm eccetto che l'aritmetica mod 9 (10x + 3) non costituisce necessariamente un gruppo - tuttavia l'algoritmo http://en.wikipedia.org/wiki/Baby-step_giant-step dovrebbe ancora essere applicato e potrebbe essere usato per cercare intervalli di k costantemente crescenti, invece di cercare possibili valori di k uno alla volta .

fonte

2013-07-02 19:07:11 mcdowella

Penso che questa sia la vera soluzione, non altri. Ma volevo solo capire quanto è efficiente rispetto a provare 1,11,111 ecc. Stiamo calcolando 10^k mod A (supponiamo A = 9 (10x + 3)) ogni iterazione, con l'aumento di k, giusto? Cosa succede se la variabile che memorizza 10^k trabocca e il risultato è molto grande? Questo è il metodo ottimale che l'intervistatore si aspetta di usare con proprietà congruenti? -Grazie .. sono solo curioso –

L'aritmetica richiesta è mod 9 (10x + 3) e se questa overflow è sfortunata, a meno che non si passi alla precisione multipla, ma ciò accade un po 'di tempo dopo 10^k di overflow. L'efficienza deriva dal fatto che l'algoritmo passo-passo/passo gigante consente di cercare una gamma di N possibilità nel tempo O (sqrt (N)) – mcdowella

#include <iostream> 
using namespace std; 

int main() { 
    int t; 
    cin>>t; 
    while(t--){ 
     long long n; 
     cin>>n; 
     long long cur = 1; 
     while(cur%n!=0){ 
      cur = cur*10+1; 
     } 
     cout<<cur<<endl; 
    } 
    return 0; 
}

fonte

2015-10-12 20:52:05

Uso di 'long long' per evitare di 'superare l'intervallo di int, lungo' è povero. Hai provato a capire _come_ altre soluzioni non hanno bisogno di numeri (molto) maggiori del numero dato? – greybeard

soluzione indipendente dalle dimensioni di uscita:

public String ones(int n) 
{ 
    int i, m = 1; 
    String num="1"; 

    for (i = 1; i <= n; i++) { 
       if (m == 0) 
       return num; 
      /* Solution found */ 
      num=num+"1"; 
      m = (10*m + 1) % n; 
    } 
    return null; /* No solution */

}

fonte

2016-01-27 16:49:01

I numeri che terminano in 3 hanno almeno un multiplo con tutti quelli

risposta

Problemi correlati