Quale numero rimane dopo aver eliminato ripetutamente i quadrati perfetti?

Question

stavo praticando problemi SRM in Topcoder.I sono imbattuto in questo problema

dichiarazione del problema: Oggi è la vigilia di Natale. Persone in tutto il mondo festeggiano questa festa. La seguente storia si svolge nella terra delle renne , dove risiede Babbo Natale.

Le renne amano le caramelle. Hanno n pezzi di caramelle. I pezzi della caramella sono numerati da 1 a n. Dasher è una delle renne. Lui vuole mangiare una delle caramelle. Per scegliere quello che mangerà, Dasher utilizza il seguente metodo: Mentre c'è più di un pezzo di caramelle: scartare tutte le caramelle che sono numerate da quadrati perfetti (cioè, caramelle 1, 4, 9, 16, 25, eccetera.). Rilegare le restanti caramelle k 1 tramite k, mantenendo i numeri nello stesso ordine. Una volta che rimane solo un pezzo di caramelle, Dasher lo mangerà.

Ti è stata data una int n. Il tuo metodo deve calcolare e restituire il numero inizialmente assegnato al pezzo di caramelle mangiato da Dasher.

ho risolto il problema utilizzando ArrayList ma la mia soluzione non riesce per numeri molto grandi (Java Heap Sapce eccezione) .Così stavo pensando se è possibile risolvere il problema in O (1) spazio complessità.

Si prega di dare i vostri suggerimenti e approccio. Non voglio il codice per favore spiega solo la logica per risolvere questo problema.

ho riaperto questa domandacon il problema dichiarazione in modo che maestroes in StackOverflow mi può aiutare a rompere questo problema in O (1) la complessità spaziale

Answer 1

Credo che la seguente soluzione funzioni correttamente e utilizzi la memoria O (1), supponendo che sia possibile contenere un numero intero nello spazio O (1). L'idea è di provare a eseguire questo processo all'indietro fino a quando non trovi la posizione definitiva del pezzo di caramelle corretto. traccia

Let attraverso un esempio di questo problema in cui n = 10. Abbiamo poi ottenere questo:

1 2 3 4 5 6 7 8 9 10 
X  X    X 

2 3 5 6 7 8 10 
X  X 

3 5 7 8 10 
X  X 

5 7 10 
X 

7 10 
X 

10 

Ora, supponiamo che vogliamo calcolare il risultato finale per questo problema. Sappiamo che quando abbiamo finito, le caramelle mangiate sono in posizione 1, dato che c'è rimasto solo un pezzo di caramella. Allora proviamo la sua creazione come questo:

1 

Ora, sappiamo che sul precedente iterazione, la caramella di indice 1 deve essere stato mangiato. Ciò significa che la caramella finale era in realtà nella posizione 2 ultima volta:

? 2 

Sulla ripetizione prima di questo, sappiamo che dal caramelle 1 è stato mangiato, la nostra caramelle deve effettivamente essere in posizione 3:

? ? 3 

A questo punto, ripensiamo ancora a un'iterazione. Sappiamo che la caramella 1 è stata mangiata, ma anche le caramelle 4 sono state mangiate. Ciò significa che l'indice della nostra caramella deve essere stato 5 nella precedente iterazione, poiché quando lo scendiamo nella posizione corretta deve essere saltato indietro di un punto per il primo elemento e uno per il quarto elemento:

? ? ? ? 5 

Ripetendo questa stessa logica, si ottiene che l'indice precedente sarebbe stato 7:

? ? ? ? ? ? 7 

Ora, per il prossimo passo, sappiamo che avremmo scooted la caramella giù due posizioni perché abbiamo abbandonato il 1 ° e 4 ° elementi. Tuttavia, questo metterebbe le nostre caramelle in posizione 9, che sarebbe stata cancellata. Ciò significa che invece avremmo imbattiamo la caramella per posizionare 10:

? ? ? ? ? ? ? ? ? 10 

