FANDOM


Below are a list of questions with partial or fully working code alongside.

Check if N is a Fibonacci Number Edit

Question from Hackerrank here. Basically check if given number is Fibonacci or not.

Here is a mathematical formula from here: Given a number N, fro it to be Fibonacci, either 5N2 + 4 or 5N2 - 4 has to be a perfect square. The code to check fro that is below. But there seems to be a problem with it. Check it out please.

#include<stdio.h>

#include<math.h>

#include<string.h>

int main(int argc, char *argv[])

{

   int T,i;

   long unsigned N,t1,t2;

   float t3,t4;

   FILE *fp,*fout, *f1,*f2;

   char *temp1,*temp2;

   fp = fopen("input07.txt","r");

   fout = fopen("output.txt","w");
   
   fscanf(fp,"%d",&T);

    for(i=0;i<T;i++)

   {

        fscanf(fp,"%lu",&N);

       printf("flag 1 %d\n",i);

       t4 = (5*N*N);

       t1 = t4+4;

       t2 = t4-4;

       t3 = floor(sqrt(t1));

       t4 = floor(sqrt(t2));

       printf("flag 2\n");

       if(((long unsigned)(t3*t3)==t1)||((long unsigned)(t4*t4)==t2)){

           fprintf(fout,"IsFibo\n");
       }

       else{
           fprintf(fout,"IsNotFibo\n");
       }

       printf("flag 3 %d\n",i);
   }

}

Snakes and LadderEdit

This was an easy problem on hackerrank. Given a snakes and ladder board, the objective was to find the minimum number of dice rolls needed to reach from the start till the end. 

This is a classic shortest path problem and there may be a lot of different kind of approaches to solve the question. Why I am writing about this is to illustrate the use of Floyd Warshall Algorith, Since the number of nodes in the graph is 100, we could use Floyd Warshall to find the shortest path as time limits won't be a problem now. Floyd Warshall has O(N^3) complexity and hence could be avoided in general. The good part about Floyd Warshall is the ease to write. It just take a Adjacency matrix and three for loops to find shortest path from each node to every other node. Following is the code I wrote. The problem can be found here


/*Strategy: Shortest path problem.
Start node and ending nodes are known. 
look for the shortest path. 
Create graph with adj matrix and use Floyd Warshall, since number of nodes are lesser than 100! 
It is O(N^3) but let's see how it goes. */
#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

int min(int a, int b){
    if (a<b){
        return a;
    }
    else{
        return b;
    }
}

int main(){
    int adjMat[100][100];
    int T,snakes,ladders,i,j,k;
    
    scanf("%d",&T);
    while(T--){
        //initialising the matrix which basically represents the minimum number of dice rolls needed to go from point i to j
        for(i=0;i<100;i++){
            for(j=0;j<100;j++){
                if(i==j){
                    adjMat[i][j] == 0;
                }
                if((j-i)<=6 && (j-i) > 0){
                    adjMat[i][j] = 1;
                }
                else{
                    adjMat[i][j] = INT_MAX/2;
                }
            }
        }

        //Changing values for snakes and ladders
        int temp1,temp2;
        scanf("%d,%d",&ladders,&snakes);
        while(ladders--){
            scanf("%d,%d",&temp1,&temp2);
            adjMat[temp1][temp2]=0;
        }
        while(snakes--){
            scanf("%d,%d",&temp1,&temp2);
            adjMat[temp1][temp2]=0;
        }
        
        
        /*for(i=0;i<100;i++){
            for(j=0;j<100;j++){
                printf("%d ",adjMat[i][j]);
            }
            printf("\n");
        }*/
        
        //applying Floyd Warshall
        int i,j,k;
        for(k=0;k<100;k++){
            for(j=0;j<100;j++){
                for(i=0;i<100;i++){
                    adjMat[i][j] = min(adjMat[i][j], (adjMat[i][k]+adjMat[k][j]));
                }
            }
        }
        printf("%d\n",adjMat[0][99]);
        
    }
    return 0;
}

Seive of ErastothenesEdit

One of the quickest way to find the number of primes. It is also something very common that everyone should know. The idea is simple. Take an array ranging from 2 to N, where N is the upper limit upto which you want to find the number of primes. Fill the array with all trues. Then start with 2 and mark all its multiples as false. Then start with the next number which is true and mark all it's multiples by false and so on, till sqrt(N).

Next just go through the entire array and find the number of uncrossed elements to get the answer. 


The code that can be used is as follows: 

#include<iostream>
#include<math.h>
using namespace std;


int main(){

int M,i,j;
cin >> M;

int container[M+1];

for(i=0;i<=M;i++){
    container[i]=1;
}

int P=0;

for(i=2;i<=floor(sqrt(M));i++){
if(container[i]==0) continue;
for (j=i*i;j <= M; j = j+i){
container[j]=0;
}
}

for(i=2;i<=M;i++){
if(container[i]==1){P++;}
}
cout << P << endl;  
return 0;

}