a bit of topcoder: SRM 632 Div 2 Medium

Problem Statement:
Given d[i] array of trailing zeroes in in the representation of a[i] (where a[i] can be any satisfying integer), determine whether a consecutive sequence a[i], a[i+1], ..., a[j] can form a geometric sequence.

Solution:
I think this is a good problem :D The important observation is that a[i], ..., a[j] can form a geometric sequence if and only if d[i], ..., d[j] forms an arithmetic sequence. This is because for a[i] to have a change in d[i] to d[i+1], it has to be multiplied with a constant \(r = r_0(2^k)\) where \(k\) is the difference between d[i] and d[i+1]. Furthermore, \(r_0\) must be odd, otherwise if we factor out \(2\) from \(r_0\) it will contribute to \(k\) leading to a contradiction. Now if d[i], ..., d[j] does not form an arithmetic sequence, there is some point where the \(k\) in \(r\) changes value, which contradicts the fact that \(r\) is constant. Finally, setting \(r_0=1\) or any other odd valued integer will give us the desired geometric sequence.