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

31.12.2019Математика, Строки

Дана строка, состоящая из целых чисел от 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: (Динамическое программирование) Как обсуждалось в разделе Проверка, делится ли большое число на 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 * /

Выход:

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

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

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

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

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

0.00 (0%) 0 votes