Interview Question
Country: India
it depends on the range of R. If it's less than 10^7, we could easily preprocess prime numbers using Sieve of Eratosthenes, and then do two binary searches for finding the primes between L and R. Then, count the frequency of each digit.
If L and R could be very big numbers, we can iterate over all numbers between L and R and do Miller-Rabin Primality Test on each of them to find out whether it's a prime or not.
require "prime"
def find_highest_digit l, r
count = Array.new(10, 0)
Prime.each(r) do |prime|
if prime >= l
number_arr = prime.to_s.split('')
while !number_arr.empty?
digit = number_arr.pop
count[digit.to_i] += 1
end
end
end
if count.inject(:+) == 0
-1
else
max = 1
max_index = nil
(0..9).each do |index|
if count[index] >= max
max_index = index
max = count[index]
end
end
max_index
end
end
#include<conio.h>
#include<stdio.h>
int arr[10],w;
void isprime(int);
int main(void)
{
int a,b,i,max,no;
clrscr();
printf("enter the two no:");
scanf("%d%d",&a,&b);
for(i=a;i<=b;i++)
isprime(i);
if(w==0)
{
printf("\nNO ANY PRIME NO");
}
else
{
max=arr[0];
no=0;
for(i=1;i<=9;i++)
{
if(arr[i]>=max)
{
max=arr[i];
no=i;
}
}
printf("\nHIGHEST OCCURING DIGIT IS %d",no);
printf("\n AND NO OF TIMES IS %d",max);
}
getch();
return 0;
}
void isprime(int m)
{
int a,q;
for(a=2;a<=m/2;a++)
{
if(m%a==0)
return;
}
w=1;
while(m>0)
{
a=m%10;
m=m/10;
arr[a]+=1;
}
}
#include<conio.h>
#include<stdio.h>
int arr[10],w;
void isprime(int);
int main(void)
{
int a,b,i,max,no;
clrscr();
printf("enter the two no:");
scanf("%d%d",&a,&b);
for(i=a;i<=b;i++)
isprime(i);
if(w==0)
{
printf("\nNO ANY PRIME NO");
}
else
{
max=arr[0];
no=0;
for(i=1;i<=9;i++)
{
if(arr[i]>=max)
{
max=arr[i];
no=i;
}
}
printf("\nHIGHEST OCCURING DIGIT IS %d",no);
printf("\n AND NO OF TIMES IS %d",max);
}
getch();
return 0;
}
void isprime(int m)
{
int a,q;
for(a=2;a<=m/2;a++)
{
if(m%a==0)
return;
}
w=1;
while(m>0)
{
a=m%10;
m=m/10;
arr[a]+=1;
}
}
#include<conio.h>
#include<stdio.h>
int arr[10],w;
void isprime(int);
int main(void)
{
int a,b,i,max,no;
clrscr();
printf("enter the two no:");
scanf("%d%d",&a,&b);
for(i=a;i<=b;i++)
isprime(i);
if(w==0)
{
printf("\n-1");
}
else
{
max=arr[0];
no=0;
for(i=1;i<=9;i++)
{
if(arr[i]>=max)
{
max=arr[i];
no=i;
}
}
printf("\nHIGHEST OCCURING DIGIT IS %d",no);
printf("\n AND NO OF TIMES IS %d",max);
}
getch();
return 0;
}
void isprime(int m)
{
int a,q;
for(a=2;a<=m/2;a++)
{
if(m%a==0)
return;
}
w=1;
while(m>0)
{
a=m%10;
m=m/10;
arr[a]+=1;
}
}
It depends on the range of R. If it's less than 10^7 we could pre-process prime numbers using the Sieve of Eratosthenes. Afterwards, we need to do two binary searches to find all the prime numbers between L and R. Then we would simply count the frequency of each digit.
Also, to make it more efficient, we could calculate the cumulative sum of frequency of each digit in prime numbers. And then we need to subtract the cumulative frequency of last number out of the range [L,R] from the last number inside the range.
If R could be a large number, we need to use Miller-Rabin Primality Test on all the numbers between L and R.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int a, b, max = 0;
Console.WriteLine("2 numbers");
a = int.Parse(Console.ReadLine());
b = int.Parse(Console.ReadLine());
for (int i = a; i <= b; i++)
{
if (prime(i))
{
max = i;
}
}
Console.WriteLine(max);
Console.ReadKey();
}
static bool prime(int i)
{
for (int j = 2; j < i / 2; j++)
{
if (i % j == 0)
{
return false;
}
}
return true;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int a, b, max = 0;
Console.WriteLine("2 numbers");
a = int.Parse(Console.ReadLine());
b = int.Parse(Console.ReadLine());
for (int i = a; i <= b; i++)
{
if (prime(i))
{
max = i;
}
}
Console.WriteLine(max);
Console.ReadKey();
}
static bool prime(int i)
{
for (int j = 2; j < i / 2; j++)
{
if (i % j == 0)
{
return false;
}
}
return true;
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int a, b, max = 0;
Console.WriteLine("2 numbers");
a = int.Parse(Console.ReadLine());
b = int.Parse(Console.ReadLine());
for (int i = a; i <= b; i++)
{
if (prime(i))
{
max = i;
}
}
Console.WriteLine(max);
Console.ReadKey();
}
static bool prime(int i)
{
for (int j = 2; j < i / 2; j++)
{
if (i % j == 0)
{
return false;
}
}
return true;
}
}
}
Is my code efficient? If not, then how can i improve the time complexity?
import java.io.*;
import java.util.*;
class RangePrime{
static ArrayList<Integer> list;
public static void main(String args[]) throws Exception{
Scanner sc= new Scanner(System.in);
list= new ArrayList<Integer>();
int L=sc.nextInt();
int R=sc.nextInt();
for(int i=L;i<=R;i++)
{
if(isPrime(i)==false)
list.add(i);
}
int arr[]= new int[10];
for(int j=0;j<list.size();j++)
{
String str=Integer.toString(list.get(j));
if(str.length()<2)
{ if(str=="0")
arr[0]=arr[0]+1;
else if(str=="1") arr[1]+=1;
else if(str=="2") arr[2]+=1;
else if(str=="3") arr[3]+=1;
else if(str=="4") arr[4]+=1;
else if(str=="5") arr[5]+=1;
else if(str=="6") arr[6]+=1;
else if(str=="7") arr[7]+=1;
else if(str=="8") arr[8]+=1;
else if(str=="9") arr[9]+=1;
}
else
{
for(int i=0;i<str.length();i++)
{
if(str.contains("0")) arr[0]+=1;
else if(str.contains("1")) arr[1]+=1;
else if(str.contains("2")) arr[2]+=1;
else if(str.contains("3")) arr[3]+=1;
else if(str.contains("4")) arr[4]+=1;
else if(str.contains("5")) arr[5]+=1;
else if(str.contains("6")) arr[6]+=1;
else if(str.contains("7")) arr[7]+=1;
else if(str.contains("8")) arr[8]+=1;
else if(str.contains("9")) arr[9]+=1;
}
}
}
int max=1;
int result=0;
for(int x=0;x<arr.length;x++)
{ if(max<arr[x])
{
result=x;
max=arr[x];
}
}
System.out.println(result);
}
static boolean isPrime(int num)
{
boolean flag=false;
for(int i=2;i<=Math.sqrt(num);i++)
{
if(num%i==0)
flag=true;
}
return flag;
}
}
Is my code efficient? If not, then how can i improve the time complexity?
import java.io.*;
import java.util.*;
class RangePrime{
static ArrayList<Integer> list;
public static void main(String args[]) throws Exception{
Scanner sc= new Scanner(System.in);
list= new ArrayList<Integer>();
int L=sc.nextInt();
int R=sc.nextInt();
for(int i=L;i<=R;i++)
{
if(isPrime(i)==false)
list.add(i);
}
int arr[]= new int[10];
for(int j=0;j<list.size();j++)
{
String str=Integer.toString(list.get(j));
if(str.length()<2)
{ if(str=="0")
arr[0]=arr[0]+1;
else if(str=="1") arr[1]+=1;
else if(str=="2") arr[2]+=1;
else if(str=="3") arr[3]+=1;
else if(str=="4") arr[4]+=1;
else if(str=="5") arr[5]+=1;
else if(str=="6") arr[6]+=1;
else if(str=="7") arr[7]+=1;
else if(str=="8") arr[8]+=1;
else if(str=="9") arr[9]+=1;
}
else
{
for(int i=0;i<str.length();i++)
{
if(str.contains("0")) arr[0]+=1;
else if(str.contains("1")) arr[1]+=1;
else if(str.contains("2")) arr[2]+=1;
else if(str.contains("3")) arr[3]+=1;
else if(str.contains("4")) arr[4]+=1;
else if(str.contains("5")) arr[5]+=1;
else if(str.contains("6")) arr[6]+=1;
else if(str.contains("7")) arr[7]+=1;
else if(str.contains("8")) arr[8]+=1;
else if(str.contains("9")) arr[9]+=1;
}
}
}
int max=1;
int result=0;
for(int x=0;x<arr.length;x++)
{ if(max<arr[x])
{
result=x;
max=arr[x];
}
}
System.out.println(result);
}
static boolean isPrime(int num)
{
boolean flag=false;
for(int i=2;i<=Math.sqrt(num);i++)
{
if(num%i==0)
flag=true;
}
return flag;
}
}
#include <stdio.h>
int main()
{
int i, prime,upper,lower, n,k=0,a[30],p,s=0,j;
printf(" ENTER THE LOWER LIMIT : ");
scanf("%d", &lower);
printf("\n ENTER THE UPPER LIMIT : ");
scanf("%d", &upper);
printf("\n PRIME NUMBERS LIST IS : ");
for(n=lower+1; n<upper; n++)
{
prime = 1;
for(i=2; i<n/2; i++)
if(n%i == 0)
{
prime = 0;
break;
}
if(prime)
{
a[k]=n;
k++;
}
}
for(i=0,j=i+1;i<k;i++,j++)
{
s=a[i]+a[j]+1;
for(p=i;p<k-1;p++)
{
if(s==a[p])
{
printf("\n%d + %d +1=%d\n",a[i],a[j],a[p]);
break;
}
}
}
}
#include<conio.h> #include<stdio.h> int arr[10],w; void isprime(int); int main(void) { int a,b,i,max,no; clrscr(); printf("enter the two no:"); scanf("%d%d",&a,&b); for(i=a;i<=b;i++) isprime(i); if(w==0) { printf("\nNO ANY PRIME NO"); } else { max=arr[0]; no=0; for(i=1;i<=9;i++) { if(arr[i]>=max) { max=arr[i]; no=i; } } printf("\nHIGHEST OCCURING DIGIT IS %d",no); printf("\n AND NO OF TIMES IS %d",max); } getch(); return 0; } void isprime(int m) { int a,q; for(a=2;a<=m/2;a++) { if(m%a==0) return; } w=1; while(m>0) { a=m%10; m=m/10; arr[a]+=1; }}
- megha July 18, 2015