Frecuencia máxima de un resto módulo 2i

Dado un número octal N , la tarea es convertir el número a decimal y luego encontrar el módulo con cada potencia de 2 , es decir , 2 ⁱ tal que i > 0 y 2 ⁱ < N, e imprimir la frecuencia máxima del módulo.
Ejemplos: 

Entrada: N = 13 
Salida: 2 
Octal(13) = decimal(11) 
11 % 2 = 1 
11 % 4 = 3 
11 % 8 = 3 
3 ocurre más, es decir, 2 veces.

Entrada: N = 21 
Salida: 4 

Enfoque: encuentre la representación binaria del número reemplazando el dígito con su representación binaria. Ahora se sabe que cada dígito en la representación binaria representa una potencia de 2 en orden creciente. Entonces, el módulo del número con una potencia de 2 es el número formado por la representación binaria de sus bits anteriores. Por ejemplo:

Octal(13) = decimal(11) = binario(1011) 
Entonces, 
11(1011) % 2 (10) = 1 (1) 
11(1011) % 4 (100) = 3 (11) 
11(1011) % 8 (1000) = 3 (011) 
 

Aquí se puede observar que cuando hay un cero en la representación binaria del módulo, el número permanece igual. Entonces, la frecuencia máxima del módulo será 1 + el número de 0 consecutivos en la representación binaria (no los ceros iniciales) del número. Como el módulo comienza desde 2, elimine el LSB del número.

A continuación se muestra la implementación del enfoque anterior: 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Binary representation of the digits
const string bin[] = { "000", "001", "010", "011",
                       "100", "101", "110", "111" };
 
// Function to return the maximum frequency
// of s modulo with a power of 2
int maxFreq(string s)
{
 
    // Store the binary representation
    string binary = "";
 
    // Convert the octal to binary
    for (int i = 0; i < s.length(); i++) {
        binary += bin[s[i] - '0'];
    }
 
    // Remove the LSB
    binary = binary.substr(0, binary.length() - 1);
 
    int count = 1, prev = -1, i, j = 0;
 
    for (i = binary.length() - 1; i >= 0; i--, j++)
 
        // If there is 1 in the binary representation
        if (binary[i] == '1') {
 
            // Find the number of zeroes in between
            // two 1's in the binary representation
            count = max(count, j - prev);
            prev = j;
        }
 
    return count;
}
 
// Driver code
int main()
{
    string octal = "13";
 
    cout << maxFreq(octal);
 
    return 0;
}

// Java implementation of the approach
class GFG
{
 
// Binary representation of the digits
static String bin[] = { "000", "001", "010", "011",
                        "100", "101", "110", "111" };
 
// Function to return the maximum frequency
// of s modulo with a power of 2
static int maxFreq(String s)
{
 
    // Store the binary representation
    String binary = "";
 
    // Convert the octal to binary
    for (int i = 0; i < s.length(); i++)
    {
        binary += bin[s.charAt(i) - '0'];
    }
 
    // Remove the LSB
    binary = binary.substring(0,
             binary.length() - 1);
 
    int count = 1, prev = -1, i, j = 0;
 
    for (i = binary.length() - 1;
         i >= 0; i--, j++)
 
        // If there is 1 in the binary representation
        if (binary.charAt(i) == '1')
        {
 
            // Find the number of zeroes in between
            // two 1's in the binary representation
            count = Math.max(count, j - prev);
            prev = j;
        }
    return count;
}
 
// Driver code
public static void main(String []args)
{
    String octal = "13";
 
    System.out.println(maxFreq(octal));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 implementation of the approach
 
# Binary representation of the digits
bin = [ "000", "001", "010", "011",
        "100", "101", "110", "111" ];
 
# Function to return the maximum frequency
# of s modulo with a power of 2
def maxFreq(s) :
 
    # Store the binary representation
    binary = "";
 
    # Convert the octal to binary
    for i in range(len(s)) :
        binary += bin[ord(s[i]) - ord('0')];
     
    # Remove the LSB
    binary = binary[0 : len(binary) - 1];
 
    count = 1; prev = -1;j = 0;
 
    for i in range(len(binary) - 1, -1, -1) :
 
        # If there is 1 in the binary representation
        if (binary[i] == '1') :
 
            # Find the number of zeroes in between
            # two 1's in the binary representation
            count = max(count, j - prev);
            prev = j;
         
        j += 1;
 
    return count;
 
# Driver code
if __name__ == "__main__" :
 
    octal = "13";
 
    print(maxFreq(octal));
 
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
                     
class GFG
{
 
// Binary representation of the digits
static String []bin = { "000", "001", "010", "011",
                        "100", "101", "110", "111" };
 
// Function to return the maximum frequency
// of s modulo with a power of 2
static int maxFreq(String s)
{
 
    // Store the binary representation
    String binary = "";
 
    // Convert the octal to binary
    for (int K = 0; K < s.Length; K++)
    {
        binary += bin[s[K] - '0'];
    }
 
    // Remove the LSB
    binary = binary.Substring(0,
             binary.Length - 1);
 
    int count = 1, prev = -1, i, j = 0;
 
    for (i = binary.Length - 1;
         i >= 0; i--, j++)
 
        // If there is 1 in the binary representation
        if (binary[i] == '1')
        {
     
            // Find the number of zeroes in between
            // two 1's in the binary representation
            count = Math.Max(count, j - prev);
            prev = j;
        }
    return count;
}
 
// Driver code
public static void Main(String []args)
{
    String octal = "13";
 
    Console.WriteLine(maxFreq(octal));
}
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript implementation of the approach
 
// Binary representation of the digits
bin = [ "000", "001", "010", "011",
            "100", "101", "110", "111" ];
 
// Function to return the maximum frequency
// of s modulo with a power of 2
function maxFreq( s )
{
 
    // Store the binary representation
    var binary = "";
 
    // Convert the octal to binary
    for (var i = 0; i < s.length; i++) {
        binary += bin[s.charAt(i) - '0'];
    }
 
    // Remove the LSB
    binary = binary.substr(0, binary.length - 1);
 
    var count = 1, prev = -1, i, j = 0;
 
    for (i = binary.length - 1; i >= 0; i--, j++)
 
        // If there is 1 in the binary representation
        if (binary.charAt(i) == '1') {
 
            // Find the number of zeroes in between
            // two 1's in the binary representation
            count = Math.max(count, j - prev);
            prev = j;
        }
 
    return count;
}
 
var octal = "13";
document.write( maxFreq(octal));
 
// This code is contributed by SoumikMondal
 
</script>

2

Complejidad de tiempo: O (N), ya que estamos usando un bucle para atravesar N veces. Donde N es la longitud de la string.
Espacio auxiliar: O(N), ya que estamos usando espacio adicional para el binario de strings.