A questo punto, dal momento che ci sono 10 caramelle a sinistra, sappiamo che abbiamo completamente invertito il processo e finito. Dato che il punto finale di riposo delle nostre caramelle era la posizione 10, sappiamo che la risposta è che la decima caramella è quella che è stata mangiata, il che corrisponde perfettamente al nostro precedente lavoro!

Il trucco dietro questo approccio è che non abbiamo bisogno di molta memoria per farlo funzionare. In particolare, ad ogni passo abbiamo bisogno di tenere traccia di solo poche cose:

• Qual indice è il pezzo finale di caramelle attualmente? Abbiamo bisogno di questo per sapere dove fermarsi.
• Quanti quadrati sono al di sotto di questo indice? Abbiamo bisogno di questo per sapere quanti elementi vengono eliminati su ogni passaggio.
• Qual è il prossimo quadrato perfetto? Abbiamo bisogno di questo per sapere quando il numero di quadrati che vengono cancellati ogni volta aumenta.
• Qual è stato l'ultimo indice che abbiamo esplorato? Questo algoritmo funziona eseguendo il processo all'indietro, quindi ad un certo punto ci accorgeremo che l'abbiamo eseguito una volta di più.Quando ciò accade, dobbiamo essere in grado di "eseguire il backup" di un passaggio per raggiungere l'ultimo indice che non ha superato il limite.

Detto questo, abbiamo il seguente algoritmo:

• Impostare l'indice corrente a 1.
• Impostare il numero di quadrati perfetti piccole per 1.
• Impostare il prossimo quadrato perfetto per 4.
• Impostare l'ultimo indice più piccolo per essere 1.
• Mentre l'indice corrente è inferiore a n:
  01.235.
  • Imposta l'ultimo indice più piccolo come indice corrente (ricorda la soluzione fino ad ora).
  • impostare la corrente index + = il numero di quadrati perfetti piccoli (eseguire il processo indietro di un passo)
  • Se l'indice corrente è uguale al successivo quadrato perfetto, aggiungere uno da esso (un caso limite di corsa all'indietro , se ci ha colpito un quadrato perfetto, dovremmo essere un passo passato)
  • Se l'indice corrente è maggiore il prossimo quadrato perfetto (ora ci sono più numeri che sono cancellati ogni passo):
    • Impostare il quadrato perfetto per essere il prossimo il quadrato perfetto.
    • Aggiungi uno al numero di quadrati perfetti più piccoli dell'indice.
• Ritorna l'ultimo indice più piccolo.

Ciò richiede solo memoria O (1) per contenere tutti i valori.

Proviamo un esempio! Con n = 20, se lavoriamo attraverso il processo formale, otteniamo questo:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 
X  X    X     X 

2 3 5 6 7 8 10 11 12 13 14 15 17 18 19 20 
X  X    X     X 

3 5 7 8 10 11 13 14 15 17 18 19 
X  X    X 

5 7 10 11 13 14 17 18 19 
X  X    X 

7 10 13 14 17 18 
X  X 

10 13 17 18 
X  X 

13 17 
X 

17 

Se corriamo il nostro algoritmo, otteniamo

Current Index  Next Square  Smaller Squares 
1     4    1 
2     4    1 
3     4    1 
5     9    2 
7     9    2 
10     16    3 
13     16    3 
17     25    4 
21     25    4 

Dal 21> 20, l'ultimo indice più piccolo è 17 , quindi restituiamo 17, che è la risposta corretta!

scritto come codice C, presupponendo l'assenza di overflow integer:

int EatenCandyIndex(int n) { 
    int currIndex = 1; 
    int numSmallerSquares = 1; 

    /* Rather than tracking the next square, track the root of the next 
    * square. We can just square this to get the next square. 
    */ 
    int rootOfNextSquare = 2; 

    /* The last spot where the candy would be before we had Too Much Candy. */ 
    int lastIndex = 1; 

    while (currIndex <= n) { 
     lastIndex = currIndex; 

     currIndex += numSmallerSquares; 
     if (currIndex == rootOfNextSquare * rootOfNextSquare) 
      ++currIndex; 

     if (currIndex > rootOfNextSquare * rootOfNextSquare) { 
      ++numSmallerSquares; 
      ++rootOfNextSquare; 
     } 
    } 

    return lastIndex; 
} 

