Given a number as a string, find the number of contiguous subsequences which recursively add up to 9 - GeeksQuiz

Given a number as a string, find the number of contiguous subsequences which recursively add up to 9 - GeeksQuiz
Given a number as a string, write a function to find the number of substrings (or contiguous subsequences) of the given string which recursively add up to 9.

-- Why 9?
Numbers are divisible by 9 if the sum of all the individual digits is evenly divisible by 9.

All digits of a number recursively add up to 9, if only if the number is multiple of 9. We basically need to check for s%9 for all substrings s. One trick used in below program is to do modular arithmetic to avoid overflow for big strings.

int count9s(char number[])

{

    int count = 0; // To store result

    int n = strlen(number);

 

    // Consider every character as beginning of substring

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

    {

        int sum = number[i] - '0';  //sum of digits in current substring

 

        if (number[i] == '9') count++;

 

        // One by one choose every character as an ending character

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

        {

            // Add current digit to sum, if sum becomes multiple of 5

            // then increment count. Let us do modular arithmetic to

            // avoid overflow for big strings

            sum = (sum + number[j] - '0')%9;

 

            if (sum == 0)

               count++;

        }

    }

    return count;

}

Read full article from Given a number as a string, find the number of contiguous subsequences which recursively add up to 9 - GeeksQuiz