search
Log In
5 votes
733 views
#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.
in Programming
retagged by
733 views
1
If N=n, then array will be like {1,2,3,0,0,0,0,0,0,0,...........}

Not getting what you are saying.

Are you saying this {1,2,3,4,5,6,7,8,9....................} ?
1
no no..:) calculate it for given program ...then generalize for N = n
1
For N = n, the IF block executes $2^{n} - 1$
0
#include <stdio.h>

#define N 3
int cnt = 0;
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) {
                    cnt++;
                    printf("%d", array[j]);
               }
          }
          printf("\n");
     }
     printf("count = %d\n",cnt );
     return 0;
}

Actually, cnt value is needed in terms of n

0
Yes, that is good otherwise needed to count as it grows polynomially.
1
#include <stdio.h>

#define N 3
int cnt = 0;
int if_run_count = 0;
int f() {
     if_run_count++;
     return 1;
}


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(f() && (1<<j)&i) {
                    cnt++;
                    printf("%d", array[j]);
               }
          }
          printf("\n");
     }
     printf("if inside count = %d\n",cnt );
     printf("if run count = %d\n",if_run_count);
     return 0;
}

QS need cnt value only but not if_run_count.

4 Answers

6 votes
 
Best answer

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

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
1
  • it is growing exponentially. 
  • To print $123$ , control enters inside if block three times
0
Yes, for 123 three times ,i.e respectively for every j.
0

can u explain how does

(1<<j)&i)

works ?

0

@Kapil SIR  is the complexity O(n2^n) ?  because outer loop executes for O(2^n) and inner loop executed for O(n) time

Correct me if my understanding is wrong

0
Yes, I think SO. But let me check if $N.2^{N} = O(2^{N})$

In this case, if this is true, then $\frac{N.2^{N}}{2^{N}}$ is not constant, but depends on N, so you r right.

Complexity = $O(N.2^{N})$
0

@Kapil  SIR  , 

I have got one more doubt here . What IF the inner loop depends on outer loop ? What is the change in complexity in such case ? that is  What happens if inner loop is 

 for( j=i; j<N; j++) 
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*}$$ 

0

How many times the if successfully executes

when N=n=3  while putting a value of n=3 in "n*2^(n-1)" we get the number of time if executed successfully is 12  which is same as  { 1,2,12,3,13,23,123 } //while counting all

I am not getting how are you calculating this?

(no of one digit subset) *1 +(no of two digit subset) *2 +........(no of  n digit subset) * n

here one digit number is 3 e.g 1,2,3  in sequence {1,1,12,3,13,23,123 } 

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
0
This is general case of  generating all combinations of a set using bit_masking. very useful for small n.

Related questions

1 vote
1 answer
1
137 views
The following sum of $n+1$ terms $2 + 3 \times \begin{pmatrix} n \\ 1 \end{pmatrix} + 5 \times \begin{pmatrix} n \\ 2 \end{pmatrix} + 9 \times \begin{pmatrix} n \\ 3 \end{pmatrix} + 17 \times \begin{pmatrix} n \\ 4 \end{pmatrix} + \cdots$ up to $n+1$ terms is equal to $3^{n+1}+2^{n+1}$ $3^n \times 2^n$ $3^n + 2^n$ $2 \times 3^n$
asked Sep 23, 2019 in Combinatory Arjun 137 views
0 votes
1 answer
2
68 views
In C language, bitwise operation can be applied to which of the following operands A. char B. int C. short, long D. All of these
asked Nov 8, 2017 in Programming rishu_darkshadow 68 views
3 votes
1 answer
3
112 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 ?
asked Jun 28, 2017 in Programming dd 112 views
0 votes
1 answer
4
139 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 above code? The value of count variable when $n = m$ ? [EDITED]
asked Apr 20, 2017 in Programming dd 139 views
...