Tuttavia, come scritto, questo algoritmo non è particolarmente efficiente. In particolare, guarda il suo comportamento nell'esempio in cui n = 20. Si noti che abbiamo tre round in cui la dimensione del passo è uno, due con il passo due e tre, ecc. Invece di avere questi round si verificano esplicitamente, potremmo invece calcolare quanti round devono verificarsi con quella dimensione del passo, quindi esegui tutti questi passaggi contemporaneamente. In questo modo, abbiamo sempre un round con taglia uno, un giro con taglia due, un giro con taglia tre, ecc. Per fare ciò, ad ogni passo avremo bisogno di vedere qual è il nostro prossimo obiettivo; questo sarà il numero n o il prossimo quadrato perfetto. Una volta trovato il nostro obiettivo, dobbiamo vedere quanti passaggi sono necessari per arrivarci. Se l'indice corrente è io e il nostro obiettivo è t, e se la nostra dimensione del passo è k, allora dobbiamo prendere i passi ⌈ (t - i)/k ⌉ per arrivarci.Utilizzando un trucco carino con divisione intera, possiamo calcolare questo come

int numSteps = ((t - i) + (k - 1))/k; 

Questo ci dà il seguente algoritmo aggiornato:

int EatenCandyIndexFaster(int n) { 
    int currIndex = 1; 
    int numSmallerSquares = 1; 

    /* Rather than tracking the next square, track the root of the next 
    * square. We can just square this to get the next square. 
    */ 
    int rootOfNextSquare = 2; 

    while (true) { 
     /* Figure out what our target is. */ 
     int target = min(n, rootOfNextSquare * rootOfNextSquare); 

     /* See how many steps are required. */ 
     int numSteps = ((target - currIndex) + (numSmallerSquares - 1))/numSmallerSquares; 

     /* See where we'd end up if we took one fewer than this many steps forward. */ 
     int lastIndex = currIndex + (numSteps - 1) * numSmallerSquares; 

     /* Take that many steps forward. */ 
     currIndex += numSmallerSquares * numSteps; 

     /* There is an edge case here: if we hit our number but it's a perfect square, 
     * we want to return the previous value. 
     */ 
     if (currIndex == n && n == rootOfNextSquare * rootOfNextSquare) 
      return lastIndex; 

     /* Otherwise, if we hit the target number exactly, return it. */ 
     if (currIndex == n) 
      return currIndex; 

     /* Otherwise, if we overshot the target number, hand back where we'd be if we 
     * took one fewer step. 
     */ 
     if (currIndex > n) 
      return lastIndex; 

     /* Oh well; didn't make it. If we hit a perfect square, skip it. */ 
     if (currIndex == rootOfNextSquare * rootOfNextSquare) 
      ++currIndex; 

     ++numSmallerSquares; 
     ++rootOfNextSquare; 
    } 
} 

Questa versione ottimizzata dell'algoritmo viene eseguito in O (√ N) tempo e usa lo spazio O (1). Il motivo per cui il tempo è legato è che ogni passo dell'algoritmo passa al quadrato perfetto successivo e ci sono solo O (√ N) quadrati perfetti in meno di N.

Spero che questo aiuti!

Answer 2

Penso che potrei essere a qualcosa qui .

f(n) = 1 if n = 1 
f(n) = f(n-floor(sqrt(n))) + floor(sqrt(n)) if n is not a perfect square 
f(n) = f(n-1) if n is a perfect square 

Il caso base è chiaro. Il caso "quadrato perfetto" deriva dall'osservazione che se n è un quadrato perfetto, sarà eliminato quando si eliminano i quadrati perfetti, quindi risolverlo equivale a risolvere per uno in meno di esso, comunque. L'ultimo deriva dall'osservazione che dopo aver rimosso i quadrati perfetti (sqrt (n)) e rinumerati, hai spostato alcuni dei numeri a sinistra (ma altrimenti le risposte sono le stesse). Possiamo controllare questo per i primi casi ...

