Hello,

Recently I appeared for telephonic round with Google and here is the question. I tried to come up with backtracking solution. Could someone please let me know of a better solution?

Question - You need to generate all 16 digit numbers such that the following conditions are satisfied by all those numbers -

1. The odd numbered positions in such a number must be a prime digit.
2. The even numbered positions in such a number must be an even digit.

Example - Since its a 16 digit number (0-indexed) , one such valid number could be 0223456782032547. In this 16 digit number all the digits in even position (position no. starting from 0) have even digit and all the digits in odd position (position no. starting from 1) have prime digit.