Делимость подстроки на 3 запроса
Учитывая большое число, n (число цифр до 10 ^ 6) и различные запросы формы:
Запрос (l, r): найдите, делится ли подстрока между индексами l и r (оба включительно) на 3.
Примеры:
Ввод: n = 12468236544. Запросы: л = 0 г = 1 л = 1 г = 2 л = 3 г = 6 л = 0 г = 10 Выход: Делится на 3 Делится на 3 Не делится на 3 Делится на 3 Объяснение: В первом запросе 12 делится на 3 Во втором запросе 24 делится на 3 и так далее.
Мы знаем, что любое число делится на 3, если сумма его цифр делится на 3. Следовательно, идея состоит в предварительной обработке вспомогательного массива, который будет хранить сумму цифр.
Математически, сумма [0] = 0 а также для i от 0 до количества цифр числа: sum [i + 1] = sum [i] + toInt (n [i]) где toInt (n [i]) представляет собой целочисленное значение i-й цифры числа n
Once our auxiliary array is processed, we can answer each query in O(1) time, because the substring from indices l to r would be divisible by 3 only if, (sum[r+1]-sum[l])%3 == 0
Below is a the implementation program for the same.
C++
// C++ program to answer multiple queries of // divisibility by 3 in substrings of a number #include <iostream> using namespace std; // Array to store the sum of digits int sum[1000005]; // Utility function to evaluate a character"s // integer value int toInt( char x) { return int (x) - "0" ; } // This function receives the string representation // of the number and precomputes the sum array void prepareSum(string s) { sum[0] = 0; for ( int i=0; i<s.length(); i++) sum[i+1] = sum[i] + toInt(s[i]); } // This function receives l and r representing // the indices and prints the required output void query( int l, int r) { if ((sum[r+1]-sum[l])%3 == 0) cout << "Divisible by 3
" ; else cout << "Not divisible by 3
" ; } // Driver function to check the program int main() { string n = "12468236544" ; prepareSum(n); query(0, 1); query(1, 2); query(3, 6); query(0, 10); return 0; } |
Java
// Java program to answer multiple queries of // divisibility by 3 in substrings of a number class GFG { // Array to store the sum of digits static int sum[] = new int [ 1000005 ]; // Utility function to evaluate a character"s // integer value static int toInt( char x) { return x - "0" ; } // This function receives the string representation // of the number and precomputes the sum array static void prepareSum(String s) { sum[ 0 ] = 0 ; for ( int i = 0 ; i < s.length(); i++) { sum[i + 1 ] = sum[i] + toInt(s.charAt(i)); } } // This function receives l and r representing // the indices and prints the required output static void query( int l, int r) { if ((sum[r + 1 ] - sum[l]) % 3 == 0 ) { System.out.println( "Divisible by 3" ); } else { System.out.println( "Not divisible by 3" ); } } // Driver code public static void main(String[] args) { String n = "12468236544" ; prepareSum(n); query( 0 , 1 ); query( 1 , 2 ); query( 3 , 6 ); query( 0 , 10 ); } } // This code has been contributed by 29AjayKumar |
Python3
# Python3 program to answer multiple queries of # divisibility by 3 in substrings of a number # Array to store the sum of digits sum = [ 0 for i in range ( 1000005 )] # Utility function to evaluate a character"s # integer value def toInt(x): return int (x) # This function receives the string representation # of the number and precomputes the sum array def prepareSum(s): sum [ 0 ] = 0 for i in range ( 0 , len (s)): sum [i + 1 ] = sum [i] + toInt(s[i]) # This function receives l and r representing # the indices and prs the required output def query(l, r): if (( sum [r + 1 ] - sum [l]) % 3 = = 0 ): print ( "Divisible by 3" ) else : print ( "Not divisible by 3" ) # Driver function to check the program if __name__ = = "__main__" : n = "12468236544" prepareSum(n) query( 0 , 1 ) query( 1 , 2 ) query( 3 , 6 ) query( 0 , 10 ) # This code is contributed by # Sanjit_Prasad |
C#
// C# program to answer multiple queries of // divisibility by 3 in substrings of a number using System; class GFG { // Array to store the sum of digits static int []sum = new int [1000005]; // Utility function to evaluate a character"s // integer value static int toInt( char x) { return x - "0" ; } // This function receives the string representation // of the number and precomputes the sum array static void prepareSum(String s) { sum[0] = 0; for ( int i = 0; i < s.Length; i++) { sum[i + 1] = sum[i] + toInt(s[i]); } } // This function receives l and r representing // the indices and prints the required output static void query( int l, int r) { if ((sum[r + 1] - sum[l]) % 3 == 0) { Console.WriteLine( "Divisible by 3" ); } else { Console.WriteLine( "Not divisible by 3" ); } } // Driver code public static void Main() { String n = "12468236544" ; prepareSum(n); query(0, 1); query(1, 2); query(3, 6); query(0, 10); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // JavaScript program to answer multiple queries of // divisibility by 3 in substrings of a number // Array to store the sum of digits let sum = []; // Utility function to evaluate a character"s // integer value function toInt(x) { return x - "0"; } // This function receives the string representation // of the number and precomputes the sum array function prepareSum(s) { sum[0] = 0; for (let i = 0; i < s.length; i++) { sum[i + 1] = sum[i] + toInt(s[i]); } } // This function receives l and r representing // the indices and prints the required output function query(l, r) { if ((sum[r + 1] - sum[l]) % 3 == 0) { document.write( "Divisible by 3" + "<br />" ); } else { document.write( "Not divisible by 3" + "<br />" ); } } // Driver Code let n = "12468236544" ; prepareSum(n); query(0, 1); query(1, 2); query(3, 6); query(0, 10); </script> |
Выход:
Делится на 3 Делится на 3 Не делится на 3 Делится на 3
Эта статья предоставлена Ашутошем Кумаром. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.
Вниманию читателя! Не прекращайте учиться сейчас. Получите все важные математические концепции для соревновательного программирования с курсом Essential Maths for CP по доступной для студентов цене. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .