Conteo de 1 después de voltear los bits en múltiplos de 1 a N

Dada la array binaria de tamaño N A[] que contiene todos los 0 inicialmente. La tarea es encontrar el conteo final de 1 después de voltear los bits en múltiplos de 1 a N.

Ejemplos:

Entrada: A[] = [0, 0, 0, 0]
Salida: 2
Explicación: 
Invertir bits en múltiplos de 1 – [1, 1, 1, 1]
Invertir bits en múltiplos de 2 – [1, 0, 1, 0]
Voltear bits en múltiplos de 3 – [1, 0, 0, 0]
Voltear bits en múltiplos de 4 – [1, 0, 0, 1] 
Por lo tanto, el recuento de 1 después del cambio final es 2.        

Entrada: A[] = [0, 0, 0, 0, 0, 0, 0]
Salida: 2
Explicación:
Invertir bits en múltiplos de 1 – [1, 1, 1, 1, 1, 1, 1]
Invertir bits en múltiplos de 2 – [1, 0, 1, 0, 1, 0, 1]
Cambiando bits en múltiplos de 3 – [1, 0, 0, 0, 1, 1, 1]
Cambiando bits en múltiplos de 4 – [ 1, 0, 0, 1, 1, 1, 1]
Invertir bits en múltiplos de 5 – [1, 0, 0, 1, 0, 1, 1]
Invertir bits en múltiplos de 6 – [1, 0, 0, 1, 0, 0, 1]
Voltear bits en múltiplos de 7 – [1, 0, 0, 1, 0, 0, 0]
Por lo tanto, el recuento de 1 después del cambio final es 2

Enfoque ingenuo: la idea básica de la solución se basa en un enfoque codicioso . 

Para cada elemento del 1 al N, voltea todos los elementos en sus múltiplos. La cuenta final de 1 en la array es la respuesta.

Siga los pasos a continuación para implementar el enfoque:

• Cree una array de tamaño N y rellénela con 0.
• Ejecute un ciclo i = 1 a i = N, y para cada i,
  • ejecutar un ciclo j = i – 1 a N con incremento = i.
    • Da la vuelta a los bits en cada j .
• Iterar sobre la array y calcular el número de 1.

La implementación del enfoque discutido anteriormente se da a continuación.

// C++ code to implement the approach
#include <iostream>
using namespace std;
 
// Function to calculate number of 1
// in the final array
int findOnes(int N, int arr[])
{
    int count = 0;
 
    // Loop to flip the elements
    // at multiples of i
    for (int i = 1; i <= N; i++) {
        for (int j = i - 1; j < N; j += i) {
            if (arr[j] == 0)
                arr[j] = 1;
            else
                arr[j] = 0;
        }
    }
 
    // Loop to determine 1s at final array
    for (int i = 0; i < N; i++) {
        if (arr[i] == 1)
            count++;
    }
 
    return count;
}
 
// Driver Code
int main()
{
    int N = 4;
    int arr[N];
 
    for (int i = 0; i < N; i++)
        arr[i] = 0;
 
    int count = findOnes(N, arr);
    cout << count;
 
    return 0;
}

// Java code to implement the approach
import java.io.*;
 
class GFG {
 
  // Function to calculate number of 1
  // in the final array
  static int findOnes(int N, int arr[])
  {
    int count = 0;
 
    // Loop to flip the elements
    // at multiples of i
    for (int i = 1; i <= N; i++) {
      for (int j = i - 1; j < N; j += i) {
        if (arr[j] == 0)
          arr[j] = 1;
        else
          arr[j] = 0;
      }
    }
 
    // Loop to determine 1s at final array
    for (int i = 0; i < N; i++) {
      if (arr[i] == 1)
        count++;
    }
 
    return count;
  }
 
  // Driver Code
  public static void main (String[] args) {
    int N = 4;
    int[] arr = new int[N];
 
    for (int i = 0; i < N; i++)
      arr[i] = 0;
 
    int count = findOnes(N, arr);
    System.out.println(count);
  }
}
 
// This code is contributed by hrithikgarg03188.

# Python code to implement the approach
 
# Function to calculate number of 1
# in the final array
def findOnes(N, arr):
    count = 0
 
    # Loop to flip the elements
    # at multiples of i
    for i in range(1, N + 1):
        for j in range(i - 1, N, i):
            if (arr[j] == 0):
                arr[j] = 1
            else:
                arr[j] = 0
 
    # Loop to determine 1s at final array
    for i in range(N):
        if (arr[i] == 1):
            count += 1
 
    return count
 
# Driver Code
N = 4
arr = [0]*N
 
for i in range(N):
    arr[i] = 0
 
count = findOnes(N, arr)
print(count)
 
# This code is contributed by shinjanpatra

// C# code to implement the approach
using System;
 
class GFG {
 
  // Function to calculate number of 1
  // in the final array
  static int findOnes(int N, int[] arr)
  {
    int count = 0;
 
    // Loop to flip the elements
    // at multiples of i
    for (int i = 1; i <= N; i++) {
      for (int j = i - 1; j < N; j += i) {
        if (arr[j] == 0)
          arr[j] = 1;
        else
          arr[j] = 0;
      }
    }
 
    // Loop to determine 1s at final array
    for (int i = 0; i < N; i++) {
      if (arr[i] == 1)
        count++;
    }
 
    return count;
  }
 
