retagged by
1,755 views
5 votes
5 votes
#include <stdio.h>

#define N 3

int main() {
     int array[N] = {1,2,3};
     int i,j;
     for ( i=1; i<(1<<N); i++) {
          for( j=0; j<N; j++) {
               if((1<<j)&i) {
                    printf("%d", array[j]);
               }
          }
          printf("\n");
     }
     return 0;
}
  • A. How many times the if successfully executes in this instance of c program. And how many time when $N = n \;\; , n \; \text{ is a positive integer }$ ?
  • B. What is the output?
  • C. What will be the complexity when $N$ is large.
retagged by

4 Answers

Best answer
6 votes
6 votes

How many times the if successfully executes in this instance of c program. 
What is the output?

Here the complexity of the code is coming to be $O(n2^{n})$

selected by
6 votes
6 votes

For this code 

#include <stdio.h>

#define N 3

int main() {
     int array[N] = {1,2,3};
     int i,j;
     for ( i=1; i<(1<<N); i++) {
          for( j=0; j<N; j++) {
               if((1<<j)&i) {
                    printf("%d", array[j]);
               }
          }
          printf("\n");
     }
     return 0;
}

Output is like : 

1,2,12,3,13,23,123 = Total $2^{n}-1$ = $2^{3}-1$ = 7 output sequences 


If we modify the code like :

#include <stdio.h>

#define N 5

int main() {
     int array[N] = {1,2,3}; //array[N] = {1,2,3,0,0}
     int i,j;
     for ( i=1; i<(1<<N); i++) {
          for( j=0; j<N; j++) {
               if((1<<j)&i) {
                    printf("%d", array[j]);
               }
          }
          printf("\n");
     }
     return 0;
}

Output is like : 

Many output Sequences = $2^{n}-1$ (Growing exponentially for every N)

edited by
4 votes
4 votes

No of times if block successfully executes,

$$\begin{align*} &= (\text{no of one digit subset})*1 \\ & \;\;\;+ (\text{no of two digit subset})*2 \\ & \;\;\;+ (\text{no of three digit subset})*3 \\ & \;\;\;+ ........... \\ & \;\;\;+ (\text{no of n digit subset})*n \\ &= \binom{n}{1}*1 + \binom{n}{2}*2 + \binom{n}{3}*3 + ........... + \binom{n}{n}*n \\ &=n.2^{n-1} \end{align*}$$ 

4 votes
4 votes
    #include <stdio.h>
     
    #define N 3
     
    int main() {
         int array[N] = {1,2,3};
         int i,j;
         for ( i=1; i<(1<<N); i++) {
              for( j=0; j<N; j++) {
                   if((1<<j)&i) {
                        printf("%d", array[j]);
                   }
              }
              printf("\n");
         }
         return 0;
    }
1
2
12
3
13
23
123

Now,

() has left to right associative and has greater precedence than any other operator.Precedence_Table.htm

<< left to right precedence, & has right to left precedence

For i=1

     and for j=0

  if((1<<j)&i)//1 will left shift 0 bit ,i.e.001+001=001

     So, if becomes true for j=0, in 1st iteration

     Prints 1

    for j=1

  if((1<<j)&i)//1 will left shift 1 bit ,i.e.010+001=000

    So, not executed

    for j=2

  if((1<<j)&i)//1 will left shift 2 bit ,i.e.100+001=000

    So, Not executed

for i=2

only

   for j=1

 if((1<<j)&i)//1 will left shift 1 bit ,i.e.010+010=010

    So,  executed a[j]=a[1]=2  Prints 2

for i=3

and for j=0

  if((1<<j)&i)//1 will left shift 0 bit ,i.e.001+001=001

     So, if becomes true for j=0, in 1st iteration

     Prints 1

  

for j=1

 if((1<<j)&i)//1 will left shift 1 bit ,i.e.010+010=010

    So,  executed a[j]=a[1]=2

    Prints 2

So, print 1 2

Likewise it will print.

Complexity will be $O(N(2^N-1))$=$O(N2^N)$

edited by

Related questions

0 votes
0 votes
1 answer
2
rishu_darkshadow asked Nov 8, 2017
318 views
In C language, bitwise operation can be applied to which of the following operandsA. char B. int C. short, long ...
3 votes
3 votes
1 answer
3
dd asked Jun 27, 2017
495 views
#include <stdio.h int main() { unsigned int m = 0; m |= 0xA38; printf("%x\n",m|(m-1)); printf("%x\n",( (m|(m-1)) + 1 ) & m ); }Find the output ?
0 votes
0 votes
1 answer
4
dd asked Apr 20, 2017
685 views
int main() { int n = 3,i,count=0; for(i=0;i<1<<n;i++) { int p = i; while(p) { int k = p & -p; p = p - k; count++; } } }The value of count variable after execution of the ...