Thursday, 12 August 2021

To find the product of every element other than itself without using division operator in O (n) time.

 For Example: Consider the below array 

1

2

3

4

A[0]

A[1]

A[2]

A[3]

To get the product of every element other than itself without using division operator in O (n) time, we use

Product of all array elements except the current element =

Product of all elements below the current index * Product of all elements above the current index

 

So Product of all elements below the current index is

1

1

2

6

A[0]

A[1]

A[2]

A[3]

 

Product of all elements above the current index is

24

12

4

1

A[0]

A[1]

A[2]

A[3]

 

Product of both would be

24

12

8

6

A[0]

A[1]

A[2]

A[3]

 

 

Java introduction- Online notes while explaining

 


Big Factorial Question Explanation To solve it in C




Debugging Questions for competitions

 

Easy:

1. https://www.codechef.com/MARCH21C/problems/NOTIME/

 

Wrong code

 

# cook your dish here

n,h,x=map(int,input().split())

a=list(map(int,input().split()))

if(h<=x):

    print("YES")

else:

    flag=0

    for i in range(n):

        if(h+a[i]>=x):

            flag=1

            break

    if(flag == 1):

        print("YES")

    else:

        print("NO")

 

Correct output:

# cook your dish here

n,h,x=map(int,input().split())

a=list(map(int,input().split()))

if(h<=x):

    print("YES")

else:

    flag=0

    for i in range(n):

        if(x+a[i]>=h):

            flag=1

            break

    if(flag == 1):

        print("YES")

    else:

        print("NO")

 

2.  https://www.codechef.com/OCT20B/problems/CHEFEZQ/

 

Wrong code

t=int(input())

for i in range(t):

    n,k=map(int, input().split())

    l=list(map(int, input().split()))

    ans=1

    carry=0

    flag=0

    for j in range(n):

        l[j]=l[j]+carry

        if(l[j] < k):

            flag=1

            break

        carry=l[j]-k

    if(flag == 1):

        print((j+1))

    else:

        print(carry+k+1)

 

Correct code:

t=int(input())

for i in range(t):

    n,k=map(int, input().split())

    l=list(map(int, input().split()))

    ans=0

    carry=0

    flag=0

    for j in range(n):

        l[j]=l[j]+carry

        if(l[j] < k):

            flag=1

            break

        carry=l[j]-k

    if(flag == 1):

        print((j+1))

    else:

        print(carry//k+n+1)

       

      

3. https://www.codechef.com/FEB19B/problems/HMAPPY2/

 

Wrong answer:

def lcm(x, y):

    from fractions import gcd

    return x * y // gcd(x, y)

 

t = int(input())

while(t>0):

    try:

        n,a,b,k=map(int,input().split())

    except EOFError:

        break

    l=lcm(a,b)

    ca=n/a

    cb=n/b

    cc=n/l

    if((ca-cc)+(cb-cc))>= k:

        print("Win")

    else:

        print("Los")

    t=t-1

 

 

Correct answer:

 

def lcm(x, y):

    from fractions import gcd

    return x * y // gcd(x, y)

 

t = int(input())

while(t>0):

    n,a,b,k=map(int,input().split())

   

    l=lcm(a,b)

    ca=n//a

    cb=n//b

    cc=n//l

    if((ca-cc)+(cb-cc))>= k:

        print("Win")

    else:

        print("Lose")

    t=t-1

 

4. https://www.codechef.com/NOV18B/problems/CHFTIRED/

Wrong Code:

#include <stdio.h>

int main()

{

                int t;

                while(t--)

                {

                                int a,b;

                                scanf("%d%d",&a,&b);

                                printf("YES\n");

                }

                return 0;

                }

 

Correct answer:

#include <stdio.h>

int main()

{

                int t;

                scanf("%d",&t);

                while(t--)

                {

                                int a,b;

                                scanf("%d%d",&a,&b);

                                printf("YES\n");

                }

                return 0;

                }

 

5. https://www.codechef.com/problems/MISSP

Wrong code:

 

#include <stdio.h>

int main() {

                // your code goes here

                int t,n;

                scanf("%d",&t);

                while(t--)

                {

                    scanf("%d",&n);

                    int a[n],b[n]={0},i;

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

                    {

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

                        b[a[i]]++;

                    }

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

                    {

                        if(b[a[i]] == 1)

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

                    }

                }

                return 0;

}

 

Correct answer

#include <stdio.h>

#include<math.h>

 

int main()

{

int t,n,a,i;

scanf("%d",&t);

while(t--)

{

 int b[100000]={0};

 scanf("%d",&n);

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

 {

     scanf("%d",&a);

     b[a]++;

 }

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

 {

     if(b[i]%2!=0)

     {

         printf("%d\n",i);

         break;

     }

 }

  }

                return 0;

}