Рубрики

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

Учитывая число в виде строки, напишите функцию, чтобы найти количество подстрок (или смежных подпоследовательностей) данной строки, которые рекурсивно складываются до 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: 909
Output: 5
There are 5 substrings which recursively add 
to nine, 9, 90, 909, 09, 9

Эта статья о оптимизированном решении проблемы, указанной ниже статьи:
Задав число в виде строки, найдите количество смежных подпоследовательностей, которые рекурсивно складываются до 9 | Установите 1 .

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

Алгоритм:

Initialize an array d of size 10 with 0
d[0]<-1
Initialize mod_sum = 0, continuous_zero = 0
for every character
    if character == '0';
        continuous_zero++
    else
        continuous_zero=0
    compute mod_sum
    update result += d[mod_sum]
    update d[mod_sum]++
    subtract those cases from result which have only 0s

Объяснение:
Если сумма цифр от индекса i до j складывается до 9, то сумма (от 0 до i-1) = сумма (от 0 до j) (мод 9).
Мы просто должны удалить случаи, которые содержат только нули. Мы можем сделать это, запомнив no. непрерывных нулей до этого символа (число этих случаев заканчивается на этом индексе) и вычитая их из результата.

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

C ++

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

using namespace std;

  

int count9s(char number[])

{

    int n = strlen(number);

  

    // хранить номер предыдущих встречных модульных сумм

    int d[9];

    memset(d, 0, sizeof(d));

  

    // нет модульной суммы (== 0) встречается до сих пор = 1

    d[0] = 1;

    int result = 0;

  

    int mod_sum = 0, continuous_zero = 0;

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

        if (!int(number[i] - '0')) // если число равно 0, увеличить

            continuous_zero++;     // нет из непрерывной_ нулевой на 1

        else                       // в противном случае значение zero_zero равно 0

            continuous_zero=0;

        mod_sum += int(number[i] - '0');

        mod_sum %= 9;

        result+=d[mod_sum];

        d[mod_sum]++;      // увеличиваем значение d этого mod_sum

                          // вычитаем нет. случаев, когда есть

                          // в подстроке только нули

        result -= continuous_zero;

    }

    return result;

}

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

int main()

{

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

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

    cout << count9s("4189");

    return 0;

}
// Этот код предоставлен Гулаб Арора

Джава

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

  

class GFG {

  

    static int count9s(char number[]) {

        int n = number.length;

  

        // хранить номер предыдущих встречных модульных сумм

        int d[] = new int[9];

  

        // нет модульной суммы (== 0) встречается до сих пор = 1

        d[0] = 1;

        int result = 0;

  

        int mod_sum = 0, continuous_zero = 0;

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

            if ((number[i] - '0') == 0) // если число равно 0, увеличить

            {

                continuous_zero++;     // нет из непрерывной_ нулевой на 1

            } else // в противном случае значение zero_zero равно 0

            {

                continuous_zero = 0;

            }

            mod_sum += (number[i] - '0');

            mod_sum %= 9;

            result += d[mod_sum];

            d[mod_sum]++;  // увеличиваем значение d этого mod_sum

                          // вычитаем нет. случаев, когда есть

                          // в подстроке только нули

            result -= continuous_zero;

        }

        return result;

    }

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

    public static void main(String[] args) {

        System.out.println(count9s("01809".toCharArray()));

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

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

    }

}
// Этот код предоставлен 29AjayKumar

python3

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

  

def count9s(number):

    n = len(number)

  

    # хранить нет. из предыдущих встреченных

    # модульные суммы

    d = [0 for i in range(9)]

  

    № № встретившейся модульной суммы (== 0)

    # до сих пор = 1

    d[0] = 1

    result = 0

  

    mod_sum = 0

    continuous_zero = 0

    for i in range(n): 

          

        # если число равно 0, увеличить

        if (ord(number[i]) - ord('0') == 0): 

            continuous_zero += 1 № № из непрерывной_ нулевой на 1

        else:

            continuous_zero = 0 # иначе Continuous_zero равно 0

              

        mod_sum += ord(number[i]) - ord('0')

        mod_sum %= 9

        result += d[mod_sum]

        d[mod_sum] += 1     # увеличить значение d этого мода

                         # вычесть нет. случаев, когда есть

                         # только нули в подстроке

        result -= continuous_zero

  

    return result

  
Код водителя

if __name__ == '__main__':

    print(count9s("01809"))

    print(count9s("1809"))

    print(count9s("4189"))

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

C #

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

   

using System;

  

class GFG {

   

    static int count9s(string number) {

        int n = number.Length;

   

        // хранить номер предыдущих встречных модульных сумм

        int[] d = new int[9];

   

        // нет модульной суммы (== 0) встречается до сих пор = 1

        d[0] = 1;

        int result = 0;

   

        int mod_sum = 0, continuous_zero = 0;

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

            if ((number[i] - '0') == 0) // если число равно 0, увеличить

            {

                continuous_zero++;     // нет из непрерывной_ нулевой на 1

            } else // в противном случае значение zero_zero равно 0

            {

                continuous_zero = 0;

            }

            mod_sum += (number[i] - '0');

            mod_sum %= 9;

            result += d[mod_sum];

            d[mod_sum]++;  // увеличиваем значение d этого mod_sum

                          // вычитаем нет. случаев, когда есть

                          // в подстроке только нули

            result -= continuous_zero;

        }

        return result;

    }

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

    public static void Main() {

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

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

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

    }

}


Выход:

8
5
3

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

Эта статья предоставлена Гулаб Арора . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

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

0.00 (0%) 0 votes