Hexadecimal numbers

 Problem:-

You are given a range 

[L, R]

. You are required to find the number of integers 

X

 in the range such that 

GCD(X,F(X))>1

 where 

F(X)

 is equal to the sum of digits of 

X

 in its hexadecimal (or base 16) representation.

For example, 

F(27)=1+B=1+11=12

 (

27

 in hexadecimal is written as 

1B

). You are aksed 

T

 such questions. 

Input format

  • The first line contains a positive integer 
    T

     denoting the number of questions that you are asked.

  • Each of the next 
    T

     lines contain two integers 

    L

     and 

    R

     denoting the range of questions.

Output Format

For each test case, you are required to print exactly 

T

 numbers as the output. 

Constraints

1T501L, R105

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:-

#include<bits/stdc++.h>
using namespace std;

// function for calculate gcd
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;
}

//Driver function
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;
            // lopgic for calculate Hexadecimal number
            while(x!=0)
            {
                int r=x%16;
                x=x/16;
                sum=sum+r;
            }
            int f=gcd(i,sum);
            // if gcd greater than 1 than return 0
            if(f==0)
             ans++;
        }
        cout<<ans<<endl;
    }
}



Leave a Reply

Your email address will not be published.