# Count of different numbers divisible by 3 that can be obtained by changing at most one digit

Given a string **str[]** number **N, **the task is to calculate the number of ways to make the given number divisible by 3 by changing at most one digit of the number.

**Examples:**

Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the **Essential Maths for CP Course** at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

Input:str[] = “23”Output:7Explanation:Below are the numbers that can be made from the string which are divisible by 3 – 03, 21, 24, 27, 33, 63, 93

1.Change 2 to 0 (0+3)=3 divisible by 3

2.Change 3 to 1 (2+1)=3 divisible by 3

3 change 3 to 4 (2+4)=6 divisible by 3

4 change 2 to 3 sum is 6 divisible by 3

Similarly there are total 7 number of ways to make the given number divisible by 3

Input:str[] = “235”Output:9

**Approach: **The idea is very simple to solve this problem. Calculate the sum of digits of a given number and then for each index, remove that digit and try all possible digits from **0** to **9** and see if the sum is divisible by **3** or not. Follow the steps below to solve the problem:

- Initialize the variable
**sum**as**0**to store the sum of digits of the number. - Iterate over a range
**[0, N]**using the variable**i**and perform the following steps:- Add the value of digit at
**i-th**index in the variable**sum.**

- Add the value of digit at
- Initialize the variable
**count**as**0**to store the answer. - Iterate over a range
**[0, N]**using the variable**i**and perform the following steps:- Initialize the variable
**remaining_sum**as**sum-(number.charAt(i)-48).** - Iterate over a range
**[0, 9]**using the variable**j**and perform the following steps:- Add the value of
**j**to the variable**remaining_sum**and if**remaining_sum**is divisible by**3**and**j**is not equal to the digit at**i-th**index, then add the value of**count**by**1.**

- Add the value of

- Initialize the variable
- After performing the above steps, print the value of
**count**as the answer.

Below is the implementation of the above approach..

## C++

`// C++ program fo the above approach` `#include<bits/stdc++.h>` `using` `namespace` `std;` ` ` `// Function to count the number of` ` ` `// possible numbers divisible by 3` ` ` `void` `findCount(string number)` ` ` `{` ` ` `// Calculate the sum` ` ` `int` `sum = 0;` ` ` `for` `(` `int` `i = 0; i < number.length(); ++i) {` ` ` `sum += number[i] - 48;` ` ` `}` ` ` `// Store the answer` ` ` `int` `count = 0;` ` ` `// Iterate over the range` ` ` `for` `(` `int` `i = 0; i < number.length(); ++i) {` ` ` `// Decreasing the sum` ` ` `int` `remaining_sum` ` ` `= sum - (number[i] - 48);` ` ` `// Iterate over the range` ` ` `for` `(` `int` `j = 0; j <= 9; ++j) {` ` ` `// Checking if the new sum` ` ` `// is divisible by 3 or not` ` ` `if` `((remaining_sum + j) % 3 == 0` ` ` `&& j != number[i] - 48) {` ` ` `// If yes increment` ` ` `// the value of the count` ` ` `++count;` ` ` `}` ` ` `}` ` ` `}` ` ` `cout<<count;` ` ` `}` ` ` `// Driver Code` ` ` `int` `main()` ` ` `{` ` ` `// Given number` ` ` `string number = ` `"235"` `;` ` ` `findCount(number);` ` ` `}` `// This code is contributed by ipg2016107.` |

## Java

`// Java program fo the above approach` `import` `java.io.*;` `import` `java.util.*;` `class` `GFG {` ` ` `// Function to count the number of` ` ` `// possible numbers divisible by 3` ` ` `public` `static` `void` `findCount(String number)` ` ` `{` ` ` `// Calculate the sum` ` ` `int` `sum = ` `0` `;` ` ` `for` `(` `int` `i = ` `0` `; i < number.length(); ++i) {` ` ` `sum += number.charAt(i) - ` `48` `;` ` ` `}` ` ` `// Store the answer` ` ` `int` `count = ` `0` `;` ` ` `// Iterate over the range` ` ` `for` `(` `int` `i = ` `0` `; i < number.length(); ++i) {` ` ` `// Decreasing the sum` ` ` `int` `remaining_sum` ` ` `= sum - (number.charAt(i) - ` `48` `);` ` ` `// Iterate over the range` ` ` `for` `(` `int` `j = ` `0` `; j <= ` `9` `; ++j) {` ` ` `// Checking if the new sum` ` ` `// is divisible by 3 or not` ` ` `if` `((remaining_sum + j) % ` `3` `== ` `0` ` ` `&& j != number.charAt(i) - ` `48` `) {` ` ` `// If yes increment` ` ` `// the value of the count` ` ` `++count;` ` ` `}` ` ` `}` ` ` `}` ` ` `System.out.println(count);` ` ` `}` ` ` `// Driver Code` ` ` `public` `static` `void` `main(String[] args)` ` ` `{` ` ` `// Given number` ` ` `String number = ` `"235"` `;` ` ` `findCount(number);` ` ` `}` `}` |