n Answer f(n) 
1  1 1 
2  2 f(2-1) + 1 = f(1) + 1 = 1 + 1 = 2 
3  3 f(3-1) + 1 = f(2) + 1 = 2 + 1 = 3 
4  3 f(4-1) = f(3) = 3 
5  5 f(5-2) + 2 = f(3) + 2 = 3 + 2 = 5 

Proving questo, se è giusto, dovrebbe essere un'estensione semplice, e fino a quando ho completarlo, lo lascio come esercizio. Dovresti controllarlo per un gran numero di casi e vedere se funziona; se non funziona, lo rimuoverò.

EDIT:

Credo che la tendenza sto notando, e la ragione per questo funziona, è che per n non quadrati, la risposta non può mai essere inferiore più grande piazza minore di n. Penso che la ragione di ciò sia che non puoi mai rimuovere m^2 + 1 prima di rimuovere tutto meno o uguale a m^2. Detto questo, le relazioni di ricorrenza di cui sopra sono quasi banalmente vere.

Answer 3

n=1, eats=1 
n=2, eats=2 
n=3, eats=3 
n=4, eats=3 
n=5, eats=5 
... 

Vedete un modello emergente? Vieni con una formula e dimostrare che la formula è corretto utilizzando mathematical induction

Ecco il codice C++:

#include <iostream> 
#include <cmath> 

using namespace std; 

bool is_perfect_square(int value) 
{  
    return pow(static_cast<double>(static_cast<int>(sqrt(static_cast<double>(value)))), 2.0) == value; 
} 

int EatEm(int n) 
{ 
    while (is_perfect_square(n)) 
    { 
     n -= (static_cast<int>(sqrt(static_cast<double>(n)) - 1)); 
    } 

    return n; 
} 

int main() 
{   
    int res = EatEm(25); 
    cout << res << endl; 
    return 0; 
} 

Answer 4

A meno che non ho fatto uno stupido errore, non c'è una formula per questo. Probabilmente potrebbe essere semplificato ma questo è il primo su cui mi sono imbattuto.

from math import floor, sqrt, ceil 

def is_square(i): 
    sq = int(i**0.5) 
    return i == sq*sq 

def brute(n): 
    seq = range(1, n+1) 
    while len(seq) > 1: 
     seq = [x for i,x in enumerate(seq, 1) if not is_square(i)] 
    return seq[0] 

def dasher(n): 
    w = lambda i: floor(sqrt(4*i+1))-1 
    q = lambda i: ceil((i**2+3)/4) 
    return q(w(n-1)+1) 

e di verificare:

>>> b = [brute(i) for i in range(1, 10**3)] 
>>> d = [dasher(i) for i in range(1, 10**3)] 
>>> b[:25] 
[1, 2, 3, 3, 5, 5, 7, 7, 7, 10, 10, 10, 13, 13, 13, 13, 17, 17, 17, 17, 21, 21, 21, 21, 21] 
>>> b == d 
True 

Answer 5

Un'altra variante dello stesso:

a = floor(sqrt(N-1)) 
b = min((N-1)/a, a+1) 
solution = a*b+1 

Oppure, ha dichiarato in modo diverso,

unsigned long long eats(unsigned long long N) { 
    unsigned long long r = (unsigned long long)sqrt(N-1); 
    while(r*r >= N) --r; 
    while(r*(r+2) < N) ++r; 
    if (N <= r*(r+1)) { 
     return r*r+1; 
    } 
    return r*(r+1)+1; 
} 

La dimostrazione segue da analizzare il next functi su cui viene assegnata la posizione successiva di qualsiasi caramella, next(n*n) = 0, in modo che non sia una funzione parziale. Se a*a < N < (a+1)*(a+1), abbiamo next(N) = N - a. Quindi una serie di forma n = a*(a+1) + 1 viaggia

a*(a+1)+1 -> a*a + 1 -> (a-1)*a + 1 -> ... -> 2*3 + 1 ->2*2 + 1 -> 1*2 + 1 -> 1*1 + 1 -> 0*1 + 1 

