(Originais Teachy 2024) - Questão Difícil de Matemática

O sistema de numeração binária é fundamental para a computação moderna, onde toda a informação é armazenada e processada utilizando apenas os dígitos 0 e 1. Converter um número decimal em binário envolve a divisão sucessiva do número por 2 e a anotação do resto da divisão, de baixo para cima, até que o quociente seja 0. Por exemplo, o número decimal 13 é convertido em binário 1101. Agora, imagine que estamos em um contexto de economia de recursos e é necessário que um algoritmo consiga determinar se um número é par ou ímpar, mas só pode realizar operações de adição, subtração e divisão por 2. Desenvolva um algoritmo que, utilizando o conceito de conversão de decimal para binário, consegue identificar se um número é par ou ímpar sem usar operações de módulo ou qualquer outro truque não relacionado à conversão binária. Em seguida, justifique por que seu algoritmo funciona e indique a complexidade de tempo do seu algoritmo.