Enésimo término de la serie de funciones de la regla

Dado un entero positivo N , la tarea es encontrar el ^término N de la serie de funciones de la regla .

La serie de funciones de la regla es una serie que tiene 1 como primer término y se forma realizando las siguientes dos operaciones:

• Agregue el entero positivo más pequeño que no esté presente en la serie.
• Luego, agregue todos los números antes del último número.

Ejemplos:

Entrada: N = 5
Salida: 1
Explicación: La serie de funciones de la regla viene dada por {1, 2, 1, 3, 1, 2, 1, 4, ….. }. Por lo tanto, el quinto ^término de la serie es 1.

Entrada: N = 8
Salida:  4

Enfoque ingenuo: El enfoque más simple para resolver el problema dado es generar la serie hasta el N- ^ésimo término y luego imprimir el N- ^ésimo término. 

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Enfoque eficiente: el enfoque anterior también se puede optimizar en función de la siguiente observación de que el ^elemento N en la serie de funciones de la regla es igual al número de bits establecidos en (N^(N – 1)) como se ilustra a continuación:

• Número de bits establecidos en el XOR bit a bit de 0 y 1 = 1
• Número de bits establecidos en el XOR bit a bit de 1 y 2 = 2
• Número de bits establecidos en el XOR bit a bit de 2 y 3 = 1
• Número de bits establecidos en el XOR bit a bit de 3 y 4 = 3
• Número de bits establecidos en el XOR bit a bit de 4 y 5 = 1
• Número de bits establecidos en el XOR bit a bit de 5 y 6 = 2
• Número de bits establecidos en el XOR bit a bit de 6 y 7 = 1
• Número de bits establecidos en el XOR bit a bit de 7 y 8 = 4
• y así…

Por lo tanto, a partir de las observaciones anteriores, el ^término N de la serie de funciones de la regla viene dado por el XOR bit a bit de N y (N – 1) . 

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count the number
// of set bits in the number N
int setBits(long n)
{
    // Store the number of setbits
    int count = 0;
 
    while (n > 0) {
 
        // Update the value of n
        n = n & (n - 1);
 
        // Update the count
        count++;
    }
 
    // Return the total count
    return count;
}
 
// Function to find the Nth term of
// the Ruler Function Series
void findNthTerm(int N)
{
    // Store the result
    int x = setBits(N ^ (N - 1));
 
    // Print the result
    cout << x;
}
 
// Driver Code
int main()
{
    int N = 8;
    findNthTerm(N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG{
 
// Function to count the number
// of set bits in the number N
static int setBits(long n)
{
     
    // Store the number of setbits
    int count = 0;
 
    while (n > 0)
    {
         
        // Update the value of n
        n = n & (n - 1);
 
        // Update the count
        count++;
    }
 
    // Return the total count
    return count;
}
 
// Function to find the Nth term of
// the Ruler Function Series
static void findNthTerm(int N)
{
     
    // Store the result
    int x = setBits(N ^ (N - 1));
 
    // Print the result
    System.out.println(x);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 8;
     
    findNthTerm(N);
}
}
 
// This code is contributed by Kingash

# Python3 program for the above approach
 
# Function to count the number
# of set bits in the number N
def setBits(n):
     
    # Store the number of setbits
    count = 0
 
    while (n > 0):
         
        # Update the value of n
        n = n & (n - 1)
 
        # Update the count
        count += 1
         
    # Return the total count
    return count
 
# Function to find the Nth term of
# the Ruler Function Series
def findNthTerm(N):
     
    # Store the result
    x = setBits(N ^ (N - 1))
 
    # Print the result
    print(x)
 
# Driver Code
N = 8
 
findNthTerm(N)
 
# This code is contributed by Ankita saini

// C# program for the above approach
using System;
class GFG {
 
    // Function to count the number
    // of set bits in the number N
    static int setBits(long n)
    {
 
        // Store the number of setbits
        int count = 0;
 
        while (n > 0) {
 
            // Update the value of n
            n = n & (n - 1);
 
            // Update the count
            count++;
        }
 
        // Return the total count
        return count;
    }
 
    // Function to find the Nth term of
    // the Ruler Function Series
    static void findNthTerm(int N)
    {
 
        // Store the result
        int x = setBits(N ^ (N - 1));
 
        // Print the result
        Console.WriteLine(x);
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int N = 8;
 
        findNthTerm(N);
    }
}
 
// This code is contributed by ukasp.

<script>
 
// Javascript program for the above approach
 
// Function to count the number
// of set bits in the number N
function setBits(n)
{
     
    // Store the number of setbits
    var count = 0;
 
    while (n > 0)
    {
         
        // Update the value of n
        n = n & (n - 1);
 
        // Update the count
        count++;
    }
 
    // Return the total count
    return count;
}
 
// Function to find the Nth term of
// the Ruler Function Series
function findNthTerm(N)
{
     
    // Store the result
    var x = setBits(N ^ (N - 1));
 
    // Print the result
    document.write(x);
}
 
// Driver code
var N = 8;
     
findNthTerm(N);
 
// This code is contributed by Khushboogoyal499
 
</script>

4

Complejidad temporal: O(log N)
Espacio auxiliar: O(1)