Find number of integers that can be obtained by replacing ? in given string for perfect divisibility by 9
Given a String S of length N. S contains βXβ at some places. Then your task is to output the number distinct of integers that can be formed by replacing βXβ from the range [0, 9] and the formed integer leaves the remainder 0 after dividing them by 9.
Note: Numbers with leading 0s are not allowed to form.
Examples:
Input: N = 2, S = XX
Output: 10
Explanation: There can be 10 possible integers, If we use the digits from the range [0, 9] at both places of X. The 10 numbers will be: {18, 27, 36, 45, 54, 63, 72, 81, 90, 99}. They all leave remainder 0 when dividing by 9.Input: N = 2, S = 9X
Output: 2
Explanation: It can be verified that there will be only two possible such integers. Which are 90 and 99.
Approach: Implement the idea below to solve the problem
The problem is observation based. Let us observe it.
There are 3 cases to observe the problem:
- Case 1: If sum of all digit characters is divisible by 9. Then:
- Example 1: 2X7X (Count of X = 2)
- Possible Integers = 2070, 2079, 2178, 2277, 2376, 2475, 2574, 2673, 2772, 2871, 2970, 2979
- Total: 12
- Example 2: 2X7 (Count of X = 1)
- Possible integers = 207 and 297
- Total Possibilities = 2
- Then the count of such integers is: (Count(βXβ)-1) 1βs followed by 2.
- Case 2: If sum of all digit characters is not divisible by 9
- Example 1: 2X5X (Count of X = 2)
- Possible Integers = 2052, 2151, 2250, 2259, 2358, 2457, 2556, 2655, 2754, 2853, 2952
- Total: 11
- Example 2: 2X5 (Count of X = 1)
- Possible Integers = 225
- Total possibilities = 1
- Then the count of such possible integers is: (Count(βXβ)) 1s.
- Case 3: If first character of string is βXβ
- Please note that there canβt be leading 0s.
- Example 1: X27X (Count of X = 2)
- Possible Integers = 1278, 2277, 3276, 4275, 5274, 6273, 7272, 8271, 9270, 9279
- Total Possibilities = 10
- Example 2: X5X (Count of X = 2)
- Possible Integers = 153, 252, 351, 450, 459, 558, 657, 756, 855, 954
- Total possibilities = 10
- Then the count of such possible integers is: 1 then followed by (Count(βXβ) β 1) 0βs.
Step-by-step approach:
- Create two variables let say sum and q to store the sum of integers in s and count of X respectively.
- Run a loop on S and count X and calculate Sum
- If (First Character is X)
- Output 1 then (q-1) times 0s
- If (Sum is divisible by 9)
- Output 1 q times
- Else
- Output 1 q-2 times and then 2 once.
Below is the implementation of the above approach:
C++
#include <iostream> #include <string> using namespace std; // Method to output the number of such integers void Count_integers( int N, const string& S) { // sum = To count the sum of integers except X // q = Count of X int sum = 0, q = 0; // Loop for initializing value of Q and Sum for ( int i = 0; i < N; i++) { if (S[i] == 'X' ) q++; else { sum += (S[i] - '0' ); } } // Printing count of integers // according to discussed patterns if (S[0] == 'X' ) { cout << "1" ; for ( int i = 1; i < q; i++) cout << "0" ; } else if (sum % 9 != 0) { for ( int i = 0; i < q; i++) cout << "1" ; } else { for ( int i = 0; i < q - 1; i++) cout << "1" ; cout << "2" ; } } // Driver Function int main() { // Inputs int N = 4; string S = "XX90" ; // Function call Count_integers(N, S); return 0; } |
Java
// Java code to implement the approach import java.util.*; // Driver Class public class GFG { // Driver Function public static void main(String[] args) { // Inputs int N = 4 ; String S = "XX90"; // Function call Count_integers(N, S); } // Method to output the number of such integers public static void Count_integers( int N, String S) { // sum = To count the sum of integers except X // q = Count of X int sum = 0 , q = 0 ; // Loop for initializing value of Q and Sum for ( int i = 0 ; i < N; i++) { if (S.charAt(i) == 'X' ) q++; else { sum += (S.charAt(i) - '0' ); } } // Printing count of integers // according to discussed patterns if (S.charAt( 0 ) == 'X' ) { System.out.print(" 1 "); for ( int i = 1 ; i < q; i++) System.out.print(" 0 "); } else if (sum % 9 != 0 ) { for ( int i = 0 ; i < q; i++) System.out.print(" 1 "); } else { for ( int i = 0 ; i < q - 1 ; i++) System.out.print(" 1 "); System.out.print(" 2 "); } } } |
Python3
# Python code for the above approach # Method to output the number of such integers def Count_integers(N, S): # sum = To count the sum of integers except X # q = Count of X sum , q = 0 , 0 # Loop for initializing value of Q and Sum for i in range (N): if (S[i] = = 'X' ): q + = 1 else : sum + = ord (S[i]) # Printing count of integers # according to discussed patterns if (S[ 0 ] = = 'X' ): print ( "1" , end = "") for i in range ( 1 , q): print ( "0" , end = "") elif ( sum % 9 ! = 0 ): for i in range (q): print ( "1" , end = "") else : for i in range (q - 1 ): print ( "1" , end = "") print ( "2" ) # Driver function def main(): # Inputs N = 4 S = "XX90" # Function call Count_integers(N, S) # Driver call if __name__ = = '__main__' : main() # This code is contributed by ragul21 |
C#
using System; // Driver Class class GFG { // Driver Function static void Main( string [] args) { // Inputs int N = 4; string S = "XX90" ; // Function call CountIntegers(N, S); } // Method to output the number of such integers static void CountIntegers( int N, string S) { // sum = To count the sum of integers except X // q = Count of X int sum = 0, q = 0; // Loop for initializing value of Q and Sum for ( int i = 0; i < N; i++) { if (S[i] == 'X' ) q++; else { sum += (S[i] - '0' ); } } // Printing count of integers // according to discussed patterns if (S[0] == 'X' ) { Console.Write( "1" ); for ( int i = 1; i < q; i++) Console.Write( "0" ); } else if (sum % 9 != 0) { for ( int i = 0; i < q; i++) Console.Write( "1" ); } else { for ( int i = 0; i < q - 1; i++) Console.Write( "1" ); Console.Write( "2" ); } } } |
Javascript
// JS Implementation // Method to output the number of such integers function countIntegers(N, S) { // sum = To count the sum of integers except X // q = Count of X let sum = 0, q = 0; // Loop for initializing value of Q and Sum for (let i = 0; i < N; i++) { if (S[i] === 'X' ) { q++; } else { sum += parseInt(S[i]); // Convert character to integer and add to sum } } // Printing count of integers according to discussed patterns if (S[0] === 'X' ) { process.stdout.write( "1" ); for (let i = 1; i < q; i++) { process.stdout.write( "0" ); } } else if (sum % 9 !== 0) { for (let i = 0; i < q; i++) { process.stdout.write( "1" ); } } else { for (let i = 0; i < q - 1; i++) { process.stdout.write( "1" ); } process.stdout.write( "2" ); } } // Driver Function // Inputs const N = 4; const S = "XX90" ; // Function call countIntegers(N, S); // This code is contributed by Sakshi |
10
Time Complexity: O(N)
Auxiliary Space: O(1)