algorithm - How to check whether number is generated from the given number -

a set of numbers between 1-360 given me. number n given me. have tell whether can generate given number n above list of number. can following operations on given numbers

1. (a+b)mod 360
2. (a-b)mod 360 a>b
3. i can take 1 number number of time(even in a+b, a=b)

now goal detect whether can generate number n or not

example suppose n 60 , list of number given 100(but may more), can generate 60 adding 100 fifteen time , take mod360 equal 60.

following solution have tried

#include<stdio.h> int ispossible=0; void anglepossible(int a1[],int angle,int currentangle,int n) {     int i;     if(angle==(currentangle%360))         ispossible = 1;     else if((currentangle!=0)&&(currentangle%360==0))         return;     for(int i=0;i<n;i++)     {         anglepossible(a1,angle,currentangle+a1[i],n);     } }  int main() {     int n,k;     int a1[361],a2[361];     int i,j;     int result;     scanf("%d%d",&n,&k);     for(i=0;i<n;i++)         scanf("%d",&a1[i]);     for(i=0;i<k;i++)         scanf("%d",&a2[i]);      for(i=0;i<k;i++)     {         ispossible=0;         anglepossible(a1,a2[i],0,n);         if(ispossible==1)         printf("yes\n");         else         printf("no\n");     }     return 0; } 

here naive algorithm solves(i think) problem, not efficient one.

problem setup:

input:

1. nums (numbers. array of ints)
2. target (the target)

output:

• bool indicating if target reachable

essentially want target using nums. starting point 0 on number line (you can 0).

therefore, keep track of locations can (an array initialized [0]). each number in nums, update locations can new number. since additions , substractions commutative, order not important.

here small python program showing idea:

def reachable(i, start = 0):    cantreach = range(360)   canreach = set()   reach = start   while reach in cantreach:     cantreach.remove(reach)     canreach.add(reach)     reach +=     reach = reach % 360    return canreach  def main(nums, target):   canreach = set([0])   in nums:     j in canreach:       canreach = canreach.union(reachable(i, j))     canreach = sorted(list(canreach))   print "can reach:", canreach   print "result:", target in canreach   main([100],60) 

the output is:

can reach: [0, 20, 40, 60, 80, 100, 120, 140, 160, 180, 200, 220, 240, 260, 280, 300, 320, 340] result: true