Рубрики

Количество подстрок, делимых на 6 в строке целых чисел

Дана строка, состоящая из целых чисел от 0 до 9. Задача состоит в том, чтобы подсчитать количество подстрок, которые при преобразовании в целое делятся на 6. Подстрока не содержит начальных нулей.

Примеры:

Input : s = "606".
Output : 5
Substrings "6", "0", "6", "60", "606"
are divisible by 6.

Input : s = "4806".
Output : 5
"0", "6", "48", "480", "4806" are 
substring which are divisible by 6.

Метод 1: (грубая сила) Идея состоит в том, чтобы найти все подстроки данной строки и проверить, делится ли подстрока на 6 или нет .
Сложность времени: O (n 2 ).

Метод 2: (Динамическое программирование) Как обсуждалось в разделе Проверка, делится ли большое число на 6 или нет . Число делится на 6, если последняя цифра делится на 2, а сумма цифр делится на 3.

Идея состоит в том, чтобы использовать динамическое программирование, которое позволяет нам быстро и эффективно вычислять ответы, отслеживая ранее вычисленные ответы и используя эти сохраненные ответы вместо пересчета значений.

Пусть f (i, m) будет количеством строк, начинающихся с индекса i, а сумма их цифр по модулю 3 (пока) равна m, а число, которое он представляет, является четным . Итак, наш ответ будет

Пусть x будет i- ой цифрой в строке. Из f (i, m) нам нужно найти все четные подстроки, которые начинаются в i + 1.
Кроме того, мы получим дополнительную подстроку, если (x + m) сама делится на 3, а x четно. Итак, мы получаем отношение повторения

// We initially pass m (sum modulo 3 so far) as 0
f(i, m) = ((x + m)%3 == 0 and x%2 == 0) + 
          f(i + 1, (m + x)%3)  // Recursive 

Запоминая состояния, мы получаем решение O (n).

Ниже приведена реализация этого подхода:

C ++

// C ++ программа для расчета количества подстрок
// делится на 6.
#include <bits/stdc++.h>
#define MAX 100002

using namespace std;

  
// Возвращаем количество подстрок, делимых на 6
// и начиная с индекса i в s [] и предыдущей сумме
// цифр по модулю 3 является m.

int f(int i, int m, char s[], int memoize[][3])

{

    // Конец строки.

    if (i == strlen(s))

        return 0;

  

    // Если уже рассчитано, вернуть

    // сохраненное значение.

    if (memoize[i][m] != -1)

        return memoize[i][m];

  

    // Преобразование в целое число.

    int x = s[i] - '0';

  

    // Увеличиваем результат на 1, если текущая цифра

    // делится на 2 и сумма цифр равна

    // делится на 3.

    // И повторить для следующего индекса с новым модулем.

    int ans = ((x+m)%3 == 0 && x%2 == 0) +

              f(i+1, (m+x)%3, s, memoize);

  

    return memoize[i][m] = ans;

}

  
// Возвращает подстроки, кратные 6.

int countDivBy6(char s[])

{

    int n = strlen(s);

  

    // Для хранения значения всех состояний.

    int memoize[n+1][3];

    memset(memoize, -1, sizeof memoize);

  

    int ans = 0;

    for (int i = 0; i < strlen(s); i++)

    {

        // Если строка содержит 0, увеличить счетчик на 1.

        if (s[i] == '0')

            ans++;

  

        // Остальное вычислить с помощью рекурсивной функции.

        // Передаем предыдущую сумму по модулю 3 как 0.

        else

            ans += f(i, 0, s, memoize);

    }

  

    return ans;

}

  
// Управляемая программа

int main()

{

    char s[] = "4806";

  

    cout << countDivBy6(s) << endl;

  

    return 0;

}

Джава

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

import java.util.*;

  

class GFG 

{

  

    static int MAX = 100002;

  

    // Возвращаем количество подстрок, делимых на 6

    // и начиная с индекса i в s [] и предыдущей сумме

    // цифр по модулю 3 является m.

    static int f(int i, int m, char s[], int memoize[][]) 

