HACKERRANK.COM => PROJECTEULER SOLUTION # 3

_{This problem is a programming version of Problem 3 from projecteuler.net}

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of a given number N?

Input Format
First line contains T, the number of test cases. This is followed by T lines each containing an integer N.

Output Format
For each test case, display the largest prime factor of N.

Constraints
1≤T≤10
10≤N≤1012

Sample Input

2

10

17

Sample Output

5

17

First of all I submitted this code and this code showed Time limit exceeded in test case 5.

So this is not the most efficient code to find the largest prime factor of a given number.

/*****************************************************/

#include<stdio.h>

int isPrime(long long int n)

{

    long long int i;

    for(i=2;i*i<=n;i++)

        if(n%i==0)

            return 0;

    return 1;

}

long long int findLargestPrimeFactor(long long int n)

{

    long long int counter=3;

    while(n%2==0)

        n/=2;

    if(n==1)

        return 2;

    while(n!=1)

    {

        if(isPrime(n))

            return n;

        while(n%counter==0)

            n/=counter;

        counter+=2;

   }

   return counter-2;

}

int main()

{

    int t;

    long long int n;

    scanf("%d",&t);

    while(t--)

    {

        scanf("%lld",&n);

        printf("%lld\n",findLargestPrimeFactor(n));

    }

    return 0;

}

/*****************************************************/

PRINTING OF PERMUTATIONS OF A GIVEN STRING USING FOR LOOP

Here, For loop(instead of recursion) has been used to print all the permutations of a given string in the lexicographic order.
The code executes correctly even for strings having repeated characters. 

For example,
           For the string:aab
           The permutations are: aab,aba,baa.

Source Code:

****************************************************************

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void swap(char*str,int index1,int index2)/*function to swap two characters of a string str
                                                                     at index1 and index2.*/
{
    char temp;
    temp=str[index1];
    str[index1]=str[index2];
    str[index2]=temp;
}

int compare(const void *a,const void *b)
{
    return strcmp((char*)a,(char*)b);
}

long long findFactorial(int n) //to find factorial of a number.
{
    long long fact=1,i;
    for(i=2;i<=n;i++)
    {
        fact*=i;
    }
    return fact;
}

long long findNumberOfPermutations(char str[]) //to find the no of permutations of a given string.
{
    long long number,repetition,*flag,i;

    flag=(long long *)malloc(sizeof(long long )*128);
    for(i=0;i<128;i++)
        flag[i]=0;
    for(i=0;str[i];i++)
        flag[str[i]]++;

    number=findFactorial(strlen(str));
    for(i=0;i<128;i++)
        if(flag[i]>1)
            number/=findFactorial(flag[i]);
    return number;
}

int findMinimum(char str[],int index1)
{
    /*
        this function returns the index of minimum element in the array
        that is greater that element at index1 but minimum in the array from index1+1 till strlen(str)
    */
    int minIndex,i;
    int min=2147483647;
    for(i=index1+1;i<strlen(str);i++)
    {
        if(str[i]<min && str[i]>str[index1])
        {
            min=str[i];
            minIndex=i;
        }
    }
    return minIndex;
}


void findNextPermutation(char str[]) //to find the next Permutation of string str.
{
    int i,index1,index2;
    for(i=strlen(str)-1;i>=0;i--)
        if(str[i-1]<str[i])
            break;

    index1=i-1;
    index2=findMinimum(str,index1);
    swap(str,index1,index2);
    qsort(str+index1+1,strlen(str)-index1-1,sizeof(char),compare);
}

void printPermutations(char str[]) //to print all permutations of a string.
{
    int i;
    long long numberOfPermutations;
    numberOfPermutations=findNumberOfPermutations(str);
    qsort((void*)str,strlen(str),sizeof(char),compare);
    for(i=0;i<numberOfPermutations;i++)
    {
        printf("%d -> %s\n",i+1,str);
        if(i==numberOfPermutations-1)
            break;
        findNextPermutation(str);
    }
}

int main()
{
    char str[10000];
    printf("\nEnter the string:");
    scanf("%s",str);
    printPermutations(str);
    return 0;
}

****************************************************************

SETTING THE ELEMENTS OF A PARTICULAR ROW AND COLUMN TO ZERO

Given a 2-D Matrix, if an element of the matrix is zero, all elements of the corresponding row and column are set to ZERO.

In the solution to this question,  a duplicate matrix has been created and by traversing the elements of
the original matrix, changes in the duplicate matrix are made accordingly.

For example,
         For a given 3x3 matrix:
                            1 2 3
                            4 0 5
                            9 7 0
         The matrix set to zero would be,
                            1 0 0
                            0 0 0
                            0 0 0

