Делимость подстроки на 3 запроса

Опубликовано: 20 Января, 2022

Учитывая большое число, 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 и так далее.

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Мы знаем, что любое число делится на 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 и многому другому, см. Полный курс подготовки к собеседованию .

РЕКОМЕНДУЕМЫЕ СТАТЬИ