Nombre de nombres tel que la différence entre le nombre et la somme de ses chiffres ne soit pas inférieure à L

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Afficher la discussion

Améliorer l’article

Enregistrer l’article

J’aime l’article

Étant donné un nombre naturel N et un nombre entier Lla tâche consiste à trouver le nombre de nombres, inférieur ou égal à N, tel que la différence entre le nombre et la somme de ses chiffres ne soit pas inférieure à L.
Exemples:

Input: N = 1500, L = 30
Output: 1461

Input: N = 1546300, L = 30651
Output: 1515631

Approcher:
Notre solution dépend d’une simple observation : si un nombre, disons X, est tel que la différence entre X et sumOfDigits(X) est inférieure ou égale à L, alors X+1 est également un nombre valide. Par conséquent, nous devons trouver un minimum tel X en utilisant recherche binaire.
Mise en œuvre:

C++

#include <bits/stdc++.h>

using namespace std;

int sumOfDigits(long long n)

{

    long long sum = 0;

    while (n > 0) {

        sum += n % 10;

        n /= 10;

    }

    return sum;

}

long long countDigits(long long num, long long limit)

{

    long long left = 1, right = num, result = 0;

    

    while (left <= right) {

        long long mid = (right + left) / 2;

        

        if ((mid - sumOfDigits(mid)) >= limit) {

            

            result = num - mid + 1;

            right = mid - 1;

        }

        else {

            left = mid + 1;

        }

    }

    

    return result;

}

int main()

{

    

    long long N = 1546300, L = 30651;

    

    cout << countDigits(N, L);

    return 0;

}

Java

class GFG

{

    

    

    static long sumOfDigits( long n )

    {

        long sum = 0;

    

        while (n > 0)

        {

            sum += n % 10;

            n /= 10;

        }

    

        return sum;

    }

    

    

    static long countDigits(long num, long limit)

    {

        long left = 1, right = num, result = 0;

    

        

        while (left <= right)

        {

            long mid = (right + left) / 2;

    

            

            if ((mid - sumOfDigits(mid)) >= limit)

            {

    

                

                result = num - mid + 1;

                right = mid - 1;

            }

            else

            {

                left = mid + 1;

            }

        }

    

        

        return result;

    }

    

    

    public static void main(String []args)

    {

        

        long N = 1546300, L = 30651;

    

        

        System.out.println(countDigits(N, L));

    }

}

Python3

def sumOfDigits(n):

    sum = 0

    while (n > 0):

        sum += n % 10

        n = int(n / 10)

    return sum

def countDigits(num, limit):

    left = 1

    right = num

    result = 0

    

    while (left <= right):

        mid = int((right + left) / 2)

        

        if ((mid - sumOfDigits(mid)) >= limit):

            

            

            result = num - mid + 1

            right = mid - 1

        

        else:

            left = mid + 1

        

    

    return result

if __name__ == '__main__':

    

    

    N = 1546300

    L = 30651

    

    print(countDigits(N, L))

C#

using System;

class GFG

{

    

    

    static long sumOfDigits( long n )

    {

        long sum = 0;

    

        while (n > 0)

        {

            sum += n % 10;

            n /= 10;

        }

    

        return sum;

    }

    

    

    static long countDigits(long num, long limit)

    {

        long left = 1, right = num, result = 0;

    

        

        while (left <= right) {

    

            long mid = (right + left) / 2;

    

            

            if ((mid - sumOfDigits(mid)) >= limit)

            {

    

                

                result = num - mid + 1;

                right = mid - 1;

            }

            else

            {

    

                left = mid + 1;

            }

        }

    

        

        return result;

    }

    

    

    public static void Main()

    {

        

        long N = 1546300, L = 30651;

    

        

        Console.WriteLine(countDigits(N, L));

    }

}

PHP

<?php

    

function sumOfDigits($n)

{

    $sum = 0;

    while ($n > 0)

    {

        $sum += $n % 10;

        $n /= 10;

    }

    return $sum;

}

function countDigits($num, $limit)

{

    $left = 1;

    $right = $num;

    $result = 0;

    

    while ($left <= $right)

    {

        $mid = floor(($right + $left) / 2);

        

        if (($mid - sumOfDigits($mid)) >= $limit)

        {

            

            $result = $num - $mid + 1;

            $right = $mid - 1;

        }

        else

        {

            $left = $mid + 1;

        }

    }

    

    return $result;

}

$N = 1546300;

$L = 30651;

echo countDigits($N, $L);

?>

Javascript

<script>

    

    

    

    

    function sumOfDigits(n)

    {

        let sum = 0;

      

        while (n > 0)

        {

            sum += n % 10;

            n = parseInt(n / 10, 10);

        }

      

        return sum;

    }

      

    

    function countDigits(num, limit)

    {

        let left = 1, right = num, result = 0;

      

        

        while (left <= right) {

      

            let mid = parseInt((right + left) / 2, 10);

      

            

            if ((mid - sumOfDigits(mid)) >= limit)

            {

      

                

                result = num - mid + 1;

                right = mid - 1;

            }

            else

            {

      

                left = mid + 1;

            }

        }

      

        

        return result;

    }

    

    

    let N = 1546300, L = 30651;

    

    document.write(countDigits(N, L));

    

</script>

Complexité temporelle: O(log N)
Espace auxiliaire: O(1)

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *