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 movesint 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 Codeint 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 approachclass 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 movesdef 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 Codeif __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 approachusing 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 movesfunction 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 sizelet N = 10; // Initialize all elements to 0let arr = new Uint8Array(10);let ans = countOnes(arr, N);document.write(ans);// This code is contributed by Mayank Tyagi </script> |
Output:
3
Time Complexity: O(N2)
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 squaresint 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 movesint countOnes(int arr[], int n){ return perfectSquares(1, n);}// Driver Codeint 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 approachimport 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 approachusing 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 squaresfunction 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 movesfunction 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:
3
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
