Mastercard, Recently asked On-Campus Question in IIT-B, October 2022 | Consecutive Composite Integers

Question

Question 1 198 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 192 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

Akshay Sharma · Answer

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 &lt;&lt; ((lastnum + firstnum) * count) / 2;

Akshay Sharma · Answer

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 &lt;= n; i++)
    prime[i] = true;

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

int count = 0;

for (int i = l; i &lt;= r; i++)
{
    if (prime[i] == true)
    {
        if (count &gt;= K)
            cout &lt;&lt; (i - count) &lt;&lt; " " &lt;&lt; i - 1 &lt;&lt; " " &lt;&lt; count &lt;&lt; "
";
        count = 0;
    }
    else
        count++;
}

if (count &gt;= K)
    cout &lt;&lt; (r - count) &lt;&lt; " " &lt;&lt; r &lt;&lt; " " &lt;&lt; count &lt;&lt; "
";

Question: Mastercard, Recently asked On-Campus Question in IIT-B, October 2022 | Consecutive Composite Integers

Question 1

Consecutive Composite Integers

Question 2

include <bits/stdc++.h>