Делимость подстроки на 11 запросов
Учитывая большое число, n (с цифрами до 10 ^ 6) и различные запросы, представленные ниже:
Запрос (l, r): найти, есть ли подстрока между индексы l и r (оба включительно) делятся на 11.
Примеры:
Ввод: n = 122164154695. Запросы: l = 0 r = 3, l = 1 r = 2, l = 5 r = 9, л = 0 г = 11 Выход: Правда Ложь Ложь Правда Объяснение: В первом запросе 1221 делится на 11 Во втором запросе 22 делится на 11 и так далее.
We know that any number is divisible by 11 if the difference between the sum of odd indexed digits and the sum of even indexed digits is divisible by 11, i.e.,
Sum(digits at odd places) – Sum(digits at even places) should be divisible by 11.
Hence, the idea is to pre-process an auxiliary array that would store the sum of digits at odd and even places.
To evaluate a query we can use the auxiliary array to answer it in O(1).
C++
// C++ program to check divisibility by 11 in // substrings of a number string #include <iostream> using namespace std; const int MAX = 1000005; // To store sums of even and odd digits struct OddEvenSums { // Sum of even placed digits int e_sum; // Sum of odd placed digits int o_sum; }; // Auxiliary array OddEvenSums sum[MAX]; // Utility function to evaluate a character"s // integer value int toInt( char x) { return int (x) - 48; } // This function receives the string representation // of the number and precomputes the sum array void preCompute(string x) { // Initialize everb sum[0].e_sum = sum[0].o_sum = 0; // Add the respective digits depending on whether // they"re even indexed or odd indexed for ( int i=0; i<x.length(); i++) { if (i%2==0) { sum[i+1].e_sum = sum[i].e_sum+toInt(x[i]); sum[i+1].o_sum = sum[i].o_sum; } else { sum[i+1].o_sum = sum[i].o_sum+toInt(x[i]); sum[i+1].e_sum = sum[i].e_sum; } } } // This function receives l and r representing // the indices and prints the required output bool query( int l, int r) { int diff = (sum[r+1].e_sum - sum[r+1].o_sum) - (sum[l].e_sum - sum[l].o_sum); return (diff%11==0); } //driver function to check the program int main() { string s = "122164154695" ; preCompute(s); cout << query(0, 3) << endl; cout << query(1, 2) << endl; cout << query(5, 9) << endl; cout << query(0, 11) << endl; return 0; } |
Java
// Java program to check divisibility by 11 in // subStrings of a number String class GFG { static int MAX = 1000005 ; // To store sums of even and odd digits static class OddEvenSums { // Sum of even placed digits int e_sum; // Sum of odd placed digits int o_sum; }; // Auxiliary array static OddEvenSums []sum = new OddEvenSums[MAX]; // Utility function to evaluate a character"s // integer value static int toInt( char x) { return x - 48 ; } // This function receives the String representation // of the number and precomputes the sum array static void preCompute(String x) { // Initialize everb sum[ 0 ].e_sum = sum[ 0 ].o_sum = 0 ; // Add the respective digits depending on whether // they"re even indexed or odd indexed for ( int i = 0 ; i < x.length(); i++) { if (i % 2 == 0 ) { sum[i + 1 ].e_sum = sum[i].e_sum + toInt(x.charAt(i)); sum[i + 1 ].o_sum = sum[i].o_sum; } else { sum[i + 1 ].o_sum = sum[i].o_sum + toInt(x.charAt(i)); sum[i + 1 ].e_sum = sum[i].e_sum; } } } // This function receives l and r representing // the indices and prints the required output static boolean query( int l, int r) { int diff = (sum[r + 1 ].e_sum - sum[r + 1 ].o_sum) - (sum[l].e_sum - sum[l].o_sum); return (diff % 11 == 0 ); } //driver function to check the program public static void main(String[] args) { for ( int i = 0 ; i < MAX; i++) { sum[i] = new OddEvenSums(); } String s = "122164154695" ; preCompute(s); System.out.println(query( 0 , 3 ) ? 1 : 0 ); System.out.println(query( 1 , 2 ) ? 1 : 0 ); System.out.println(query( 5 , 9 ) ? 1 : 0 ); System.out.println(query( 0 , 11 ) ? 1 : 0 ); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 program to check divisibility by # 11 in subStrings of a number String MAX = 1000005 # To store sums of even and odd digits class OddEvenSums: def __init__( self , e_sum, o_sum): # Sum of even placed digits self .e_sum = e_sum # Sum of odd placed digits self .o_sum = o_sum sum = [OddEvenSums( 0 , 0 ) for i in range ( MAX )] # This function receives the String # representation of the number and # precomputes the sum array def preCompute(x): # Initialize everb sum [ 0 ].e_sum = sum [ 0 ].o_sum = 0 # Add the respective digits # depending on whether # they"re even indexed or # odd indexed for i in range ( len (x)): if (i % 2 = = 0 ): sum [i + 1 ].e_sum = ( sum [i].e_sum + int (x[i])) sum [i + 1 ].o_sum = sum [i].o_sum else : sum [i + 1 ].o_sum = ( sum [i].o_sum + int (x[i])) sum [i + 1 ].e_sum = sum [i].e_sum # This function receives l and r representing # the indices and prints the required output def query(l, r): diff = (( sum [r + 1 ].e_sum - sum [r + 1 ].o_sum) - ( sum [l].e_sum - sum [l].o_sum)) if (diff % 11 = = 0 ): return True else : return False # Driver code if __name__ = = "__main__" : s = "122164154695" preCompute(s) print ( 1 if query( 0 , 3 ) else 0 ) print ( 1 if query( 1 , 2 ) else 0 ) print ( 1 if query( 5 , 9 ) else 0 ) print ( 1 if query( 0 , 11 ) else 0 ) # This code is contributed by rutvik_56 |
C#
// C# program to check // divisibility by 11 in // subStrings of a number String using System; class GFG{ static int MAX = 1000005; // To store sums of even // and odd digits public class OddEvenSums { // Sum of even placed digits public int e_sum; // Sum of odd placed digits public int o_sum; }; // Auxiliary array static OddEvenSums []sum = new OddEvenSums[MAX]; // Utility function to // evaluate a character"s // integer value static int toInt( char x) { return x - 48; } // This function receives the // String representation of the // number and precomputes the sum array static void preCompute(String x) { // Initialize everb sum[0].e_sum = sum[0].o_sum = 0; // Add the respective digits // depending on whether they"re // even indexed or odd indexed for ( int i = 0; i < x.Length; i++) { if (i % 2 == 0) { sum[i + 1].e_sum = sum[i].e_sum + toInt(x[i]); sum[i + 1].o_sum = sum[i].o_sum; } else { sum[i + 1].o_sum = sum[i].o_sum + toInt(x[i]); sum[i + 1].e_sum = sum[i].e_sum; } } } // This function receives l and r // representing the indices and // prints the required output static bool query( int l, int r) { int diff = (sum[r + 1].e_sum - sum[r + 1].o_sum) - (sum[l].e_sum - sum[l].o_sum); return (diff % 11 == 0); } // Driver function to check the program public static void Main(String[] args) { for ( int i = 0; i < MAX; i++) { sum[i] = new OddEvenSums(); } String s = "122164154695" ; preCompute(s); Console.WriteLine(query(0, 3) ? 1 : 0); Console.WriteLine(query(1, 2) ? 1 : 0); Console.WriteLine(query(5, 9) ? 1 : 0); Console.WriteLine(query(0, 11) ? 1 : 0); } } // This code is contributed by gauravrajput1 |
Выход:
1 1 0 1
Эта статья предоставлена Ашутошем Кумаром. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .