Optimisation O(n) pour l'Égalité des Chiffres Finaux
IntuitionAu lieu de simuler naïvement chaque opération, qui conduirait à une complexité en O(n²) pour des chaînes de longueur pouvant atteindre 10⁵, on remarque
# Intuition
Au lieu de simuler naïvement chaque opération, qui conduirait à une complexité en O(n²) pour des chaînes de longueur pouvant atteindre 10⁵, on remarque que l'opération est linéaire (modulo 10). Ainsi, les deux chiffres finaux peuvent être exprimés comme des sommes pondérées des chiffres initiaux, où les coefficients sont les binomiaux de la ligne correspondante de Pascal.

# Approach
L'idée est de reformuler le problème en calculant directement les deux chiffres finaux. après avoir effectué (L–2) opérations (pour une chaîne de longueur L), on peut montrer que :

Le premier chiffre final est une somme pondérée des premiers L–1 chiffres de la chaîne avec des coefficients binomiaux.
Le second chiffre final est une somme pondérée des derniers L–1 chiffres, décalée d'une position.
La difficulté réside dans le calcul des coefficients binomiaux modulo 10. Puisque 10 n'est pas premier, il n'est pas possible d'utiliser directement une inversion modulaire pour la division. Pour contourner ce problème, on décompose chaque coefficient en :

Une partie résiduelle « copremière » avec 10.
Les puissances de 2 et 5 qui forment le 10.
Ainsi, pour chaque coefficient, si on possède à la fois un facteur 2 et un facteur 5, le coefficient est nul modulo 10. Sinon, on calcule la contribution modulo 10 en combinant la partie copremière et le facteur 2 ou 5 restant. Ce calcul est effectué en une boucle linéaire, garantissant une optimisation suffisante pour traiter des cas de grande taille.

# Complexity
- Time complexity:
Chaque coefficient est calculé en une seule itération sur la chaîne (avec n = L – 2), et les opérations à l’intérieur de la boucle se font en temps constant.

- Space complexity:
L’algorithme utilise un nombre constant de variables supplémentaires (en dehors de la chaîne d’entrée).

# Code
```java []
class Solution {
    public boolean hasSameDigits(String s) {
        int L = s.length();

        int n = L - 2;
        int A = 0, B = 0;

        int res = 1;
        int cnt2 = 0;
        int cnt5 = 0;
        

        for (int j = 0; j <= n; j++) {

            int cVal;
            if (cnt2 > 0 && cnt5 > 0) {
                cVal = 0;
            } else if (cnt2 > 0) {
                cVal = (int) ( (long) res * pow2(cnt2) % 10 );
            } else if (cnt5 > 0) {

                cVal = (int) ( (long) res * 5 % 10 );
            } else {
                cVal = res % 10;
            }
            

            int digitA = s.charAt(j) - '0';
            int digitB = s.charAt(j+1) - '0';
            A = (A + cVal * digitA) % 10;
            B = (B + cVal * digitB) % 10;
            

            if (j < n) {

                int numerator = n - j;
                int denominator = j + 1;
                

                int num2 = 0, num5 = 0;
                int tmp = numerator;
                while (tmp % 2 == 0) { num2++; tmp /= 2; }
                while (tmp % 5 == 0) { num5++; tmp /= 5; }
                int numCoprime = tmp % 10;
                

                int den2 = 0, den5 = 0;
                tmp = denominator;
                while (tmp % 2 == 0) { den2++; tmp /= 2; }
                while (tmp % 5 == 0) { den5++; tmp /= 5; }
                int denCoprime = tmp % 10;
                

                res = (res * numCoprime) % 10;
                cnt2 += num2;
                cnt5 += num5;
                

                int inv = modInv(denCoprime);
                res = (res * inv) % 10;
                cnt2 -= den2;
                cnt5 -= den5;

            }
        }
        return A == B;
    }
    

    private int pow2(int exp) {
        if(exp == 0) return 1;
        switch(exp % 4) {
            case 1: return 2;
            case 2: return 4;
            case 3: return 8;
            default: return 6;
        }
    }
    

    private int modInv(int x) {
        switch(x) {
            case 1: return 1;
            case 3: return 7;
            case 7: return 3;
            case 9: return 9;
            default: return 1;
        }
    }
    

    public static void main(String[] args) {
        Solution sol = new Solution();

        System.out.println("s = \"3902\" -> " + sol.hasSameDigits("3902"));
        System.out.println("s = \"34789\" -> " + sol.hasSameDigits("34789"));
        

        String s = "8511091174243970293830342753059959793455377893239051540927082033187240124651229102505421365397729731740624985976268193161909092667482162609105851918329325410229303096145203285966520320429119384446770055324289454442954597630606378451482361366896910776550615973749924980365499549511704675725195663107728081029608575109725399732672058587256993726863276501858883662007362560815246884096259020234496053459165914113397087333641562001970404358712101566463126129305760602714410261720198595772192756949994361450529207454149673035573098830421831309194263544594007550188801321953486900418288916392541385847578758551708294616501456816524717438312058500300288868953422115931462276486885913112671552112754119767267621269560618674030131754128856353720751335308105588014754553778617501267029280240423832512177715508236759500474945035840428596745739268598933476010552810416514316060195958059404368153600344223160971369308987776658691971723970769376180896862840723518439341935614206767582388604235193637092402433663668727253863972978514229601582421448166527144131253387154395775592358019590680702190704499241496925111130194219795706800345173303260442653604447578003347631943913218385257512925060165807340873922438201432922853019264090389581305644965200572122806139177551973435419645514198562152315885392561597057958489927226094303976667008461440816384107700958082762054062862978877164156340331810298614797596471444329253938876072843770795718420670993562025309405464921097647102127112753047141132213852170185177941108947208851591877874428506536720569272960446163857345970157074777262657467919343799385582135456166613132027220067090289431721832069601432323573404866372353541042870928620955868755334424571763936184484330974970756512179803681363021075184601757687640941008917712631764272527828638442519961130805821109137312058154056088794778667809778520891462897389040931374831253566950261285451732547782440546368493373827016874592373107472040883380959501216070238219495029145308865413087337192076688648645267137352032821663013782324960261680805708481713272384569339945696255637747022170099488797844015341942650394639976630537358294896083644891306864428090342753841957230297332886715097445715870047132909598527580066721731847355525276473254280573636687108825582815472218447930101385552289625287402143639205489747896990810626817492093426862879930237761595807688491386266037305034155993242960325800766341555409447456085209442690249493319595974410499461472889992743304042638661402936492751134153618438719122659779278593454345562856939161533956406664062082948502192616188359181424778685153097822238878650684606450186365367824787969956896239686299711473952543244454407437972621019129858045855802669740924346562271755789922776852966015983373223984515681628996744657357266074345956404557430495922634049229408654918041656688799879520877100522487922957705935017704071417671856380551133496181712641524172716734775879858208226434051731656057563966349762268670773167064345059714223679637100751184692572787651829263323319095148243753853280906286968525848051465210590600256007080343223858268670720042068419494674887376834277991448904219871084565845566765609281789755289059876005460861951378749415901441459192337407041165444863382494204852095924440945180423738602946245407515741984712673149515067375321667553297489332356750942403610336886254800514132765055130423896419669598451107787594693528731655017976186383968755105230110421192185775629168145593057911559376473844619261209489258070880197188964305822209497843893720207883604806732462355187403570140697897014178540619928507223798723141945207998863064388718759430755734127925254545618782725641065676253642825199669088788157091153054087652424968346143752354760700188475028543129035231781427786570123258459465262727961004609483163242709460058271249800801401170601368826025839065359868446587778315774995596977318361459374351686542010357910338611548104543410042691137071879894419360441632041055110202794163";
        System.out.println("Cas long -> " + sol.hasSameDigits(s));
    }
}
```
['Java']