Given two integers L and R. The task is to find the count of all even numbers in the range [L, R] whose sum of digits is divisible by 3.
Examples:
Input: L = 18, R = 36
Output: 4
18, 24, 30, 36 are the only numbers in the range [18, 36] which are even and whose sum of digits is divisible by 3.
Input: L = 7, R = 11
Output: 0
There is no number in the range [7, 11] which is even and whose sum of digits is divisible by 3.
Naive approach: Initialize count = 0 and for every number in the range [L, R], check if the number is divisible by 2 and sum of its digits is divisible by 3. If yes then increment the count. Print the count in the end.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the// sum of digits of xint sumOfDigits(int x){ int sum = 0; while (x != 0) { sum += x % 10; x = x / 10; } return sum;}// Function to return the count// of required numbersint countNumbers(int l, int r){ int count = 0; for (int i = l; i <= r; i++) { // If i is divisible by 2 and // sum of digits of i is divisible by 3 if (i % 2 == 0 && sumOfDigits(i) % 3 == 0) count++; } // Return the required count return count;}// Driver codeint main(){ int l = 1000, r = 6000; cout << countNumbers(l, r); return 0;} |
Java
// Java implementation of the approach class GFG{// Function to return the // sum of digits of x static int sumOfDigits(int x) { int sum = 0; while (x != 0) { sum += x % 10; x = x / 10; } return sum; } // Function to return the count // of required numbers static int countNumbers(int l, int r) { int count = 0; for (int i = l; i <= r; i++) { // If i is divisible by 2 and // sum of digits of i is divisible by 3 if (i % 2 == 0 && sumOfDigits(i) % 3 == 0) count++; } // Return the required count return count; } // Driver code public static void main(String args[]) { int l = 1000, r = 6000; System.out.println(countNumbers(l, r)); } }// This code is contributed by Arnab Kundu |
Python3
# python implementation of the approach# Function to return the# sum of digits of xdef sumOfDigits(x): sum = 0 while x != 0: sum += x % 10 x = x//10 return sum# Function to return the count# of required numbersdef countNumbers(l, r): count = 0 for i in range(l, r + 1): # If i is divisible by 2 and # sum of digits of i is divisible by 3 if i % 2 == 0 and sumOfDigits(i) % 3 == 0: count += 1 return count# Driver codel = 1000; r = 6000print(countNumbers(l, r))# This code is contributed by Shrikant13 |
C#
// C# implementation of the approach using System;class GFG{// Function to return the // sum of digits of x static int sumOfDigits(int x) { int sum = 0; while (x != 0) { sum += x % 10; x = x / 10; } return sum; } // Function to return the count // of required numbers static int countNumbers(int l, int r) { int count = 0; for (int i = l; i <= r; i++) { // If i is divisible by 2 and // sum of digits of i is divisible by 3 if (i % 2 == 0 && sumOfDigits(i) % 3 == 0) count++; } // Return the required count return count; } // Driver code public static void Main() { int l = 1000, r = 6000; Console.WriteLine(countNumbers(l, r)); } }// This code is contributed by Code_Mech. |
PHP
<?php// PHP implementation of the approach// Function to return the sum of// digits of xfunction sumOfDigits( $x){ $sum = 0; while ($x != 0) { $sum += $x % 10; $x = $x / 10; } return $sum;}// Function to return the count// of required numbersfunction countNumbers($l, $r){ $count = 0; for ($i = $l; $i <= $r; $i++) { // If i is divisible by 2 and // sum of digits of i is divisible by 3 if ($i % 2 == 0 && sumOfDigits($i) % 3 == 0) $count++; } // Return the required count return $count;}// Driver code$l = 1000;$r = 6000;echo countNumbers($l, $r);// This code is contributed by princiraj1992?> |
Javascript
<script>// JavaScript implementation of the approach// Function to return the// sum of digits of xfunction sumOfDigits(x){ let sum = 0; while (x != 0) { sum += x % 10; x = Math.floor(x / 10); } return sum;}// Function to return the count// of required numbersfunction countNumbers(l, r){ let count = 0; for (let i = l; i <= r; i++) { // If i is divisible by 2 and // sum of digits of i is divisible by 3 if (i % 2 == 0 && sumOfDigits(i) % 3 === 0) count++; } // Return the required count return count;}// Driver code let l = 1000, r = 6000; document.write(countNumbers(l, r));// This code is contributed by Manoj.</script> |
Output:
834
Time Complexity: O(r – l), as we are traversing from l to r.
Auxiliary Space: O(1), as we are not using any extra space.
Efficient approach:
- We have to check that the number is divisible by 2.
- We have to check that the sum of digit is divisible by 3 which means that the number is divisible by 3.
So overall we have to check if a number is divisible by both 2 and 3, and since both 2 and 3 are co prime so we just have to check if a number is divisible by their product i.e. 6.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std;// Function to return the count// of required numbersint countNumbers(int l, int r){ // Count of numbers in range // which are divisible by 6 return ((r / 6) - (l - 1) / 6);}// Driver codeint main(){ int l = 1000, r = 6000; cout << countNumbers(l, r); return 0;} |
Java
// Java implementation of the approachclass GFG{// Function to return the count// of required numbersstatic int countNumbers(int l, int r){ // Count of numbers in range // which are divisible by 6 return ((r / 6) - (l - 1) / 6);}// Driver codepublic static void main(String[] args){ int l = 1000, r = 6000; System.out.println(countNumbers(l, r));}}// This code is contributed by princiraj1992 |
Python3
# Python3 implementation of the approach # Function to return the count # of required numbers def countNumbers(l, r) : # Count of numbers in range # which are divisible by 6 return ((r // 6) - (l - 1) // 6); # Driver code if __name__ == "__main__" : l = 1000; r = 6000; print(countNumbers(l, r)); # This code is contributed by Ryuga |
C#
// C# implementation of the above approach using System; class GFG{// Function to return the count// of required numbersstatic int countNumbers(int l, int r){ // Count of numbers in range // which are divisible by 6 return ((r / 6) - (l - 1) / 6);}// Driver codepublic static void Main(String[] args){ int l = 1000, r = 6000; Console.WriteLine(countNumbers(l, r));}}// This code contributed by Rajput-Ji |
PHP
<?php// PHP implementation of the approach// Function to return the count// of required numbersfunction countNumbers($l, $r){ // Count of numbers in range // which are divisible by 6 return ((int)($r / 6) - (int)(($l - 1) / 6));}// Driver code$l = 1000; $r = 6000;echo(countNumbers($l, $r));// This code is contributed // by Code_Mech.?> |
Javascript
<script>// Javascript implementation of the approach// Function to return the count// of required numbersfunction countNumbers(l, r){ // Count of numbers in range // which are divisible by 6 return (parseInt(r / 6) - parseInt((l - 1) / 6));}// Driver codevar l = 1000, r = 6000;document.write(countNumbers(l, r));</script> |
Output:
834
Time Complexity: O(1), as we are not traversing or using any loops.
Auxiliary Space: O(1), as we are not using any extra space.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
