Time complexity analysis of different looping program

 Analyze the time complexity of below function

Q1)

A()

{

    i=1;

    s=1;

    while(s<=n) 

    {

        i++;

        s=s+i;

        print "hi"

    }

}

for n=15 the values of i and s inside while loop as shown below:

i 1 2 3 4 5

s 1 3 6 10 15

for n=15, the while loop runs 5 times ..i.e, approximately sqrt(n) times

so time complexity = O(sqrt(n))

In depth explanation:

Let this while loop runs k times and after k iterations,

s would be sum of first k natural numbers.

and s must be >= n to come out of the loop

(k*(k+1))/2 = n

k*k+k >2*n

k*k approximately equal to n

k is approximately equal to sqrt(n)

===========================================

 Analyze the time complexity of below function

Q2)

A()

{

    i=1;

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

    {

        print "hi"

    }

time complexity = O(sqrt(n))

===========================================

Analyze the time complexity of below function

Q3) 

A()

{

    int i,j,k,n;

    for(i=1;i<=n;i++) 

    {

        for(j=1;j<=i;j++)

        {

            for(k=1;k<=100;k++)

                print "hi"

        }

    }

}

                    |i=1       |i=2 |i=3

j loop runs         |1 time      |1,2 that is 2 times |1,2,3 that is 3 times     

for each j k runs |100 times |2*100 times |k=3*100

= 100+2*100+3*100 +.....+n*100

                    = 100*(1+2+3+............+n)

                    = O(n*n)

==============================================================

Q4) 

A()

{

    int i,j,k,n;

    for(i=1;i<=n;i++) 

    {

        for(j=1;j<=i*i;j++)

        {

            for(k=1;k<=n/2;k++)

                print "hi"

        }

    }

}

                    |i=1       |i=2 |i=3 ..........n

j loop runs         |1 time      |1,2,3,4 i.e, 4 times |3*3=9 times......n*n     

for each j k runs |n/2 times |4*n/2 times |9*n/2........(n*n)* n/2

= n/2+4*(n/2)+9*(n/2) +.....+(n*n)* (n/2)

                    = n/2*(1+4+9+............+n*n)

                    = n/2*(n*(n+1)*(2*n+1))/6

                    = O(n*n*n*n)

====================================================================

Q5) 

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

{

print "hi"

}

i will take values 1,2,4....n

2^0, 2^1, 2^2.....2^k

2^k =n and k=log2(n)

===================================================================

Q6)

while(n>1)

{

n = n/2

}

if n=16 then 16,8,4,2..4 times ...log2(16) = log2(n) times

======================================================================

Q7)

for(i=n/2;i<=n;i++) ........................n/2 times

    {

        for(j=1;j<=n/2;j++) .............. n/2 times

        {

            for(k=1;k<=n;k = k*2) ....... log2(n) times

                print "hi"

        }

    }

= (n/2)*(n/2)*log2(n) = n*nlog2(n)

===========================================================================

Q8)

for(i=n/2;i<=n;i++) ........................n/2 times

    {

        for(j=1;j<=n;j = 2*j) .............. log2(n) times

        {

            for(k=1;k<=n;k = k*2) ....... log2(n) times

                print "hi"

        }

    }

= (n/2)*log2(n)*log2(n) = n*log2(n)*log2(n)

printing the matrix in spiral format in c

#include<stdio.h>

#include<string.h>

int main() 

{

    int n,i,j,r=0,co=1,c=0,nr=0,nc=0;

    scanf("%d",&n);

    int mat[n][n],nd=n;

    while(n>=1)

    {

        for(i=1;i<n;i++)

            mat[r][c++]=co++;

        for(i=1;i<n;i++)

            mat[r++][c]=co++;

        for(i=1;i<n;i++)

            mat[r][c--]=co++;

        for(i=1;i<n;i++)

            mat[r--][c]=co++;

        n=n-2;

        nr++;

        nc++;

        r=nr;

        c=nc;

    }

    if(nd%2 != 0)

        mat[--nr][--nc]=co;

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

    {

        for(j=0;j<nd;j++)

            printf("%3d ",mat[i][j] ); 

        printf("\n");

    }

} 

