Problem

You are given a range . You are required to find the number of integers $�$ in the range such that $���\left(�,�\left(�\right)\right)>1$ where $�\left(�\right)$ is equal to the sum of digits of $�$ in its hexadecimal (or base 16) representation.

For example, $�\left(27\right)=1+�=1+11=12$ ($27$ in hexadecimal is written as $1�$). You are aksed $�$ such questions.

Input format

• The first line contains a positive integer $�$ denoting the number of questions that you are asked.
• Each of the next $�$ lines contain two integers $�$ and $�$ denoting the range of questions.

Output Format

For each test case, you are required to print exactly $�$ numbers as the output.

Constraints

Sample Input
3
1 3
5 8
7 12
Sample Output
2
4
6
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

For the first test-case, numbers which satisfy the criteria specified are : 2,3. Hence, the answer is 2.

For the second test-case, numbers which satisfy the criteria specified are : 5,6,7 and 8. Hence the answer is 4.

For the third test-case, numbers which satisfy the criteria specified are : 7,8,9,10,11 and 12. Hence the answer is 6.

Code(C++):-

#include<bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
int n=a>b?b:a;
for(int i=n;i>1;i--)
{
if(a%i==0 && b%i==0)
return 0;
}
return 1;
}
int main()
{
int t,l,r;
cin>>t;
while(t--)
{
cin>>l>>r;
int ans=0;
for(int i=l;i<=r;i++)
{
int x=i;
int sum=0;
while(x!=0)
{
int r=x%16;
x=x/16;
sum=sum+r;
}
int f=gcd(i,sum);
if(f==0)
ans++;
}
cout<<ans<<endl;
}
}

Code(JAVA):-

//import for Scanner and other utility classes
import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
/*
//Scanner
Scanner s = new Scanner(System.in);
String name = s.nextLine(); // Reading input from STDIN
System.out.println("Hi, " + name + "."); // Writing output to STDOUT
*/
int[] L = new int[n];
int[] R = new int[n];
int smallest = Integer.MAX_VALUE;
int largest = Integer.MIN_VALUE;
for(int i=0; i<n; i++){
L[i] = Integer.parseInt(s[0]);
smallest = Math.min(smallest, L[i]);
R[i] = Integer.parseInt(s[1]);
largest = Math.max(largest, R[i]);
}
int[] calc = new int[largest-smallest+2];
calc[0] = 0;
int temp = 0;
for(int i=1; i<=largest-smallest+1; i++){
if(GCD(i+smallest-1, getF(i+smallest-1)) > 1) temp = 1;
else temp = 0;
calc[i] = temp + calc[i-1];
}
for(int i=0; i<n; i++){
System.out.println(calc[R[i]-smallest+1] - calc[L[i]-smallest]);
}
}
public static int getF(int x){
int res = 0;
while(x>0){
res += x%16;
x = x/16;
}
return res;
}
public static int GCD(int a, int b){
if(a%b==0) return b;
else return GCD(b, a%b);
}
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-
iMocha coding Questions:-
Tech Mahindra coding questions:-
Unthinkable Solutions coding questions:-