Prateek Chauhan
- Jun 22, 2020
- 3 min read

TCS Codevita | Prime Fibonacci

Updated: Jul 10, 2020

In this blog, we will discuss a problem asked in TCS Codevita 2019.

Before running into the solution please do it by yourself first.

Problem Description

Given two numbers n1 and n2

Find prime numbers between n1 and n2, then
Make all possible unique combinations of numbers from the list of the prime numbers you found in step 1.
From this new list, again find all prime numbers.
Find the smallest (a) and largest (b) number from the 2nd generated list, also count of this list.
Consider the smallest and largest number as the 1st and 2nd number to generate the Fibonacci series respectively till the count (number of primes in the 2nd list).
Print the last number of a Fibonacci series as an output

Constraints

2 <= n1, n2 <= 100

n2 - n1 >= 35

Input Format

One line containing two space-separated integers n1 and n2.

Output

The last number of a generated Fibonacci series.

Timeout

Test Case

Example 1:

Input:

2 40

Output:

13158006689

Explanation:

1st prime list = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

Combination of all the primes = [23, 25, 27, 211, 213, 217, 219, 223, 229, 231, 32, 35, 37, 311, 313, 319, 323, 329, 331, 337, 52, 53, 57, 511, 513, 517, 519, 523, 529, 531, 537, 72, 73, 75, 711, 713, 717, 719, 723, 729, 731, 737, 112, 113, 115, 117, 1113, 1117, 1119, 1123, 1129, 1131, 1137, 132, 133, 135, 137, 1311, 1317, 1319, 1323, 1329, 1331, 1337, 172, 173, 175, 177, 1711, 1713, 1719, 1723, 1729, 1731, 1737, 192, 193, 195, 197, 1911, 1913, 1917, 1923, 1929, 1931, 1937, 232, 233, 235, 237, 2311, 2313, 2317, 2319, 2329, 2331, 2337, 292, 293, 295, 297, 2911, 2913, 2917, 2919, 2923, 2931, 2937, 312, 315, 317, 3111, 3113, 3117, 3119, 3123, 3129, 3137, 372, 373, 375, 377, 3711, 3713, 3717, 3719, 3723, 3729, 3731]

2nd prime list=[193, 3137, 197, 2311, 3719, 73, 137, 331, 523, 1931, 719, 337, 211, 23, 1117, 223, 1123, 229, 37, 293, 2917, 1319, 1129, 233, 173, 3119, 113, 53, 373, 311, 313, 1913, 1723, 317]

smallest (a) = 23

largest (b) = 3719

Therefore, the last number of a Fibonacci series i.e. 34th Fibonacci number in the series that has 23 and 3719 as the first 2 numbers is 13158006689

Example 2:

Input:

30 70

Output:

Explanation:

1st prime list=[31, 37, 41, 43, 47, 53, 59, 61, 67]

2nd prime list generated form combination of 1st prime list = [3137, 5953, 5347, 6761, 3761, 4337, 6737, 6131, 3767, 4759, 4153, 3167, 4159, 6143]

the smallest prime in 2nd list=3137

the largest prime in 2nd list=6761

Therefore, the last number of a Fibonacci series i.e. 14th Fibonacci number in the series that has 3137 and 6761 as the first 2 numbers is 2027041

Implementation Using C:

#include<stdio.h>
#include<math.h>
#include<limits.h>
#include<stdlib.h>
#define PRIME 1
#define NOT_PRIME 0
#define UNIQUE 1
#define NOT_UNIQUE 0

int isPrime(int);
int combine(int,int);
int isUnique(int arr[], int size, int searchVal);

int main()
{
  int n1, n2, num, countForPrimes, countForCombi,outInd,inInd,fiboCtr;
  int *primesArr=NULL,primesArrInd;
  int *combiPrimesArr = NULL, combiPrimesArrInd;
  int combiVal, smallest, greatest;
  smallest = INT_MAX;
  greatest = INT_MIN;
  long long int term1, term2, term3;
  
  scanf("%d %d",&n1, &n2);
 
  primesArrInd = 0;
  countForPrimes = (n2 - n1 + 1)/2;
  primesArr = (int*)malloc(sizeof(int)*countForPrimes);

  for(num = n1; num<=n2; num++)
  {
    if(isPrime(num) == PRIME)
      primesArr[primesArrInd++]=num;
  }
  countForCombi = (primesArrInd*(primesArrInd - 1));
  combiPrimesArr = (int *)malloc(sizeof(int)*countForCombi);
  combiPrimesArrInd = 0;
  for(outInd = 0; outInd<primesArrInd; outInd++)
  {
    for(inInd = 0; inInd < primesArrInd; inInd++)
    {
      combiVal = combine(primesArr[outInd], primesArr[inInd]);
      	if(isPrime(combiVal) == PRIME
          && isUnique(combiPrimesArr, combiPrimesArrInd, combiVal) == UNIQUE)
        {
          if(combiVal < smallest)
            smallest = combiVal;
          if(combiVal > greatest)
            greatest = combiVal;

          combiPrimesArr[combiPrimesArrInd++] = combiVal;
        }
    }
  }

  term1=smallest;
  term2=greatest;
  term3=term1+term2;
  for(fiboCtr = 3; fiboCtr<combiPrimesArrInd; fiboCtr++)
  {
    term1=term2;
    term2=term3;
    term3=term1+term2;
  }

printf("%lld",term3);
free(primesArr);
free(combiPrimesArr);
  return 0;
}

int isPrime(int num)
{
  int checkFactor, until;

  if(num == 2 ||num ==3 || num == 5) return PRIME;
  if(num <=1||num%2==0) return NOT_PRIME;
   until = sqrt(num);
   for(checkFactor=3; checkFactor <= until; checkFactor+=2)
   	if(num % checkFactor == 0) return NOT_PRIME;

   return PRIME;
}

int combine(int num1, int num2)
{
  int power = 1, toProcess;
  toProcess = num2;
  
  while(toProcess!=0)
  {
    toProcess/=10;
    power*=10;
  }
  return num1*power + num2;
}
int isUnique(int arr[], int size, int searchVal)
{
  int ind;
  for(ind = 0; ind <size; ind++)
    if(arr[ind] == searchVal)return NOT_UNIQUE;
  return UNIQUE;
}

Happy Coding!

Join us on Telegram @programmersdoor

Please write comments if you find any bug in the above code/algorithm, or find other ways to solve the same problem.

Follow Programmers Door for more.

#blog #interview #placement #learn #computer #science