    {

        // Конец строки.

        if (i == s.length)

        {

            return 0;

        }

  

        // Если уже рассчитано, вернуть

        // сохраненное значение.

        if (memoize[i][m] != -1

        {

            return memoize[i][m];

        }

  

        // Преобразование в целое число.

        int x = s[i] - '0';

  

        // Увеличиваем результат на 1, если текущая цифра

        // делится на 2 и сумма цифр равна

        // делится на 3.

        // И повторить для следующего индекса с новым модулем.

        int ans = ((x + m) % 3 == 0 && x % 2 == 0) ? 1 + f(i + 1,

                (m + x) % 3, s, memoize) : f(i + 1, (m + x) % 3, s, memoize);

        memoize[i][m] = ans;

        return memoize[i][m];

    }

  

    // Возвращает подстроки, кратные 6.

    static int countDivBy6(char s[]) 

    {

        int n = s.length;

  

        // Для хранения значения всех состояний.

        int[][] memoize = new int[n + 1][3];

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

        {

            for (int j = 0; j < 3; j++) 

            {

                memoize[i][j] = -1;

            }

        }

  

        int ans = 0;

        for (int i = 0; i < s.length; i++) 

        {

            // Если строка содержит 0, увеличить счетчик на 1.

            if (s[i] == '0'

            {

                ans++;

            

            // Остальное вычислить с помощью рекурсивной функции.

            // Передаем предыдущую сумму по модулю 3 как 0.

            else 

            {

                ans += f(i, 0, s, memoize);

            }

        }

  

        return ans;

    }

  

    // Управляемая программа

    public static void main(String[] args) 

    {

        char s[] = "4806".toCharArray();

  

        System.out.println(countDivBy6(s));

    }

}

  
// Этот код предоставлен Rajput-Ji

python3

# Python3 программа для вычисления числа
Количество подстрок

  
# Возвращаем количество подстрок делимых
# на 6 и начиная с индекса i в s [] и
# предыдущая сумма цифр по модулю 3 равна m.

def f(i, m, s, memoize):

      

    # Конец строки.

    if (i == len(s)):

        return 0

  

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

    # сохраненное значение.

    if (memoize[i][m] != -1): 

        return memoize[i][m] 

  

    # Преобразование в целое число.

    x = ord(s[i]) - ord('0')

  

    # Увеличить результат на 1, если текущая цифра

    # делится на 2 и сумма цифр

    # делится на 3.

    # И повторить для следующего индекса с новым модулем.

    ans = (((x + m) % 3 == 0 and x % 2 == 0) +

          f(i + 1, (m + x) % 3, s, memoize)) 

  

    memoize[i][m] = ans

    return memoize[i][m]

  
# Возвращает подстроки, кратные 6.

def countDivBy6(s):

    n = len(s)

  

    # Для хранения значения всех состояний.

    memoize = [[-1] * 3 for i in range(n + 1)]

  

    ans = 0

    for i in range(len(s)):

          

        # Если строка содержит 0, приращение

        # считать на 1.

        if (s[i] == '0'):

            ans += 1

  

        # Остальное рассчитать с помощью рекурсивной функции.

        # Передайте предыдущую сумму по модулю 3 как 0.

        else:

            ans += f(i, 0, s, memoize)

  

    return ans

  
Код водителя

if __name__ == '__main__':

    s = "4806"

  

    print(countDivBy6(s))

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

C #

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

using System;

  

class GFG

{

  

    static int MAX = 100002;

  

    // Возвращаем количество подстрок, делимых на 6

    // и начиная с индекса i в s [] и предыдущей сумме

    // цифр по модулю 3 является m.

    static int f(int i, int m, char []s, int [,]memoize) 

    {

        // Конец строки.

        if (i == s.Length)

        {

            return 0;

        }

  

        // Если уже рассчитано, вернуть

        // сохраненное значение.

        if (memoize[i,m] != -1) 

        {

            return memoize[i,m];

        }

  

        // Преобразование в целое число.

        int x = s[i] - '0';

  

        // Увеличиваем результат на 1, если текущая цифра

        // делится на 2 и сумма цифр равна

        // делится на 3.

        // И повторить для следующего индекса с новым модулем.

        int ans = ((((x + m) % 3 == 0) && (x % 2 == 0)) ? 1 : 0)

                + f(i + 1, (m + x) % 3, s, memoize);

  

        return memoize[i,m] = ans;

    }

  

    // Возвращает подстроки, кратные 6.

    static int countDivBy6(char []s) 

    {

        int n = s.Length;

  

        // Для хранения значения всех состояний.

        int[,] memoize = new int[n + 1,3];

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

        {

            for (int j = 0; j < 3; j++)

            {

                memoize[i,j] = -1;

            }

        }

  

        int ans = 0;

        for (int i = 0; i < s.Length; i++)

        {

            // Если строка содержит 0, увеличить счетчик на 1.

            if (s[i] == '0'

            {

                ans++;

            

            // Остальное вычислить с помощью рекурсивной функции.

            // Передаем предыдущую сумму по модулю 3 как 0.

            else

            {

                ans += f(i, 0, s, memoize);

            }

        }

  

        return ans;

    }

  

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

    public static void Main(String[] args) 

    {

        char []s = "4806".ToCharArray();

  

        Console.WriteLine(countDivBy6(s));

    }

}

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


Выход:

5

Сложность времени: O (n).

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

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

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

Количество подстрок, делимых на 6 в строке целых чисел

0.00 (0%) 0 votes