TNQT Digital 2 Coding Question

general
,
21

The question mentioned… Two consecutive prime numbers whose difference is 6. Wasted much time to implement this. Also thanks to shitty compiler.
Then I looked on the test cases and realized as per sample test case, it doesn’t require to be consecutive primes… Like ( 7,13)… Then I found the pattern. But it was too late.

22

According to this pattern
I have to check every time that ( 6n+1 and 6n+7 ) or ( 6n-1 and 6n+5) are prime or not.
I think there will be TLE if i check all these for prime in range 10^9

23

Remember that box at the start which had “Debugger”, “Close Debugger”, “Move”, etc. and you had to click on “Move” till it went to one side of the screen?
If you press “Debugger” on that, eclipse opens and you can provide manual input in it. I didn’t know this in the Ninja NQT too! They never mentioned it. I thought it was something related to the test software.

24

That was for Manually Input.:roll_eyes:
I didn’t use that i thought my test window will be closed if i use that. :face_with_hand_over_mouth:
So you used Eclipse for writing your code?

1 Like
25

constraints were till 10^9
sieve shld timeout too
i guess test cases were weak as some solved it using sieve

26

you could do it in O(n) linear loop time, without using sieve, by usage of number theory. However, I would like to ask, if anyone could shade any light on how the repeated generation of the indentation error problem that was arising in the provided python ide in tcs digital was solved

27

Main thing was to observe the pattern just.
**Manual checking without sieve also passed!!!**:rofl::rofl:

#include < iostream>
using namespace std;


bool isPrime(int n){
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
 

    if (n % 2 == 0 || n % 3 == 0)
        return false;
 
    for (int i = 5; i * i <= n; i = i + 6){
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    
    return true;
}



int main(){
  
  int m = 2;
  int n = 40;
  
  for(int i=m;i<=n-6;i++){
      if(isPrime(i) && isPrime(i+6)){
          cout<<i<<" "<<i+6<<endl;
          
      }
  }
  

}
28

I am sure this is unsolvable.

I also get 6/7 anyway.

30

No it can be solvable…fully see u can’t make array of length 10^9 but yaa u can make vector of that size.

31

By using this √n/6 complexity method u get full marks??

32

Tell us …how to implement that sab ye hi kah rhe h ki pattern h ya I see there is a pattern but how will u implement that… Pls explain.

1 Like
33

Show me the code…

1 Like
34

here is a better approach according to me.
step 1.store all prime number from l to r in vector vec
step 2.lets suppose its size is len
step 3.
for(int i=0;i<len-1;i++)
{
for(int j=i+1;j<len;j++)
{
if(vec[j]-vec[i]==6)
{
cout<<vec[i]<<vec[j]<<endl;
break;
}
else if(vec[j]-vec[i]>6)
break;
}
//control reaches here if break is reached.
}

35

Same here, I also get 6/7 test case.

36

I also used the Sieve method for the range of 10^7 and passed all test cases in java.
I think there is compiler issue with other languages because i don’t know anyone who has solved this in any other language except java.

1 Like
37
38

How did you store all the prime numbers from L to R?
What algorithm?

39

Same here afaik…
// 20 char

40

What was your test centre?
// 20 char

41

Mene nhi diya NQT…