Thursday, 18 December 2014

Determining the number of square integers (perfect squares) between any given range.

/*Square integer is a integer which is a perfect square of any integer. In this , I have tried this with 2 possible solutions*/

1st solution (brute force method):-

#include<stdio.h>
#include<math.h>
int main(){
    int n;
    long t,a,b;
    int i,count=0;
    printf("Enter number of test cases\n");//number of ranges
    scanf("%d",&n);
    while(n>0){
        count=0;
        scanf("%d%d",&a,&b);
        for(i=a;i<=b;i++){
            t=sqrt(i);/*function to determine square root of any given number;*/
           
            if(t*t==i)/*checking if this particular number is perfect square*/

            count++;
           
        }
        n--;
    printf("%d\n",count);
    }
}

2nd solution (one of the best(optimized way) to determine if number is perfect square or not):-

#include<stdio.h>
#include<math.h>
int main(){
    int n,a,b;
    int count=0;
    printf("Enter number of test cases\n");//number of ranges
    scanf("%d",&n);
    while(n>0){
        scanf("%d%d",&a,&b);
        count=floor(sqrt(b))-ceil(sqrt(a))+1;/*optimized way to calculate all perfect squares b/w a &&b;*/
 
        printf("%d\n",count);
        n--;
    }

o/p:-
Enter number of test cases
2
3 9
2 /*between 3 and 9 (inclusive) only 2 numbers are perfect squares--4 and 9*/

17 24
0

Tuesday, 16 December 2014

To print every pass of an insertion sort (ready to run) in c

/* First let me tell you some basic about insertion sort (for those who wants to refresh there concepts). Its a sorting technique which have a time complexity in worst case as O(n*n) an best case is O(n);*/
/*also i did not utilize the argument of printArr() ,which can be utilized for displaying and knowing the pass number*/
#include<stdio.h>
#include<math.h>
int n,arr[10];
//function to print the elements in the array
void printArr(int a){
    int j;
    for(j=0;j<n;j++)
    printf(" %d",arr[j]);
}

int main(){
    int i,j,k;
    printf("Enter number of elements");
    scanf("%d",&n);
//taking input
    for(i=0;i<n;i++){
        printf("Enter element %d",i+1);
        scanf("%d",&arr[i]);
       }

printArr(0);//simply print input array
//doing the insertion sort and displaying every pass result
for(i=0;i<n;i++){
        k=arr[i];
        j=i-1;
        while(j>=0&&k<arr[j]){
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=k;
        printf("\n");
        printArr(i+1);
    }
return 0;
}

Monday, 29 September 2014

Program to determine if given number is fibonacci or not..fully functional

C program to determine if the number is fibonacci number or not?

/*first let me tell you , a fibonacci number is a number of the form

*fibonacci(n)=fibonacci(n-1)+fibonacci(n-2);
*i.e. nth fibonacci number is sum of n-1 and (n-2)th fibonacci number given that
*fibonacci(0)=0 ,and
*fibonacci(1)=1;

*following is the program to help u with*/

#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
uint64_t fib(uint64_t);//u can take long long int
int check_fib(uint64_t);
uint64_t fibon[10000000];//array to store fibonacci number calculated

int main(){
uint64_t i;
long t,j;
uint64_t *a;
fibon[1]=1;
           //taking the number of test cases
       scanf("%ld",&t);
       //allocating that much element array
    a=calloc(t,sizeof(uint64_t));
       for(j=0;j<t;j++){
                        scanf("%llu",&a[j]);
       }
       for(j=0;j<t;j++){
    i=a[j];
       check_fib(i);
       printf("\n");
       }
       return 0 ;
       }

uint64_t fib(uint64_t n){
uint64_t l;
    if(n==0||n==1)
    return n;

   
    else if(fibon[n]){
return fibon[n];
}
else{

    l=fib(n-1)+fib(n-2);
    fibon[n]=l;
return fibon[n];
}
return;
}

int check_fib(uint64_t i){
     uint64_t j,l;
     j=2;
    if(i<10000000){
     if(i==fib(0)||i==fib(1)){
                              printf("IsFibo");
                              return 0;
                              }
     else {
          while(j<=i+1&&i!=fib(j))
                      j++;
                     
          if(j<=i+1)
    printf("IsFibo");
    else
          printf("IsNotFibo");
          }
}
else{
while(fib(j)<i)
j++;
if(fib(j)==i)
printf("IsFibo");
else
printf("IsNotFibo");
}
          return 0;
     }                   



/* An easy way to determine if the given number is fibonacci or not
 if the number is n
calculate (5n*n+4) or (5n*n-4) is a perfect square or not. if it is than its a fibonacci number.
Try it yourself
Thank You!!
*/