谷歌的一道面试题,请大家集思广益

是有关算法的
如果有一个等差数组,然后对这个数组里面的每个元素做如下操作
1. 如果这个元素是偶数,除以2, 然后得到的数字再分析是否是偶数,如果还是,继续除2,一直除到是奇数,
2. 如果这个元素是奇数,那么就保持原样
这样就得到了另外一个数组,
现在要求根据这个变换后的数组,能否得到变换前的数组,请描述下思路.
比如现在有个数组{1,2,3,4},变换后是{1,1,3,1},那么需要根据{1,1,3,1},得到1,2,3,4.

我当场想了20分钟也没有想出来,回头又想了几天还是没有什么很完整的思路,问了一个清华数学研究生,也没有搞定,因为对这个挺感兴趣的,发出来大家讨论下看看有没有高人能解答的.

谢谢

不能反向得到原始值， 我们以结果数组 1，1，3，1 为例子
假设原始值为 2^n, 2^m, 3*2^p, 2^q
由等差数组我们可以得到： p=n; m=n+1; q=n+2;（过程略）
那么数组2^n, 2^(n+1), 3*2^n, 2^(n+2)为原始数组；
则n=0是， 是1，2，3，4； n=1时，是2，4，6，8.
由此，不可反推原始数组。

事实上，2^n * (原始等差数组)都是目标数组的解！
因此要唯一确定解，必须附带其它条件。

如果不考虑算法优化的话是否可以这样

给定一个值，比如9，那么从1,1,1,1,。。。遍历到9，9,9,9,9，9
给每个位置的元素o进行o<<n的运算，
直到出现数组各自相邻元素的差为定值

bushmen,你的推导很有见地,当初我没有从他这个例子去展开想,而是举了很多其他例子去找到规律,而且他的提示"写个长点的数组来看看规律"也从某种程度上引导了我的思维方向,如果加一个条件,取最小的正整数集,这样应该可以得到一个唯一的答案,如果是这样的话,如何反推呢?求解...

TopCoder的题目。答案有很多个，要求选择最小的。

其实很Easy。设原来的数列第一项是a,差值是d。现在的数列首项是b，差值是e。
分情况（这样比较容易思考）：
1. a、d都是偶数。不考虑。
2. a是偶数，d是奇数。则知道偶数项(从1开始计数)都是奇数，也即现在的数列与原来的数列中，偶数项是不变的。就可以算出d了。
3. a是奇数，d是偶数。则知道所有项都是奇数，也即不变。
4. a、d是奇数，则奇数项都是奇数，也即不变。

然后求出最小的数组。

比如现在的是：1,1,3,1。按照情况2，偶数项都是奇数（1,1），故而d=0，显然不符合。
按照情况3，显然也不符合。按照情况4，d=(3-1)/2=1，故而为1,2,3,4，验证偶数项，满足。

thihy，你的这个思路真的太好了，确实很好的回答的了这个问题，感谢bushmen，thihy，你们给我提供了很好的思路考虑这个问题。

值得思考的算法。。。