Header Ads Widget

Hexadecimal numbers | hackerearth solution

Rajnish Tripathi 05:30

 Problem

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

For example, �(27)=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

1≤�≤501≤�, �≤105

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 java.io.BufferedReader;
import java.io.InputStreamReader;
//import for Scanner and other utility classes
import java.util.*;
class TestClass {
public static void main(String args[] ) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
/*
//Scanner
Scanner s = new Scanner(System.in);
String name = s.nextLine(); // Reading input from STDIN
System.out.println("Hi, " + name + "."); // Writing output to STDOUT
*/
// Write your code here
int n = Integer.parseInt(br.readLine());
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++){
String[] s = br.readLine().split(" ");
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:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-


Tags:

Post a Comment

0 Comments