Рубрики

Количество чисел, которые не содержат 3

Учитывая число n, напишите функцию, которая возвращает количество чисел от 1 до n, которые не содержат цифру 3 в их десятичном представлении.

Примеры:

Input: n = 10
Output: 9 

Input: n = 45
Output: 31 
// Numbers 3, 13, 23, 30, 31, 32, 33, 34, 
// 35, 36, 37, 38, 39, 43 contain digit 3. 

Input: n = 578
Output: 385

Мы настоятельно рекомендуем вам нажать здесь и попрактиковаться, прежде чем переходить к решению.

Решение:
Мы можем решить это рекурсивно. Пусть count (n) будет функцией, которая считает такие числа.

'msd' --> the most significant digit in n 
'd'   --> number of digits in n.

count(n) = n if n < 3

count(n) = n - 1 if 3 <= n  10 and msd is not 3

count(n) = count( msd * (10^(d-1)) - 1) 
           if n > 10 and msd is 3
Let us understand the solution with n = 578. 
count(578) = 4*count(99) + 4 + count(78)
The middle term 4 is added to include numbers 
100, 200, 400 and 500.

Let us take n = 35 as another example.  
count(35) = count (3*10 - 1) = count(29)

C ++

#include <bits/stdc++.h>

using namespace std;

  
/ * возвращает количество чисел, которые
в диапазоне от 1 до n и не содержит 3
как цифра * /

int count(int n) 

    // Базовые случаи (при условии, что n не отрицательно)

    if (n < 3) 

        return n; 

    if (n >= 3 && n < 10) 

        return n-1; 

  

    // Рассчитать 10 ^ (d-1) (10 поднять до степени d-1), где d

    // количество цифр в n. ро будет 100 для n = 578

    int po = 1; 

    while (n/po > 9) 

        po = po*10; 

  

    // найти самую значимую цифру (msd 5 для 578)

    int msd = n/po; 

  

    if (msd != 3) 

        // Для 578 всего будет 4 * count (10 ^ 2 - 1) + 4 + count (78)

        return count(msd)*count(po - 1) + count(msd) + count(n%po); 

    else

        // Для 35 сумма будет равна count (29)

        return count(msd*po - 1); 

  
// Код драйвера

int main() 

    cout << count(578) << " "

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

#include <stdio.h>

  
/ * возвращает количество чисел, которые находятся в диапазоне от 1 до n и не содержат 3

   как цифра * /

int count(int n)

{

    // Базовые случаи (при условии, что n не отрицательно)

    if (n < 3)

        return n;

    if (n >= 3 && n < 10)

       return n-1;

  

    // Рассчитать 10 ^ (d-1) (10 поднять до степени d-1), где d

    // количество цифр в n. ро будет 100 для n = 578

    int po = 1;

    while (n/po > 9)

        po = po*10;

  

    // найти самую значимую цифру (msd 5 для 578)

    int msd = n/po;

  

    if (msd != 3)

      // Для 578 всего будет 4 * count (10 ^ 2 - 1) + 4 + count (78)

      return count(msd)*count(po - 1) + count(msd) + count(n%po);

    else

      // Для 35 сумма будет равна count (29)

      return count(msd*po - 1);

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    printf ("%d ", count(578));

    return 0;

}

Джава

// Java-программа для подсчета чисел, которые не содержат 3

import java.io.*;

  

class GFG 

{

    // Функция, которая возвращает количество чисел, которые

    // находятся в диапазоне от 1 до n

    // и не содержать 3 в виде цифры

    static int count(int n)

    {

        // Базовые случаи (при условии, что n не отрицательно)

        if (n < 3)

            return n;

        if (n >= 3 && n < 10)

            return n-1;

   

        // Рассчитать 10 ^ (d-1) (10 поднять до степени d-1), где d

        // количество цифр в n. ро будет 100 для n = 578

        int po = 1;

        while (n/po > 9)

            po = po*10;

   

        // найти самую значимую цифру (msd 5 для 578)

        int msd = n/po;

   

        if (msd != 3)

            // Для 578 всего будет 4 * count (10 ^ 2 - 1) + 4 + count (78)

            return count(msd)*count(po - 1) + count(msd) + count(n%po);

        else

            // Для 35 сумма будет равна count (29)

            return count(msd*po - 1);

    }

      

