Рубрики

Задав число в виде строки, найдите количество смежных подпоследовательностей, которые рекурсивно складываются в 9

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

Например цифры 729 рекурсивно добавить к 9,
7 + 2 + 9 = 18
Рекурс на 18
1 + 8 = 9

Примеры:

 
Input: 4189
Output: 3
There are three substrings which recursively add to 9.
The substrings are 18, 9 and 189.

Input: 999
Output: 6
There are 6 substrings which recursively add to 9.
9, 99, 999, 9, 99, 9

Все цифры числа рекурсивно складываются до 9, если только если число кратно 9. Нам в основном нужно проверять s% 9 для всех подстрок s. Один из приемов, используемых в приведенной ниже программе, заключается в создании модульной арифметики, чтобы избежать переполнения для больших строк.

Ниже приводится простая реализация, основанная на этом подходе. Реализация предполагает отсутствие начальных 0 во входном номере.

C ++

// C ++ программа для подсчета подстрок с рекурсивной суммой, равной 9
#include <iostream>
#include <cstring>

using namespace std;

  

int count9s(char number[])

{

    int count = 0; // Для сохранения результата

    int n = strlen(number);

  

    // Рассматривать каждый символ как начало подстроки

    for (int i = 0; i < n; i++)

    {

        int sum = number[i] - '0'// сумма цифр в текущей подстроке

  

        if (number[i] == '9') count++;

  

        // Один за другим выбираем каждый символ как конечный

        for (int j = i+1; j < n; j++)

        {

            // Добавить текущую цифру к сумме, если сумма становится кратной 5

            // затем увеличить счетчик. Давайте сделаем модульную арифметику для

            // избежать переполнения для больших строк

            sum = (sum + number[j] - '0')%9;

  

            if (sum == 0)

               count++;

        }

    }

    return count;

}

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

int main()

{

    cout << count9s("4189") << endl;

    cout << count9s("1809");

    return 0;

}

Джава

// Java-программа для подсчета
// подстроки с
// рекурсивная сумма, равная 9

import java.io.*;

  

class GFG

{

static int count9s(String number)

{

    // Для сохранения результата

    int count = 0

    int n = number.length();

  

    // Рассмотрим каждый символ

    // как начало подстроки

    for (int i = 0; i < n; i++)

    {

        // сумма цифр в

        // текущая подстрока

        int sum = number.charAt(i) - '0'

  

        if (number.charAt(i) == '9'

            count++;

  

        // один за другим выбираем

        // каждый символ как

        // конечный символ

        for (int j = i + 1;

                 j < n; j++)

        {

            // Добавить текущую цифру в

            // сумма, если сумма становится

            // кратно 5 тогда

            // увеличение количества Позволять

            // мы делаем модульную арифметику

            // чтобы избежать переполнения для

            // большие строки

            sum = (sum +

                   number.charAt(j) - 

                            '0') % 9;

  

            if (sum == 0)

            count++;

        }

    }

    return count;

}

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

public static void main (String[] args) 

{

    System.out.println(count9s("4189"));

    System.out.println(count9s("1809"));

}
}

  
// Этот код добавлен
// от anuj_67.

Python 3

# Python 3 программа для подсчета подстрок
# с рекурсивной суммой, равной 9

  

def count9s(number):

  

    count = 0 # Сохранить результат

    n = len(number)

  

    # Рассмотрим каждый символ как

    # начало подстроки

    for i in range(n):

          

        # сумма цифр в текущей подстроке

        sum = ord(number[i]) - ord('0')     

  

        if (number[i] == '9'):

            count += 1

  

        # Один за другим выбирайте каждого персонажа

        # как конечный символ

        for j in range(i + 1, n):

          

            # Добавить текущую цифру в сумму, если

            # сумма становится кратной 5 тогда

            # количество приращений. Давайте делать

            # модульная арифметика, чтобы избежать

            # переполнение для больших строк

            sum = (sum + ord(number[j]) - 

                         ord('0')) % 9

  

            if (sum == 0):

                count += 1

    return count

  
Код водителя

if __name__ == "__main__":

      

    print(count9s("4189"))

    print(count9s("1809"))

  
# Этот код предоставлен ita_c

C #

// C # программа для подсчета
// подстроки с
// рекурсивная сумма, равная 9

using System;

class GFG

{

static int count9s(String number)

{

    // Для сохранения результата

    int count = 0; 

    int n = number.Length;

  

    // Рассмотрим каждый символ

    // как начало подстроки

    for (int i = 0; i < n; i++)

    {

        // сумма цифр в

        // текущая подстрока

        int sum = number[i] - '0'

  

        if (number[i] == '9'

            count++;

  

        // один за другим выбираем

        // каждый символ как

        // конечный символ

        for (int j = i + 1;

                 j < n; j++)

        {

            // Добавить текущую цифру в

            // сумма, если сумма становится

            // кратно 5 тогда

            // увеличение количества Позволять

            // мы делаем модульную арифметику

            // чтобы избежать переполнения для

            // большие строки

            sum = (sum + number[j] - 

                           '0') % 9;

  

            if (sum == 0)

            count++;

        }

    }

    return count;

}

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

public static void Main () 

{

    Console.WriteLine(count9s("4189"));

    Console.WriteLine(count9s("1809"));

}
}

  
// Этот код добавлен
// от anuj_67.

PHP

<?php
// PHP программа для подсчета подстрок
// с рекурсивной суммой, равной 9

  

function count9s($number)

{

    // Для сохранения результата

    $count = 0; 

    $n = strlen($number);

  

    // Рассмотрим каждый символ как

    // начало подстроки

    for ($i = 0; $i < $n; $i++)

    {

        // сумма цифр в

        // текущая подстрока

        $sum = $number[$i] - '0'

  

        if ($number[$i] == '9') $count++;

  

        // один за другим выбираем каждого персонажа

        // как конечный символ

        for ($j = $i + 1; $j < $n; $j++)

        {

              

            // Добавить текущую цифру в сумму,

            // если сумма становится кратной 5

            // затем увеличить счетчик. Разрешите нам

            // делаем модульную арифметику для

            // избежать переполнения для больших строк

            $sum = ($sum + $number[$j] - '0') % 9;

  

            if ($sum == 0)

            $count++;

        }

    }

    return $count;

}

  

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

    echo count9s("4189"),"\n";

    echo count9s("1809");

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


Выход:

3
5

Временная сложность вышеуказанной программы составляет O (n 2 ). Пожалуйста, дайте мне знать, если есть лучшее решение.

Задав число в виде строки, найдите количество смежных подпоследовательностей, которые рекурсивно складываются до 9 | Набор 2

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

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

Задав число в виде строки, найдите количество смежных подпоследовательностей, которые рекурсивно складываются в 9

0.00 (0%) 0 votes