 # DE Shaw On Campus Internship Coding round problem

Two friends, Alex and Munich managed to reach the

World Finals of an event hosted by Engineering Maths Global Private Limited. They are given a problem and they have 3 hours to solve it. The problem is easy, but as it involves large numbers, they find it difficult to solve them. Help them solve it.

You are given with an array A of size N, and 2

integers S and D. You are allowed to perform following operations on

a number x.

1.x+ A[i]

2.x-A[i]

1. x xor A[i] (bitwise xor)

where i varies from 0 to N-1. The number x at all the times must be within the range [0, 100000].

tell the minimum number of moves in which you can

change number S to number D. Output -1 if it is not

possible to convert S to D.

Input Format

The first line of input contains an integer N denoting the size of array A. Next line contains N space-separated integers

denoting A[i].

Next line contains an integer denoting S.

Next line contains an integer denoting D.

Constraints :

1<= N <= 100

1 <= A[i], S, D <= 10^5

** I am not getting how to solve this, can anyone give a solution for this problem using DP ?

2 Likes