    // Драйвер программы

    public static void main (String[] args) 

    {

        int n = 578;

        System.out.println(count(n));

    }

}

  
// Предоставлено Прамод Кумар

питон

# Программа Python для подсчета чисел до n, которые не содержат 3

  
# Возвращает количество чисел в диапазоне от 1 до n
# и не содержать 3 в виде цифры

def count(n):

      

    # Базовые случаи (n не отрицательно)

    if n < 3:

        return n

    elif n >= 3 and n < 10:

        return n-1

          

    # Рассчитать 10 ^ (d-1) (10 поднять до степени d-1), где d

    # количество цифр в n. ро будет 100 для n = 578

      

    po = 1

    while n/po > 9:

        po = po * 10

      

    # Найти MSD (MSD 5 для 578)

    msd = n/po

      

    if msd != 3:

        # Для 578 всего будет 4 * count (10 ^ 2 - 1) + 4 + ccount (78)

        return count(msd) * count(po-1) + count(msd) + count(n%po)

    else:

        # Для 35 всего будет равно кол (29)

        return count(msd * po - 1)

          
# Драйверная программа

n = 578

print count(n)

  
# Предоставлено Харшитом Агравалом

C #

// C # программа для подсчета чисел, которые не
// содержат 3

using System;

  

class GFG {

      

    // Функция, которая возвращает количество

    // числа в диапазоне от

    // 1 к n и не содержит 3 как

    // цифра

    static int count(int n)

    {

          

        // Базовые случаи (при условии, что n

        // не отрицательно)

        if (n < 3)

            return n;

        if (n >= 3 && n < 10)

            return n-1;

  

        // Рассчитать 10 ^ (d-1) (10 рейз

        // к степени d-1) где d

        // количество цифр в n. По воле

        // быть 100 для n = 578

        int po = 1;

          

        while (n / po > 9)

            po = po * 10;

  

        // найти наиболее значимый

        // цифра (MSD 5 для 578)

        int msd = n / po;

  

        if (msd != 3)

          

            // Для 578 всего будет

            // 4 * count (10 ^ 2 - 1) + 4 +

            // count (78)

            return count(msd) * count(po - 1) 

                + count(msd) + count(n % po);

        else

          

            // Для 35 сумма будет равна

            // считать (29)

            return count(msd * po - 1);

    }

      

    // Драйвер программы

    public static void Main () 

    {

        int n = 578;

          

        Console.Write(count(n));

    }

}

  
// Этот код предоставлен Sam007.

PHP

<?php
/ * возвращает количество чисел в диапазоне
от 1 до n и не содержат 3 в качестве цифры * /

function count1($n)

{

      

    // Базовые случаи (при условии, что n не отрицательно)

    if ($n < 3)

        return $n;

    if ($n >= 3 && $n < 10)

        return $n-1;

  

    // Рассчитать 10 ^ (д-1) (10 поднять до

    // мощность d-1) где d - количество цифр

    // гостиница. ро будет 100 для n = 578

    $po = 1;

    for($x = intval($n/$po); $x > 9; $x = intval($n/$po))

        $po = $po*10;

  

    // найти самую значимую цифру (msd 5 для 578)

    $msd = intval($n / $po);

  

    if ($msd != 3)

      

    // Для 578 всего будет 4 * count (10 ^ 2 - 1)

    // + 4 + count (78)

    return count1($msd) * count1($po - 1) +

                count1($msd) + count1($n%$po);

    else

      

    // Для 35 сумма будет равна count (29)

    return count1($msd*$po - 1);

}

  
// Программа драйвера для проверки вышеуказанной функции

    echo count1(578);

  
// Этот код предоставлен mits.
?>


Выход:

385

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Количество чисел, которые не содержат 3

0.00 (0%) 0 votes