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++
#include <bits/stdc++.h>
using namespace std;
int sumOfDigits( int x)
{
int sum = 0;
while (x != 0) {
sum += x % 10;
x = x / 10;
}
return sum;
}
int countNumbers( int l, int r)
{
int count = 0;
for ( int i = l; i <= r; i++) {
if (i % 2 == 0 && sumOfDigits(i) % 3 == 0)
count++;
}
return count;
}
int main()
{
int l = 1000, r = 6000;
cout << countNumbers(l, r);
return 0;
}
|
Java
class GFG
{
static int sumOfDigits( int x)
{
int sum = 0 ;
while (x != 0 )
{
sum += x % 10 ;
x = x / 10 ;
}
return sum;
}
static int countNumbers( int l, int r)
{
int count = 0 ;
for ( int i = l; i <= r; i++)
{
if (i % 2 == 0 && sumOfDigits(i) % 3 == 0 )
count++;
}
return count;
}
public static void main(String args[])
{
int l = 1000 , r = 6000 ;
System.out.println(countNumbers(l, r));
}
}
|
Python3
def sumOfDigits(x):
sum = 0
while x ! = 0 :
sum + = x % 10
x = x / / 10
return sum
def countNumbers(l, r):
count = 0
for i in range (l, r + 1 ):
if i % 2 = = 0 and sumOfDigits(i) % 3 = = 0 :
count + = 1
return count
l = 1000 ; r = 6000
print (countNumbers(l, r))
|
C#
using System;
class GFG
{
static int sumOfDigits( int x)
{
int sum = 0;
while (x != 0)
{
sum += x % 10;
x = x / 10;
}
return sum;
}
static int countNumbers( int l, int r)
{
int count = 0;
for ( int i = l; i <= r; i++)
{
if (i % 2 == 0 && sumOfDigits(i) % 3 == 0)
count++;
}
return count;
}
public static void Main()
{
int l = 1000, r = 6000;
Console.WriteLine(countNumbers(l, r));
}
}
|
PHP
<?php
function sumOfDigits( $x )
{
$sum = 0;
while ( $x != 0)
{
$sum += $x % 10;
$x = $x / 10;
}
return $sum ;
}
function countNumbers( $l , $r )
{
$count = 0;
for ( $i = $l ; $i <= $r ; $i ++)
{
if ( $i % 2 == 0 &&
sumOfDigits( $i ) % 3 == 0)
$count ++;
}
return $count ;
}
$l = 1000;
$r = 6000;
echo countNumbers( $l , $r );
?>
|
Javascript
<script>
function sumOfDigits(x)
{
let sum = 0;
while (x != 0) {
sum += x % 10;
x = Math.floor(x / 10);
}
return sum;
}
function countNumbers(l, r)
{
let count = 0;
for (let i = l; i <= r; i++) {
if (i % 2 == 0 && sumOfDigits(i) % 3 === 0)
count++;
}
return count;
}
let l = 1000, r = 6000;
document.write(countNumbers(l, r));
</script>
|
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++
#include <bits/stdc++.h>
using namespace std;
int countNumbers( int l, int r)
{
return ((r / 6) - (l - 1) / 6);
}
int main()
{
int l = 1000, r = 6000;
cout << countNumbers(l, r);
return 0;
}
|
Java
class GFG
{
static int countNumbers( int l, int r)
{
return ((r / 6 ) - (l - 1 ) / 6 );
}
public static void main(String[] args)
{
int l = 1000 , r = 6000 ;
System.out.println(countNumbers(l, r));
}
}
|
Python3
def countNumbers(l, r) :
return ((r / / 6 ) - (l - 1 ) / / 6 );
if __name__ = = "__main__" :
l = 1000 ; r = 6000 ;
print (countNumbers(l, r));
|
C#
using System;
class GFG
{
static int countNumbers( int l, int r)
{
return ((r / 6) - (l - 1) / 6);
}
public static void Main(String[] args)
{
int l = 1000, r = 6000;
Console.WriteLine(countNumbers(l, r));
}
}
|
PHP
<?php
function countNumbers( $l , $r )
{
return ((int)( $r / 6) -
(int)(( $l - 1) / 6));
}
$l = 1000; $r = 6000;
echo (countNumbers( $l , $r ));
?>
|
Javascript
<script>
function countNumbers(l, r)
{
return (parseInt(r / 6) - parseInt((l - 1) / 6));
}
var l = 1000, r = 6000;
document.write(countNumbers(l, r));
</script>
|
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.
Contact Us