Distancia máxima entre dos 1 en representación binaria de N

Dado un número N, la tarea es encontrar la distancia máxima entre dos 1 en la representación binaria de N dado. Imprime -1 si la representación binaria contiene menos de dos 1.
Ejemplos: 
 

Input: N = 131
Output: 7
131 in binary = 10000011.
The maximum distance between two 1's = 7.

Input: N = 8
Output: -1
8 in binary = 01000.
It contains less than two 1's.

Acercarse: 
 

• Primero encuentre la representación binaria de N .
• Para cada bit calculado, verifique si es un ‘1’.
• Almacene el índice del primer ‘1’ encontrado en first_1, y el último ‘1’ encontrado en last_1
• Luego verifique si last_1 es menor o igual que first_1. Será el caso cuando N es una potencia de 2. Por lo tanto imprime -1 en este caso.
• En cualquier otro caso, encuentre la diferencia entre last_1 y first_1. Esta será la distancia requerida.

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

// C++ program to find the
// Maximum distance between two 1's
// in Binary representation of N
 
#include <bits/stdc++.h>
using namespace std;
 
int longest_gap(int N)
{
 
    int distance = 0, count = 0,
        first_1 = -1, last_1 = -1;
 
    // Compute the binary representation
    while (N) {
 
        count++;
 
        int r = N & 1;
 
        if (r == 1) {
            first_1 = first_1 == -1
                          ? count
                          : first_1;
            last_1 = count;
        }
 
        N = N / 2;
    }
 
    // if N is a power of 2
    // then return -1
    if (last_1 <= first_1) {
        return -1;
    }
    // else find the distance
    // between the first position of 1
    // and last position of 1
    else {
        distance = (last_1 - first_1);
        return distance;
    }
}
 
// Driver code
int main()
{
    int N = 131;
    cout << longest_gap(N) << endl;
 
    N = 8;
    cout << longest_gap(N) << endl;
 
    N = 17;
    cout << longest_gap(N) << endl;
 
    N = 33;
    cout << longest_gap(N) << endl;
 
    return 0;
}

// Java program to find the
// Maximum distance between two 1's
// in Binary representation of N
class GFG
{
    static int longest_gap(int N)
    {
        int distance = 0, count = 0,
            first_1 = -1, last_1 = -1;
     
        // Compute the binary representation
        while (N != 0)
        {
            count++;
     
            int r = N & 1;
     
            if (r == 1)
            {
                first_1 = first_1 == -1 ?
                                  count : first_1;
                last_1 = count;
            }
            N = N / 2;
        }
     
        // if N is a power of 2
        // then return -1
        if (last_1 <= first_1)
        {
            return -1;
        }
         
        // else find the distance
        // between the first position of 1
        // and last position of 1
        else
        {
            distance = (last_1 - first_1);
            return distance;
        }
    }
     
    // Driver code
    public static void main (String[] args)
    {
        int N = 131;
        System.out.println(longest_gap(N));
     
        N = 8;
        System.out.println(longest_gap(N));
     
        N = 17;
        System.out.println(longest_gap(N));
     
        N = 33;
        System.out.println(longest_gap(N));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 program to find the
# Maximum distance between two 1's
# in Binary representation of N
def longest_gap(N):
 
    distance = 0
    count = 0
    first_1 = -1
    last_1 = -1
 
    # Compute the binary representation
    while (N > 0):
        count += 1
 
        r = N & 1
 
        if (r == 1):
            if first_1 == -1:
                first_1 = count
            else:
                first_1 = first_1
 
            last_1 = count
 
        N = N // 2
 
    # if N is a power of 2
    # then return -1
    if (last_1 <= first_1):
        return -1
         
    # else find the distance
    # between the first position of 1
    # and last position of 1
    else:
        distance = last_1 - first_1
        return distance
 
# Driver code
N = 131
print(longest_gap(N))
 
N = 8
print(longest_gap(N))
 
N = 17
print(longest_gap(N))
 
N = 33
print(longest_gap(N))
 
# This code is contributed by Mohit Kumar

// C# program to find the
// Maximum distance between two 1's
// in Binary representation of N
using System;
 
class GFG
{
    static int longest_gap(int N)
    {
        int distance = 0, count = 0,
            first_1 = -1, last_1 = -1;
     
        // Compute the binary representation
        while (N != 0)
        {
            count++;
     
            int r = N & 1;
     
            if (r == 1)
            {
                first_1 = first_1 == -1 ?
                                  count : first_1;
                last_1 = count;
            }
            N = N / 2;
        }
     
        // if N is a power of 2
        // then return -1
        if (last_1 <= first_1)
        {
            return -1;
        }
         
        // else find the distance
        // between the first position of 1
        // and last position of 1
        else
        {
            distance = (last_1 - first_1);
            return distance;
        }
    }
     
    // Driver code
    public static void Main (String []args)
    {
        int N = 131;
        Console.WriteLine(longest_gap(N));
     
        N = 8;
        Console.WriteLine(longest_gap(N));
     
        N = 17;
        Console.WriteLine(longest_gap(N));
     
        N = 33;
        Console.WriteLine(longest_gap(N));
    }
}
 
// This code is contributed by Arnab Kundu

<script>
// Javascript program to find the
// Maximum distance between two 1's
// in Binary representation of N
 
function longest_gap(N)
{
 
    let distance = 0, count = 0,
        first_1 = -1, last_1 = -1;
 
    // Compute the binary representation
    while (N) {
 
        count++;
 
        let r = N & 1;
 
        if (r == 1) {
            first_1 = first_1 == -1
                          ? count
                          : first_1;
            last_1 = count;
        }
 
        N = parseInt(N / 2);
    }
 
    // if N is a power of 2
    // then return -1
    if (last_1 <= first_1) {
        return -1;
    }
    // else find the distance
    // between the first position of 1
    // and last position of 1
    else {
        distance = (last_1 - first_1);
        return distance;
    }
}
 
// Driver code
    let N = 131;
    document.write(longest_gap(N) + "<br>");
 
    N = 8;
    document.write(longest_gap(N) + "<br>");
 
    N = 17;
    document.write(longest_gap(N) + "<br>");
 
    N = 33;
    document.write(longest_gap(N) + "<br>");
 
</script>

7
-1
4
5

Complejidad de tiempo: O (log N)

Espacio Auxiliar: O(1)