input 

6

output:

  1   2     3   4    5     6 

 20  21  22  23  24   7 

 19  32  33  34  25   8 

 18  31  36  35  26   9 

 17  30  29  28  27  10 

 16  15  14  13  12  11

Hacker Rank Append and Delete solution in c

Problem:

https://www.hackerrank.com/challenges/append-and-delete/problem

Solution:

#include<stdio.h>

#include<string.h>

int main()

{

    char s[101],t[101];

    int k;

    scanf(" %s",s);

    scanf(" %s",t);

    scanf("%d",&k);

    int ls=strlen(s);

    int lt=strlen(t),i,ans;

    for(i=0;s[i]!='\0'&&t[i]!='\0';i++)

    {

        if(s[i]!=t[i])

            break;

    }

    ans=ls-i+lt-i;

        

    if(ans ==k||(ans < k && ans%2 == k%2)||k>=ls+lt)

        printf("Yes");

    else

        printf("No");

    

}

consider this testcase

y

yu

2

Here we can perform only one operation that is appending u

but given k is 2

so for this test case output must be No

so this is taken care by the condition

number of operations required and k must be even

as delete and append are two operations.

Also when k>=ls+lt, we can remove entire s string and append t string

as we can delete an empty string as many times as we like..so when k>=ls+lt,

output is always "YES"

John and GCD list Hacker Rank solution in C

Problem:

https://www.hackerrank.com/challenges/john-and-gcd-list/problem

Explanation:

GCD(B[1],B[2]) =A[1] that is A[1] divides B[2]

GCD(B[2],B[3]) =A[2] that is A[2] also divides B[2]

so B[2] must be divisible by both A[1] and A[2].

as LCM of A[1],A[2] will be divisible by both A[1] and A[2].

Therefore B[2] must be a multiple of LCM(A[1],A[2])

Since in the question, they wanted minimum value of B[2]

So, B[2] = LCM(A[1],A[2])

#include<stdio.h>

int gcd(int,int);

int lcm(int,int);

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n,i;

        scanf("%d",&n);

        int a[n];

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

            scanf("%d",&a[i]);

        printf("%d ",a[0]);

        for(i=0 ; i<n-1 ; i++)

        {

            if(a[i+1] >a[i])

                printf("%d ",lcm(a[i+1],a[i]));

            else

                printf("%d ",lcm(a[i],a[i+1]));

        }

        printf("%d\n",a[n-1]);        

    }

    return 0;

}

int gcd(int a, int b)

{

    if (b == 0)

        return a;

    return gcd(b, a % b);

}

int lcm(int a, int b)

{

    return (a*b)/gcd(a,b);

}

Sum The Series Problem Code: SUM1 codechef solution in c

https://www.codechef.com/problems/SUM1 

Explanation:

In the Question, it is mentioned to do %1000000007, to ensure the answer will always a number from 0 to 1000000006 

As n can take a value upto 10^16 in the question and n^2 cannot fit in even long long int, we cannot do n*n and then apply %1000000007

So we cannot do (n*n)%1000000007 so we do like this

((n%1000000007)*(n%1000000007))%1000000007

According to modular arithmetic (a*b)%m = ((a%m)*(b%m))%m

Here is the solution:

#include<stdio.h>

#define MOD 1000000007

int main() 

{

int t;

scanf("%d",&t);

while(t--)

{

    long long int n;

    scanf("%lld",&n);

    printf("%lld\n",(((n%MOD)*(n%MOD))%MOD));

}

return 0;

}

Printing Pattern Using Loops Hacker Rank Solution in C

https://www.hackerrank.com/challenges/printing-pattern-2 

Solution

#include <stdio.h>

int main() 

{

    int n,d,min;

    scanf("%d", &n);

  d=2*n-1;

    for(int i=1;i<=d;i++)

    {

        for(int j=1;j<=d;j++)

        {

            if(i<j)

                min=i-1;

            else

                min=j-1;

            if(min>d-j)

                min=d-j;

            if(min>d-i)

                min=d-i;

            printf("%d ",n-min);

        }

        printf("\n");

    }

    return 0;

}