Dada una array de tamaño N en la que inicialmente todos los elementos son 0 (cero). La tarea es contar el número de 1 en la array después de realizar N movimientos en la array como se explica:
En cada movimiento (comenzando de 1 a N) el elemento en la posición del múltiplo del número de movimiento cambia de 0 a 1 o 1 a 0.
Mover 1 : cambia el elemento en la posición 1, 2, 3,…
Mover 2 : cambia el elemento en la posición 2, 4, 6,…
Mover 3 : cambia el elemento en la posición 3, 6, 9, …
Cuenta los elementos cuyo valor es 1 después de realizar N movimientos.
Nota : considere que la array está indexada en 1.
Ejemplo:
Entrada : N = 5, arr[] = {0, 0, 0, 0, 0}
Salida : 2
Explicación :
Mover 1: {1, 1, 1, 1, 1}
Mover 2: {1, 0, 1, 0, 1}
Mover 3: {1, 0, 0, 0, 1}
Mover 4: {1, 0, 0, 1, 1}
Mover 5: {1, 0, 0, 1, 0}
Números totales de 1 después de 5 movimientos = 2.Entrada : N = 10, arr[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Salida : 3
Enfoque ingenuo: iterar por el número de movimientos y, para cada movimiento, recorrer los elementos desde el número de movimiento hasta N y verificar si la posición es múltiplo del número de movimiento o no. Si es múltiplo del número de movimiento, cambie el elemento en esa posición, es decir, si es 0, cámbielo a 1 y si es 1, cámbielo a 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count number of 1's in the
// array after performing N moves
int countOnes(int arr[], int N)
{
for (int i = 1; i <= N; i++) {
for (int j = i; j <= N; j++) {
// If index is multiple of move number
if (j % i == 0) {
if (arr[j - 1] == 0)
arr[j - 1] = 1; // Convert 0 to 1
else
arr[j - 1] = 0; // Convert 1 to 0
}
}
}
int count = 0;
// Count number of 1's
for (int i = 0; i < N; i++)
if (arr[i] == 1)
count++; // count number of 1's
return count;
}
// Driver Code
int main()
{
int N = 10; // Initialize array size
// Initialize all elements to 0
int arr[10] = { 0 };
int ans = countOnes(arr, N);
cout << ans;
return 0;
}
Java
// Java implementation of the above approach
class GFG
{
// Function to count number of 1's in the
// array after performing N moves
static int countOnes(int arr[], int N)
{
for (int i = 1; i <= N; i++)
{
for (int j = i; j <= N; j++)
{
// If index is multiple of move number
if (j % i == 0)
{
if (arr[j - 1] == 0)
{
arr[j - 1] = 1; // Convert 0 to 1
}
else
{
arr[j - 1] = 0; // Convert 1 to 0
}
}
}
}
int count = 0;
// Count number of 1's
for (int i = 0; i < N; i++)
{
if (arr[i] == 1)
{
count++; // count number of 1's
}
}
return count;
}
// Driver Code
public static void main(String[] args)
{
int N = 10; // Initialize array size
// Initialize all elements to 0
int arr[] = new int[10];
int ans = countOnes(arr, N);
System.out.println(ans);
}
}
// This code contributed by Rajput-Ji
Python3
# Python3 implementation of the above approach # Function to count number of 1's in the # array after performing N moves def countOnes(arr, N): for i in range(1, N + 1, 1): for j in range(i, N + 1, 1): # If index is multiple of move number if (j % i == 0): if (arr[j - 1] == 0): arr[j - 1] = 1 # Convert 0 to 1 else: arr[j - 1] = 0 # Convert 1 to 0 count = 0 # Count number of 1's for i in range(N): if (arr[i] == 1): count += 1 # count number of 1's return count # Driver Code if __name__ == '__main__': N = 10 # Initialize array size # Initialize all elements to 0 arr = [0 for i in range(10)] ans = countOnes(arr, N) print(ans) # This code is contributed by # Surendra_Gangwar
C#
// C# implementation of the above approach
using System;
class GFG
{
// Function to count number of 1's in the
// array after performing N moves
static int countOnes(int []arr, int N)
{
for (int i = 1; i <= N; i++)
{
for (int j = i; j <= N; j++)
{
// If index is multiple of move number
if (j % i == 0)
{
if (arr[j - 1] == 0)
{
arr[j - 1] = 1; // Convert 0 to 1
}
else
{
arr[j - 1] = 0; // Convert 1 to 0
}
}
}
}
int count = 0;
// Count number of 1's
for (int i = 0; i < N; i++)
{
if (arr[i] == 1)
{
count++; // count number of 1's
}
}
return count;
}
// Driver Code
public static void Main(String[] args)
{
int N = 10; // Initialize array size
// Initialize all elements to 0
int []arr = new int[10];
int ans = countOnes(arr, N);
Console.WriteLine(ans);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation of the above approach
// Function to count number of 1's in the
// array after performing N moves
function countOnes(arr, N)
{
for(let i = 1; i <= N; i++)
{
for(let j = i; j <= N; j++)
{
// If index is multiple of move number
if (j % i == 0)
{
if (arr[j - 1] == 0)
// Convert 0 to 1
arr[j - 1] = 1;
else
// Convert 1 to 0
arr[j - 1] = 0;
}
}
}
let count = 0;
// Count number of 1's
for(let i = 0; i < N; i++)
if (arr[i] == 1)
// count number of 1's
count++;
return count;
}
// Driver Code
// Initialize array size
let N = 10;
// Initialize all elements to 0
let arr = new Uint8Array(10);
let ans = countOnes(arr, N);
document.write(ans);
// This code is contributed by Mayank Tyagi
</script>
3
Complejidad del Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: El enfoque eficiente se basa en un enfoque codicioso. Básicamente se basa en el siguiente patrón.
Mientras hacemos esto para N = 1, 2, 3, 4, 5,… se encuentra que la respuesta requerida es el número total de cuadrados perfectos de 1 a n (ambos inclusive).
Por lo tanto, Respuesta = Número total de cuadrados perfectos de 1 a N
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count number of perfect squares
int perfectSquares(int a, int b)
{
// Counting number of perfect squares
// between a and b
return (floor(sqrt(b)) - ceil(sqrt(a)) + 1);
}
// Function to count number of 1s in
// array after N moves
int countOnes(int arr[], int n)
{
return perfectSquares(1, n);
}
// Driver Code
int main()
{
// Initialize array size
int N = 10;
// Initialize all elements to 0
int arr[10] = { 0 };
cout << countOnes(arr, N);
return 0;
}
Java
// Java implementation of the above approach
import java.io.*;
class GFG {
// Function to count number of perfect squares
static double perfectSquares(int a, int b)
{
// Counting number of perfect squares
// between a and b
return (Math.floor(Math.sqrt(b)) - Math.ceil(Math.sqrt(a)) + 1);
}
// Function to count number of 1s in
// array after N moves
static double countOnes(int arr[], int n)
{
return perfectSquares(1, n);
}
// Driver Code
public static void main(String[] args)
{
// Initialize array size
int N = 10;
// Initialize all elements to 0
int arr[] = { 0 };
System.out.println(countOnes(arr, N));
}
}
// This code is contributed by jit_t.
Python3
# Python3 implementation of the above approach from math import sqrt, ceil, floor; # Function to count number of perfect squares def perfectSquares(a, b) : # Counting number of perfect squares # between a and b return (floor(sqrt(b)) - ceil(sqrt(a)) + 1); # Function to count number of 1s in # array after N moves def countOnes(arr, n) : return perfectSquares(1, n); # Driver Code if __name__ == "__main__" : # Initialize array size N = 10; # Initialize all elements to 0 arr = [0] * 10; print(countOnes(arr, N)); # This code is contributed by Ankit Rai
C#
// C# implementation of the above approach
using System;
class GFG {
// Function to count number of perfect squares
static double perfectSquares(int a, int b)
{
// Counting number of perfect squares
// between a and b
return (Math.Floor(Math.Sqrt(b)) - Math.Ceiling(Math.Sqrt(a)) + 1);
}
// Function to count number of 1s in
// array after N moves
static double countOnes(int[] arr, int n)
{
return perfectSquares(1, n);
}
// Driver Code
static public void Main()
{
// Initialize array size
int N = 10;
// Initialize all elements to 0
int[] arr = { 0 };
Console.WriteLine(countOnes(arr, N));
}
}
// This code is contributed by JitSalal.
PHP
<?php
// PHP implementation of the above approach
// Function to count number of perfect squares
function perfectSquares($a, $b)
{
// Counting number of perfect squares
// between a and b
return (floor(sqrt($b)) - ceil(sqrt($a)) + 1);
}
// Function to count number of 1s in
// array after N moves
function countOnes($arr, $n)
{
return perfectSquares(1, $n);
}
// Driver Code
// Initialize array size
$N = 10;
// Initialize all elements to 0
$arr[10] = array(0);
echo countOnes($arr, $N);
// This code is contributed by jit_t
?>
Javascript
<script>
// javascript implementation of the above approach
// Function to count number of perfect squares
function perfectSquares(a, b)
{
// Counting number of perfect squares
// between a and b
return (Math.floor(Math.sqrt(b)) - Math.ceil(Math.sqrt(a)) + 1);
}
// Function to count number of 1s in
// array after N moves
function countOnes(arr , n)
{
return perfectSquares(1, n);
}
// Driver Code
// Initialize array size
var N = 10;
// Initialize all elements to 0
var arr = [ 0 ];
document.write(countOnes(arr, N));
// This code is contributed by aashish1995
</script>
3
Complejidad del tiempo: O(log(log N))