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