6 weeks ago

John 930

Hyderabad

Question 1

Consecutive Composite Integers

Given a range [L, R] and an integer K, find all the groups in the given range having at least K consecutive composite integers.

Example:

Input:

L = 500, R = 650, K = 10

Output:

510   520   11
524   540   17
620   630   11

Explanation:

Prime number between 500 to 650 are {503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647}.

So between them the consecutive composite number which are greater than K are 510-520, 524-540 and 620-630.

Input:

L = 10, R = 18, K = 2

Output:

14 16 3

Question 2

Given n and a number, the task is to find the sum of n digit numbers that are divisible by given number.

Examples:

Input:

n = 2, number = 7

Output:

728

There are thirteen n digit numbers that are divisible by 7.

Numbers are : 14+ 21 + 28 + 35 + 42 + 49 + 56 + 63 +70 + 77 + 84 + 91 + 98.

Input:

n = 3, number = 7

Output:

70336

Input:

n = 3, number = 4

Output :

124200

12 months ago

Akshay Sharma 1000

Chandigarh

Question 2

Naive Approach

• Naive approach could be traversal through all N numbers and for each number check the divisibility and calculate the sum.
• But the time Complexity of this approach could be very bad that is something like (10^N) In this question, we are not given constraints So it gets passed for the N when its range from 0-8 So we have to come up with the better solution.

Efficient Approach

• In this approach, we are basically using some maths to compute the solution for the given problem that is we can count the total number divisible by a given number. After that applying formula for sum_of_ap will give us the correct solution.

• Below is the equation that we are going to use to compute the answer where count is the total number divisible by N :

  count/2  * (first-term + last-term)
  

• We can get the first term and last term using pow(10, Number) and pow(10, Number-1).

• After that knowing the first number that is divisible by the given digit X is something like: firstnum = (firstnum - firstnum % X)+X
• Then we apply our formula for calculating the sum and print the answer.
• Time Complexity : 0(N) for pow() function

Pseudo Code

 int firstnum = pow(10, digit - 1);
 int lastnum = pow(10, digit);
 firstnum = (firstnum - firstnum % X) + X;
 lastnum = (lastnum - lastnum % X);
 int count = ((lastnum - firstnum) / X + 1);
 cout << ((lastnum + firstnum) * count) / 2;

12 months ago

Akshay Sharma 1000

Chandigarh

Question 1

Brute Force

• A simple solution would be to traverse all numbers in a given range and:
• Check if each number is prime or not.
• Keep a count of consecutive composite numbers.
• Print the group range with its count if the value exceeds K.
• But this solution required too much time Complexity that is O((R-L)*√R) but we can come up with a better solution that this so below is the optimized approach.

Optimized Approach

• Instead of finding all the consecutive composite numbers, we can use the Alternate Hypothesis to find prime numbers in a given range and solve the problem efficiently.
• We can generate the prime numbers between the range and after generating the prime numbers array, traverse the array.
• And Check if the consecutive composite numbers exceed more than 10 or not
• Time Complexity : O(R*log(log(R)))

Pseudo Code

 int n = r;
bool prime[n + 1] = {false};
for (int i = 0; i <= n; i++)
    prime[i] = true;

for (int p = 2; p * p <= n; p++)
{
    if (prime[p] == true)
    {
        for (int i = p * p; i <= n; i += p)
            prime[i] = false;
    }
}

int count = 0;

for (int i = l; i <= r; i++)
{
    if (prime[i] == true)
    {
        if (count >= K)
            cout << (i - count) << " " << i - 1 << " " << count << "\n";
        count = 0;
    }
    else
        count++;
}

if (count >= K)
    cout << (r - count) << " " << r << " " << count << "\n";