  // Driver Code
  public static void Main()
  {
    int N = 4;
    int[] arr = new int[N];
 
    for (int i = 0; i < N; i++)
      arr[i] = 0;
 
    int count = findOnes(N, arr);
    Console.WriteLine(count);
  }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
 
// JavaScript code to implement the approach
 
// Function to calculate number of 1
// in the final array
function findOnes(N, arr)
{
    let count = 0;
 
    // Loop to flip the elements
    // at multiples of i
    for (let i = 1; i <= N; i++) {
        for (let j = i - 1; j < N; j += i) {
            if (arr[j] == 0)
                arr[j] = 1;
            else
                arr[j] = 0;
        }
    }
 
    // Loop to determine 1s at final array
    for (let i = 0; i < N; i++) {
        if (arr[i] == 1)
            count++;
    }
 
    return count;
}
 
// Driver Code
 
let N = 4;
let arr = new Array(N);
 
for (let i = 0; i < N; i++)
    arr[i] = 0;
 
let count = findOnes(N, arr);
document.write(count);
 
// This code is contributed by shinjanpatra
 
</script>

2

Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)

Enfoque eficiente: El enfoque eficiente para resolver este problema se basa en la siguiente observación matemática:

Después de voltear todos los bits en múltiplos de números en el rango de 1 a N, solo quedarán 1 de piso (√N) . 

Esta relación se puede probar como se muestra a continuación:

Inicialmente, todos los elementos son 0. 

Lema 1: En cualquier índice i, el elemento final será 1 si se voltea un número impar de veces. Esto es trivial.

Lema 2: para cualquier índice i, el número de veces que se lanzará el elemento en ese índice es igual al número de factores de esa moneda.
Dado que volteamos elementos en múltiplos de 1, 2, 3, 4, … N. Para cada factor de cualquier índice i, se volteará. 

Lema 3: A partir del Lema 1 y Lema 2, todos los índices con número impar de factores tendrán como elemento final el 1.
Para cualquier número natural N, podemos escribirlo en su forma de factorización prima:

• norte = α ^un X β ^segundo X γ ^C X δ ^re ….
  donde α < β < γ < δ …. son números primos y a, b, c, d son números enteros.
• Entonces, número total de factores de N = (a+1) x (b+1) x (c+1) x (d+1) x …
• Por lo tanto, queremos que ((a+1) x (b+1) x (c+1) x (d+1) x …) sea impar .
• => ((a+1) x (b+1) x (c+1) x (d+1) x …) es impar si (a+1) x (b+1) x (c+1) x (d+1) x … es impar
  => (a+1) x (b+1) x (c+1) x (d+1) x … es impar si (a+1), (b+1) , (c+1), (d+1) … es impar
  => (a+1), (b+1), (c+1), (d+1) es impar si a, b, c, d , …. incluso
• Por lo tanto, N = α ^a x β ^b x γ ^c x δ ^d …. should tiene a, b, c, d, … como números enteros pares. Esto solo es posible si N es un cuadrado perfecto .

Por tanto, todos los índices que sean cuadrados perfectos tendrán el 1 como elemento final.

Número de cuadrados perfectos debajo de N = ⌊√N⌋ 

La implementación de la observación discutida anteriormente se da a continuación.

// C++ code to implement the approach
#include <cmath>
#include <iostream>
using namespace std;
 
// Function to count number of 1's
// in final array
int findOnes(int N, int arr[])
{
    return floor(sqrt(N));
}
 
// Driver Code
int main()
{
    int N = 4;
    int arr[] = { 0, 0, 0, 0 };
 
    int count = findOnes(N, arr);
    cout << count;
 
    return 0;
}

// JAVA code to implement the approach
import java.util.*;
class GFG
{
 
  // Function to count number of 1's
  // in final array
  public static int findOnes(int N, int arr[])
  {
    return (int)Math.floor((int)Math.sqrt(N));
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int N = 4;
    int arr[] = new int[] { 0, 0, 0, 0 };
 
    int count = findOnes(N, arr);
    System.out.print(count);
  }
}
 
// This code is contributed by Taranpreet

// C# code to implement the approach
using System;
class GFG {
 
    // Function to count number of 1's
    // in final array
    static int findOnes(int N, int[] arr)
    {
        return (int)(Math.Floor(Math.Sqrt(N)));
    }
 
    // Driver Code
    public static void Main()
    {
        int N = 4;
        int[] arr = { 0, 0, 0, 0 };
 
        int count = findOnes(N, arr);
        Console.Write(count);
    }
}
 
// This code is contributed by Samim Hossain Mondal.

<script>
// Javascript code to implement the approach
 
// Function to count number of 1's
// in final array
function findOnes(N, arr)
{
    return Math.floor(Math.sqrt(N));
}
 
// Driver Code
let N = 4;
let arr = [ 0, 0, 0, 0 ];
 
let count = findOnes(N, arr);
document.write(count);
 
// This code is contributed by Samim Hossain Mondal.
</script>

# Python code to implement the approach
 
# Function to count number of 1's
# in final array
import math
 
 
def findOnes(N, arr):
 
    return math.floor(math.sqrt(N))
 
 
# Driver Code
N = 4
arr = [ 0, 0, 0, 0 ]
 
count = findOnes(N, arr)
print(count)
 
# This code is contributed by shinjanpatra

2

Tiempo Complejidad: O(1)
Espacio Auxiliar: O(1)