## Python3

`# Python program fo the above approach` `# Function to count the number of` `# possible numbers divisible by 3` `def` `findCount(number):` ` ` ` ` `# Calculate the sum` ` ` `sum` `=` `0` ` ` `for` `i ` `in` `range` `(` `len` `(number)):` ` ` `sum` `+` `=` `int` `(number[i]) ` `-` `48` ` ` `# Store the answer` ` ` `count ` `=` `0` ` ` `# Iterate over the range` ` ` `for` `i ` `in` `range` `(` `len` `(number)):` ` ` ` ` `# Decreasing the sum` ` ` `remaining_sum ` `=` `sum` `-` `(` `int` `(number[i]) ` `-` `48` `)` ` ` `# Iterate over the range` ` ` `for` `j ` `in` `range` `(` `10` `):` ` ` ` ` `# Checking if the new sum` ` ` `# is divisible by 3 or not` ` ` `if` `((remaining_sum ` `+` `j) ` `%` `3` `=` `=` `0` `and` `j !` `=` `int` `(number[i]) ` `-` `48` `):` ` ` ` ` `# If yes increment` ` ` `# the value of the count` ` ` `count ` `+` `=` `1` ` ` `print` `(count)` `# Driver Code` `# Given number` `number ` `=` `"235"` `findCount(number)` `# This code is contributed by gfgking.` |

## C#

`// C# program fo the above approach` `using` `System;` `using` `System.Collections.Generic;` `class` `GFG{` ` ` `// Function to count the number of` `// possible numbers divisible by 3` `static` `void` `findCount(` `string` `number)` `{` ` ` ` ` `// Calculate the sum` ` ` `int` `sum = 0;` ` ` `for` `(` `int` `i = 0; i < number.Length; ++i)` ` ` `{` ` ` `sum += (` `int` `)number[i] - 48;` ` ` `}` ` ` ` ` `// Store the answer` ` ` `int` `count = 0;` ` ` ` ` `// Iterate over the range` ` ` `for` `(` `int` `i = 0; i < number.Length; ++i)` ` ` `{` ` ` ` ` `// Decreasing the sum` ` ` `int` `remaining_sum = sum - ((` `int` `)number[i] - 48);` ` ` ` ` `// Iterate over the range` ` ` `for` `(` `int` `j = 0; j <= 9; ++j)` ` ` `{` ` ` ` ` `// Checking if the new sum` ` ` `// is divisible by 3 or not` ` ` `if` `((remaining_sum + j) % 3 == 0 &&` ` ` `j != number[i] - 48)` ` ` `{` ` ` ` ` `// If yes increment` ` ` `// the value of the count` ` ` `++count;` ` ` `}` ` ` `}` ` ` `}` ` ` `Console.Write(count);` `}` `// Driver Code` `public` `static` `void` `Main()` `{` ` ` ` ` `// Given number` ` ` `string` `number = ` `"235"` `;` ` ` ` ` `findCount(number);` `}` `}` `// This code is contributed by SURENDRA_GANGWAR` |

## Javascript

`<script>` `// Javascript program fo the above approach` `// Function to count the number of` `// possible numbers divisible by 3` `function` `findCount(number) {` ` ` `// Calculate the sum` ` ` `let sum = 0;` ` ` `for` `(let i = 0; i < number.length; ++i) {` ` ` `sum += number[i] - 48;` ` ` `}` ` ` `// Store the answer` ` ` `let count = 0;` ` ` `// Iterate over the range` ` ` `for` `(let i = 0; i < number.length; ++i) {` ` ` `// Decreasing the sum` ` ` `let remaining_sum = sum - (number[i] - 48);` ` ` `// Iterate over the range` ` ` `for` `(let j = 0; j <= 9; ++j) {` ` ` `// Checking if the new sum` ` ` `// is divisible by 3 or not` ` ` `if` `((remaining_sum + j) % 3 == 0 && j != number[i] - 48) {` ` ` `// If yes increment` ` ` `// the value of the count` ` ` `++count;` ` ` `}` ` ` `}` ` ` `}` ` ` `document.write(count);` `}` `// Driver Code` `// Given number` `let number = ` `"235"` `;` `findCount(number);` `// This code is contributed by gfgking` `</script>` |

**Output**

9

**Time Complexity:** O(N)**Auxiliary Space:** O(1)