Codility złożoność mojego rozwiązania

0

Witam

Moje rozwiązanie jest oczywiście niedoskonałe, ale zastanawiam się nad jego złożonością. Mi wychodzi N*logN, przy czym podstawa logarytmu to 10 tutaj, czy dobrze liczę?

Dziękuję i pozdrawiam.

Załaczam kod:

int solution(int N)
{
    int counter = 0;
    int num = pow(11,N);

    for(int i = 1; i < N; ++i)
    {
        while (num != 0)
        {
            if (fmod(num,pow(10,i)) == 1)
                counter++;

            num = num / pow(10, i);
        }
    }
    return counter;
}

0

ten kod nie działa bo warunek while zawsze ebdzie prawdziwy

0

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include "math.h"
#include <map>

using namespace std;

int solution(int N)
{
if(N == 0)
return 1;
if(N = 1)
return 2;

int counter = 0;
int num = pow(11,N);

for(int i = 1; i < N; ++i)
{
    while (num != 0)
    {
        if (fmod(num,pow(10,i)) == 1)
            counter++;

        num = num / pow(10, i);
    }
}
return counter;

}

int main()
{
int n = 3;

cout<<solution(n)<<endl;

cout<<pow(11, n)<<endl;

}

od 0 do 8 daje prawidłowe wartości.

0
  1. źle zadane pytanie. Nie powinniśmy zgadywać na czym polega problem na podstawie kodu. Zawsze pisz co kod ma robić, a w takim przypadku dawaj link do zadania.
  2. źle zrobione, bo brak ci świadomości, że double ma skończoną precyzję i od pewnej potęgi masz zaokrąglenia
  3. na dodatek problem nie został wygooglowany:

http://stackoverflow.com/a/8498251/1387438
http://www.algorytm.org/algorytmy-arytmetyczne/szybkie-potegowanie-modularne.html
https://pl.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/fast-modular-exponentiation

Januszeg napisał(a):

od 0 do 8 daje prawidłowe wartości.

A co w tym dziwnego: https://www.google.com/search?q=ln+(11^9)+%2F+ln+(2)

0

MarekR22

Dziękuję za odpowiedź i pomoc ale jeśli umiałbyś czytać ze zrozumieniem to mnie wcale nie interesuje czy ten kod działa poprawnie dla potęg, czy jest overflow(bo wiem, że jest) tylko ja tu widzę dwie pętle - jedna w drugiej i jedna z nich dzieli swój argument przez 10 po każdym obiegu i moje pytanie dotyczy wyłącznie złożoności.

1

Gdbyś wczytywał num z zewnatrz to miałbys O(N) = N*log10(num) ale ze obliczasz num jako num(N)= 11^N </code>to otrzymujesz <code>O(N)=N*log10(num(N))=N*log10(11^N)~=k*N*log10(10^N)= k*N*N ~= N^2;

ed. złożonosc to N + log(num(N)) = 2*N ponieważ while odpali Ci sie =dojedzie do zera i wiecej nie ruszy.

0

topik92 dzięki.

1 użytkowników online, w tym zalogowanych: 0, gości: 1