Count number of 1s in the array after N moves

0 0 7 minutes read

Given an array of size N in which initially all the elements are 0(zero). The task is to count the number of 1’s in the array after performing N moves on the array as explained:
In each move (starting from 1 to N) the element at the position of the multiple of the move number is changed from 0 to 1 or 1 to 0.
Move 1: Change the element at position at 1, 2, 3, …
Move 2: Change the element at position at 2, 4, 6, …
Move 3: Change the element at position at 3, 6, 9, …
Count the elements whose value is 1 after performing N moves.

Note: Consider that the array is 1-indexed.

Example:
Input: N = 5, arr[] = {0, 0, 0, 0, 0}
Output: 2
Explanation:
Move 1: {1, 1, 1, 1, 1}
Move 2: {1, 0, 1, 0, 1}
Move 3: {1, 0, 0, 0, 1}
Move 4: {1, 0, 0, 1, 1}
Move 5: {1, 0, 0, 1, 0}
Total numbers of 1’s after 5 moves = 2.

Input: N = 10, arr[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Output: 3

Naive approach: Iterate for the number of moves and for each move traverse the elements from Move number to N and check whether the position is multiple of move number or not. If it is multiple of move number then change the element at that position i.e. If it is 0 change it to 1 and if it is 1 change it to 0.

Below is the implementation of above approach:

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>

Output:

Time Complexity: O(N²)
Auxiliary Space: O(1)

Efficient Approach: The efficient approach is based on a greedy approach. It is basically based on the below pattern.
While we do this for N = 1, 2, 3, 4, 5, … it is found that the answer required is the total number of perfect squares from 1 to n (both inclusive).
Hence, Answer = Total number of perfect squares from 1 to N

Below is the implementation of the above approach:

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>

Output:

Time Complexity: O(log(log N))
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!