hudson-river-trading SDE Internship Online Test: Counting Base-k Numbers with 0 and 1

An internship online test question for hudson-river-trading SDE role. Find how many numbers less than or equal to n have base k representations with only digits 0 and 1.