Javascript program to count 1's in sorted binary array
We have two ways to count 1's in a sorted binary array. The first is to iterate over the array and count the number of 1's. The second method is to use the binary search algorithm to find the first occurrence of 1 in the array.
It should be noted that in order to use these methods, the array must be sorted.
In this blog post, we will discuss a JavaScript program to count the number of 1’s in a sorted binary array. We will also look at some edge cases and optimization techniques to make the program more efficient.
Problem Statement
Given a sorted binary array, the task is to count the number of 1's in the array. Arrays can be of any size and their elements can only be 0 or 1.
enter
bin_array[] = {0, 0, 0,1,1,1}
Output
3
method 1
The first method that comes to mind is to iterate over the array and count the number of 1's.
Initialize a count variable to store the number in the array.
Iterate over the array and check each element. If the current element is equal to 1, increment the counter.
Example
<html>
<body>
<p id="result1"></p>
<p id="result2"></p>
<script>
function count_num_of_Ones( bin_array,n) {
let num_of_ones=0;
for (let ind = 0; ind < n; ind++) {
if(bin_array[ind]==1){
num_of_ones++;
}
}
return num_of_ones;
}
let bin_array = [0,0,0,1,1,1];
let n = bin_array.length;
document.getElementById("result1").innerHTML = "Original Array: " + JSON.stringify(bin_array);
document.getElementById("result2").innerHTML = "Count of 1's in given array is " + count_num_of_Ones(bin_array,n)
</script>
</body>
</html>
However, the time complexity of this method is O(n), where n is the size of the array, since we want to iterate through the entire array once.
This can be optimized by taking advantage of the fact that the array is sorted.
Method 2
To find the first instance of 1 in an array, use the binary search method. Simply subtract the index of the first 1 instance from the total number of items in the array to get the number of 1's.
In this implementation, we use the "first occurrence" binary search technique to find the first instance of 0 in the array.
The low and high variables are initially set to the first and last index of the array, respectively.
The number of items in the array is also specified as the value of a variable named firstOne, which will be used to record the index of the first instance of the number 1.
The while loop will continue to run until the low index is greater than or equal to the high index. After each iteration, we determine the midpoint of the current range.
If the middle element is 1, update the firstOne variable and move the high index to the earlier element. If the element at the midpoint is 0, we move the lower index to the subsequent element.
After the while loop completes, we check if the first variable corresponds to the -1 value of the array. If it is, it means there is no 1 in the array, so 1 is returned. If not, return firstOne minus arr.length.
Example
<html>
<body>
<p id="result1"></p>
<p id="result2"></p>
<script>
function count_num_of_Ones(bin_arr,low,high) {
var low = 0;
var high = bin_arr.length - 1;
var firstOne = -1;
while (low <= high) {
var mid = Math.floor((low + high) / 2);
if (bin_arr[mid] == 1) {
firstOne = mid;
high = mid -1;
} else {
low = mid + 1;
}
}
return firstOne == -1 ? 0 : bin_arr.length - firstOne;
}
let bin_array = [0,0,0,1,1,1,1];
let n = bin_array.length;
document.getElementById("result1").innerHTML = "Original Array: " + JSON.stringify(bin_array);
document.getElementById("result2").innerHTML = "Count of 1's in given array is " + count_num_of_Ones(bin_array,n)
</script>
</body>
</html>
The time complexity of this method is O(log n), which is much more efficient than the previous method.
In this tutorial, we discussed a JavaScript program to count the number of 1's in a sorted binary array.
The above is the detailed content of Javascript program to count 1's in sorted binary array. For more information, please follow other related articles on the PHP Chinese website!
Hot AI Tools
Undresser.AI Undress
AI-powered app for creating realistic nude photos
AI Clothes Remover
Online AI tool for removing clothes from photos.
Undress AI Tool
Undress images for free
Clothoff.io
AI clothes remover
Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!
Hot Article
Hot Tools
Notepad++7.3.1
Easy-to-use and free code editor
SublimeText3 Chinese version
Chinese version, very easy to use
Zend Studio 13.0.1
Powerful PHP integrated development environment
Dreamweaver CS6
Visual web development tools
SublimeText3 Mac version
God-level code editing software (SublimeText3)
Hot Topics
1386
52
What should I do if I encounter garbled code printing for front-end thermal paper receipts?
Apr 04, 2025 pm 02:42 PM
Frequently Asked Questions and Solutions for Front-end Thermal Paper Ticket Printing In Front-end Development, Ticket Printing is a common requirement. However, many developers are implementing...
Who gets paid more Python or JavaScript?
Apr 04, 2025 am 12:09 AM
There is no absolute salary for Python and JavaScript developers, depending on skills and industry needs. 1. Python may be paid more in data science and machine learning. 2. JavaScript has great demand in front-end and full-stack development, and its salary is also considerable. 3. Influencing factors include experience, geographical location, company size and specific skills.
How to merge array elements with the same ID into one object using JavaScript?
Apr 04, 2025 pm 05:09 PM
How to merge array elements with the same ID into one object in JavaScript? When processing data, we often encounter the need to have the same ID...
Demystifying JavaScript: What It Does and Why It Matters
Apr 09, 2025 am 12:07 AM
JavaScript is the cornerstone of modern web development, and its main functions include event-driven programming, dynamic content generation and asynchronous programming. 1) Event-driven programming allows web pages to change dynamically according to user operations. 2) Dynamic content generation allows page content to be adjusted according to conditions. 3) Asynchronous programming ensures that the user interface is not blocked. JavaScript is widely used in web interaction, single-page application and server-side development, greatly improving the flexibility of user experience and cross-platform development.
The difference in console.log output result: Why are the two calls different?
Apr 04, 2025 pm 05:12 PM
In-depth discussion of the root causes of the difference in console.log output. This article will analyze the differences in the output results of console.log function in a piece of code and explain the reasons behind it. �...
How to achieve parallax scrolling and element animation effects, like Shiseido's official website?
or:
How can we achieve the animation effect accompanied by page scrolling like Shiseido's official website?
Apr 04, 2025 pm 05:36 PM
Discussion on the realization of parallax scrolling and element animation effects in this article will explore how to achieve similar to Shiseido official website (https://www.shiseido.co.jp/sb/wonderland/)...
Can PowerPoint run JavaScript?
Apr 01, 2025 pm 05:17 PM
JavaScript can be run in PowerPoint, and can be implemented by calling external JavaScript files or embedding HTML files through VBA. 1. To use VBA to call JavaScript files, you need to enable macros and have VBA programming knowledge. 2. Embed HTML files containing JavaScript, which are simple and easy to use but are subject to security restrictions. Advantages include extended functions and flexibility, while disadvantages involve security, compatibility and complexity. In practice, attention should be paid to security, compatibility, performance and user experience.
How to implement panel drag and drop adjustment function similar to VSCode in front-end development?
Apr 04, 2025 pm 02:06 PM
Explore the implementation of panel drag and drop adjustment function similar to VSCode in the front-end. In front-end development, how to implement VSCode similar to VSCode...
