Christmas Event Website Template Free Download – Website Design – HTML – CSS Tutorial
Again starting from the rightmost 1 and subtracting the rest we get:
1010-10 = 1000 (or 10-2 = 8 in decimal system)
I will keep subtracting like this until I get zero.
1000-1000=0 (or 8-8=0 in decimal system)
Note that the useful 3 indices for 11 are 11,10,8 we get by subtracting the power of 2! 13 or 1101 in binary and then see the solution below:
1101-1=1100 (or 13-1=12 in decimal system)
1100-100 = 1000 (or 12-4 = 8 in decimal system)
1000-1000=0 (or 8-8=0 in decimal system)
Useful index 13,12,8 for 13 have been found!
Christmas Event Website Template Free Download – Website Design – HTML – CSS Tutorial
Now the question is how to do this in the code? A loop can be done checking one bit at a time but the work can be done in O(1). The index after the idx number index will be:
idx=idx – (idx & -idx)
To understand how it works, look at subtraction in the book before reading my explanation! I am giving an example, say idx=10 or 1010 in binary. Then in 2’s complement method -idx or -10 will be 0101+1=0110. (For those who have forgotten, to get the 2’s complement, you need to flip the bits and add 1.) Now if we do a bitwise AND, we get:
1010
0110
——-
0010
Got the rest of the 1 from the right! Now subtract it and the work is done. Why is it working? We can divide the binary number into 3 parts x1z. 1 is the rightmost 1, x is any bit before it, z is the o bit after the 1 (x or z is the zero, one or more bits. Now if we reverse the bits we get: x’0z’. The bits in x or z I got x’ and z’ by inverting, that means z’ is some 1 bit. If we add 1 to find out 2’s complement, we get: x’1z. Now if we AND the previous numbers x1z and x’1z, we get 1z. The part of x is all zero. So drop that in. Then we get the remainder from 1 to the right!
The code is then very simple:
How to do the update operation? Which index after 1010 or 10 will cover 10? Now we shift the rightmost 1 to the left. Adding 10 to 1010 gives 1100 or 12 which covers the whole 10. Similarly adding 100 to 12 or 1100 gives 10000 which covers the whole of 12. Figure out how it works!
Christmas Event Website Template Free Download – Website Design – HTML – CSS Tutorial
As before, just adding to the minus will move the rightmost 1 to the left. That means the number we are adding, a larger number will be subtracted from the new index during the query so the new index must cover the previous one! The code would be like this:
This is a binary indexed tree. Now we can easily update any index and sum from 1 to any index.
Complexity:
Adding or subtracting powers of 2 in all update and query cases, starting with the lower power and subtracting the higher power. So the time complexity will be O(log×n)
. All operations are performed on Tree array only, space complexity is O(n).
.
Note that this problem can be done with a segment tree, but it takes much less memory and the code is much smaller. However, in the segment tree, all ranges can be updated, here the range with index number 1 can be updated.
Problem 1: Query time i
from j
What to do if asked to find the sum of subarrays between indexes?
Problem 2: If it is said in the query that going to the lowest index of the array will get the sum more than X, then how to find the index? Hints: O(logn*logn).
Some problems from online jazz:
Curious Robin Hood
Inversion Count
Nice Day
I intend to write about 2D binary indexed trees and other problems in the future. That’s it for today. Happy Coding!
A Handout in Graph Theory 10: Floyd Warshall
Floyd Warshall is probably the smallest graph algorithm ever, written in just 3 lines! But this 3 line algorithm has a lot to understand. Floyd Warshall’s task is to find the shortest distance from each node in the graph to all other nodes. Such an algorithm is called the “all-pair shortest path” algorithm. Before reading this article you should know about adjacency matrix.
We can easily understand the algorithm by doing some simulation on a graph. See the image below:
Figure shows a weighted directed graph of four nodes. And in the upper right corner is a matrix. The weight or cost of the u-v edge is placed in the u,vth cell of the matrix. In those rooms which do not have a direct edge between them, Asim or Infinity is placed. And Konakuni houses value 0 because there is no distance to go from one’s own house to one’s own house!
Now suppose we take the node number “2” as the “middle node”. We will call the middle node k. So now k=2. (We will treat all nodes one by one as intermediate nodes, this can be done in any order)
Now take any pair of nodes (i,j). Let i=1, v=3. We want to go from u to v, leaving node k in between. Then we need to go from i to k, then from k to j. But why do we go like this if not profitable? We leave k in between only if the total cost decreases. Current distance from 1 to 3 is matrix[1][3]=infinity. And if we put k=2 in the middle then the distance will be matrix[1][2] + matrix[2][3] = 3 +2 = 5. That means the cost is decreasing! We can update the graph like this:
We went from 1 to 3 using 2 as the “middle node” at a total cost of 5. In the graph, we can directly give an edge from 1 to 3 at a cost of 5.
Now again assume i=2, j=4. And k=2 as before. Now matrix[2][4]=infinity. Meanwhile matrix[2][2] + matrix[2][4] = 0 + infinity. But this time the distance did not decrease. So there is no need to update the graph. Surely you understand the update condition will be like this:
if(matrix[i][k] + matrix[k][j] < matrix[i][j])
matrix[i][j] = matrix[i][k] + matrix[k][j]
Or we can write in one line:
matrix[i][j] = min(matrix[i][j] , matrix[i][k] + matrix[k][j])
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
Free Website Create – HTML CSS, PHP, JavaScript Programming Projects For Free
Follow Us
Thank You,
Before Download
You must Join our Facebook Group and Subscribe YouTube Channel
FreeWebsiteCreate.net tries to provide HTML, CSS, SCSS, JavaScript, React, Android Studio, Java, PHP, Laravel, Python, Django, C#(C Sharp), and ASP.net-related projects 100% free. We try to make learning easier. Free Website Create always tries to give free projects to new learners. Free projects and source code will help to learn quickly.
They can save time and learn more. In this post, we share a free portfolio project website code with HTML and CSS. This free code portfolio contains a single landing page with a responsive design. In this post, we get a free best carpenter and craftsman service website designed by FreeWebsiteCreate with HTML, CSS, Bootstrap, and JavaScript.