vediamo che anche i numeri della forma a*a +1 raggiungono 1. Numero di qualsiasi altra forma raggiunge un quadrato più grande di 1 ad un certo punto:

a*(a+1) -> a*a -> eliminated 
a*(a+1) + r -> a*a + r -> (a-1)*a + r 

per 2 <= r <= a. Se r = a, (a-1)*a + r = a*a è un quadrato, con conseguente eliminazione immediata. Se r < a, il numero raggiunto dopo due passaggi ha lo stesso formato con lo stesso r. Proseguendo, ne consegue che il numero raggiunge

(r+1)*(r+2) + r -> (r+1)*(r+1) + r -> r*(r+1) + r -> r*r + r -> r*r -> elimination. 

Così abbiamo visto

• Un numero raggiunge il punto 1 nel processo se e solo se è di forma n*n + 1 o n*(n+1) + 1

L'ultimo numero per raggiungere il primo posto a partire da N caramelle è ovviamente il numero più grande di tale modulo non superiore a N. QED.

Answer 6

Si sa che l'ultimo numero verrà rimosso dal numero speciale 1. Se si generano tutti i numeri rimossi di 1, si avrà un set che contiene il numero speciale. Quindi tutto ciò che devi fare è generare quei numeri.

Quindi vediamo se c'è un motivo.

Sia n 150

Numeri rimossi da 1

r = [1, 2, 3, 5, 7, 10, 13, 17, 21, 26, 31, 37, 43 , 50, 57, 65, 73, 82, 91, 101, 111, 122, 133]

Array di r [i + 1] -r [i]

[1, 1 , 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 10, 10, 11 , 11]

Numeri rimossi da 2

r = [4, 6, 8, 11, 14, 18, 22, 27, 32, 38, 44, 51, 58, 66, 74, 83, 92, 102, 112, 123, 134, 146]

Array di r [i + 1] -r [i]

[2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12]

Numeri rimossi dal 9 Sappiamo che i numeri rimossi da 9 saranno diversi nei primi 2 elementi per 3 e il primo elemento è 9. Da quello, possiamo generare i numeri che verranno rimossi seguendo questo schema di 3 3,4,4,5,5 [9, 12, 15, 19, 23, 28, 33, 39, 45, 52, 59, 67, 75, 84, 93, 103, 113, 124, 135, 147] [3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12]

import math 

def getSpecial(n): 
    sp = list() 
    s = 1 
    while((s * s) <= n): 
     sp.append(s*s) 
     s += 1 
    return sp 

def bruteForce(n): 
    nu = range(n+1) 
    nu.pop(0) 
    while(len(nu) > 1): 
     sp = getSpecial(len(nu)) 
     removed = list() 
     for x in sp[::-1]: 
      removed.append(nu.pop(x-1)) 
    return nu[0] 

def fancyMathWitchCraft(n): 
    sp = getSpecial(n)  
    oneset = [1] 
    j = 0.0 
    while(oneset[-1] <= n): 
     oneset.append(oneset[-1] + int(1 + 1 * math.floor(j/2))) 
     j = j + 1.0 

    if(oneset[-1] <= n): 
     return oneset[-1] 
    if(oneset[-2] <= n): 
     return oneset[-2] 
    if(oneset[-3] <= n): 
     return oneset[-3] 



def main(): 
    for x in range(1,2000): 
     if(bruteForce(x) != fancyMathWitchCraft(x)): 
      print(x, bruteForce(x), fancyMathWitchCraft(x)) 
    print("Done") 

if __name__ == "__main__": 
    main() 

L' la prova di ciò è probabilmente nel fatto che l'ultimo sq perfetto rimuoverà solo 1 numero, quindi il numero finale verrà dal più grande segmento continuo che non sarà influenzato dopo il 1a iterazione, e questo sarà l'ultimo segmento. Se vuoi VERAMENTE una dimostrazione matematica per questo, dovrai rispondere a questa domanda a meta.stackoverflow