Source Code:-
*****************************************************************

#include<stdio.h>
#include<stdlib.h>

/*function which takes the original matrix,creates its duplicate and sets
   the required elements to zero in the duplicate matrix*/

  int ** setZero(int **arr,int m,int n)
 {
    int **arr1,i,j,k;
    arr1=(int**)malloc(sizeof(int*)*m);//allocating memory to duplicate matrix.
    for(i=0;i<m;i++)
        arr1[i]=(int*)malloc(sizeof(int)*n);
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            arr1[i][j]=arr[i][j];

    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
        {
            if(arr[i][j]==0)
            {
                for(k=0;k<m;k++)
                    arr1[k][j]=0;
                for(k=0;k<n;k++)
                    arr1[i][k]=0;
            }
        }
    }
    return arr1;
}

int main()
{
    int **arr,m,n,i,j,**arr1;
    printf("\nEnter the no of rows:");
    scanf("%d",&m);
    printf("\nEnter the no of columns:");
    scanf("%d",&n);
    arr=(int**)malloc(sizeof(int*)*m);
    for(i=0;i<m;i++)
        arr[i]=(int*)malloc(sizeof(int)*n);

    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            scanf("%d",&arr[i][j]);

    arr1=setZero(arr,m,n);

//the original matrix is kept intact and the changes are done in the duplicate one i.e. arr1.

    for(i=0;i<m;i++)
    {
        for(j=0;j<n;j++)
            printf("%d",arr1[i][j]);//printing of elements of duplicate matrix i.e. arr1.
        printf("\n");
    }
    return 0;
}


*****************************************************************

CHECKING IF THE TWO GIVEN STRINGS ARE ANAGRAMS OR NOT

String1 is said to be the ANAGRAM of String2 if the characters of String1 can be jumbled up to form String2. To check for ANAGRAMS, the length of the two strings has to be same.

For example, BUTTERFLY  and TTFYLUBRE are ANAGRAMS.
                      MOUSE and UESOME are not ANAGRAMS as the lengths vary.
                      LABEL and BBALE are not ANAGRAMS as the characters of the two strings
                      are not same.

Source Code:-
********************************************************
#include<stdio.h>
#include<string.h>

int isAnagram(char str1[],char str2[]);

int main()
{
    char str1[100],str2[100];
    int r;
    printf("\nEnter first string:");
    gets(str1);
    printf("\nEnter second string:");
    gets(str2);
    if(strlen(str1)==strlen(str2))/*if length of the 2 strings are not equal,
                                    they are not anagrams.*/
    {
        r=isAnagram(str1,str2);
        if(r==1)
            printf("TRUE");
        else
            printf("FALSE");
    }
    else
        printf("FALSE");
    return 0;
}


int isAnagram(char str1[],char str2[]) //function to check if 2 strings are anagrams.
{
    int abc1[128],abc2[128],i;

    /*the length of the two arrays is chosen as 128 as basic ASCII code is from 0 to 127.
    so checking for all characters becomes quite easy and fast.*/

    for(i=0;i<128;i++)
    {
        abc1[i]=abc2[i]=0;
    }

    /*For a given character in a string,incrementation is done in
      the array at the character's corresponding ascii index*/

    for(i=0;str1[i]!='\0';i++)
        abc1[(int)str1[i]]++;

    for(i=0;str2[i]!='\0';i++)
        abc2[(int)str2[i]]++;

    for(i=0;i<128;i++)//if the 2 arrays are equal,the strings are Anagrams.
    {
        if(abc1[i]!=abc2[i])
            return 0;
    }
    return 1;
}


********************************************************

Find whether a number is present in another number as a substring or not without using Arrays

Question:

Write a program to take two numbers from the user and find whether the second number is present in the first number or not without using arrays.

For example:

Suppose the first number is 152643798

And the second number is 43

So we can say that the second number is present in the first number.

/****************************************************************/

#include<stdio.h>

int isPresent(long long int a,long long int b)

{

    long long int ca,cb;

    ca=a;

    cb=b;

    while(a)

    {

        while(a && b)

        {

            if(a%10 == b%10)

            {

                a/=10;

                b/=10;

            }

            else

                break;

        }

        if(!b)

            return 1;

        ca/=10;

        a=ca;

        b=cb;

    }

    return 0;

}

int main()

{

    long long int num,n;

    printf("Enter two numbers : \n");

    scanf("%lld%lld",&num,&n);

    if(isPresent(num,n))

        printf("YES\n");

    else

        printf("NO\n");

    return 0;

}

/****************************************************************/