Wednesday 21 December 2016

Circular Array Loop detection C program


You are given an array of positive and negative integers. if a number n at an index is positive, then move forward n steps. Conversely, if its negative, move backwards n steps. Determine if there is a loop in this array. For Example given the array [2,-1,1,2,2] index 0 maps to index 2,1 maps to 0,2 maps to 3 and so on. There is a loop in this array because 0 maps to 2,2 maps to 3,3 maps to 0.(Use the modulo operator)
Solution 1:
#include<stdio.h>
    #include<stdlib.h>
    main()
    {
       
        int a[10],n,i,k,x,c;
        printf("enter the size of array");
        scanf("%d",&n);
        printf("enter the elements");
        for(i=0;i<n;i++)
scanf("%d",&a[i]);
        x=k=0;
        c=0;
        while(c<n) //we can have maximum of n jumps
        {
        //printf("\t%d\t",k);
  if(a[k]==0)
  {
printf("element value cannot be zero");
exit(0);
}
else if(a[k]>0)
            {
 k=(k+a[k])%n;
}
else if(a[k]<0)
            {
            k=(k+a[k])%n;
            if(k<0)
  k=n+k;
            }
            if(x==k)
            {
              printf("loop exists");
                exit(0);
}
            c++;
}
}

(OR)

Below this recursive implementation, you have simple code
#include<stdio.h>
#include<stdlib.h>
void fun(int ,int ,int );
int b[10][10];
main()
    {
       
        int a[10],n,i,k,x;
        printf("enter the size of array");
        scanf("%d",&n);
        printf("enter the elements");
        for(i=0;i<n;i++)
        scanf("%d",&a[i]);
        for(i=0;i<n;i++)
        {
            k=i;
            if(a[k]==0)
                  {
                    printf("element value cannot be zero");
                    exit(0);
                }
                else if(a[k]>0)
                {
                  k=(k+a[k])%n;
                  //printf("\n%d",k);
                }
                  else if(a[k]<0)
                {
                    k=(k+a[k])%n;
                    if(k<0) k=n+k;
                    //printf("\n%d",k);
                }
                b[i][0]=i;
                b[i][1]=k;
              
        }
              
        k=0;
        for(i=0;i<n;i++)
    {
         x=b[i][0];
         fun(i,k,x);
    }
}
void fun(int i,int k,int x)
{
        for(k=k+1; k<5;k++)
        {
                if(b[i][1]==b[k][0])
                {
                        if(x==b[k][1])
                        {
                                printf("loop exists");
                                exit(0);
                        }
                        else
                         fun(k,1,x);
                }
        }
}

(OR)


#include<stdio.h>
#include<stdlib.h>
main()
{

    int a[10],n,i,k,x,j,c,t;
    printf("enter the size of array");
    scanf("%d",&n);
    printf("enter the elements");
    for(i=0;i<n;i++)
    scanf("%d",&a[i]);
    for(i=0;i<n;i++)
    {
        x=i;k=i;
          c=0;
          while(c<n) //Atmost we can have maximum of n jumps
          {
            if(a[k]==0) 
            {
                printf("element value cannot be zero");
                exit(0);
            }
            else if(a[k]>0)
            {
              k=(k+a[k])%n;
            }
            else if(a[k]<0)
            {
                k=(k+a[k])%n; //if k+a[k] is negative then (k+a[k])%n is also negative
                if(k<0) k=n+k;
/* if the index k is negative we have to loop back to last element in the array.
This can be achieved by doing subtracting from n and 
since k is negative, n+k will be do the subtraction from n*/
             }
            if(x==k)
            {
                printf("loop exists");
                exit(0);
            }

            c++;
        }
    }
}

No comments:

Post a Comment