The Gateway to Computer Science Excellence
+5 votes
633 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 by Veteran (57.2k points)
retagged by | 633 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})$

by Boss (21.5k points)
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)

by Veteran (50.9k points)
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*}$$ 

by Veteran (57.2k points)
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)$

by Veteran (119k points)
edited by
0
This is general case of  generating all combinations of a set using bit_masking. very useful for small n.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,291 answers
198,209 comments
104,892 users