Fenwick Iterations — FENWITER
PROBLEM link SUBMIT in practice
DIFFICULTY LEVEL- Easy
PREREQUISITE- Fenwick tree basics, Bit manipulation.
PROBLEM:
Fenwick Tree data structure holds information about array of elements and can process two types of operations:
- Add some value to any element of the array.
- Calculate sum of all elements on any prefix of the array
Both the operations takes O(Log n) time to compute. This data structure is memory efficient and takes nearly same memory as that of original array.
As it takes O(Log n) time to calculate the sum of any prefix of the array ,Chef has designed a problem to verify that it is actually taking O(log n) operations or not.
For that you have to access the fenwick tree Log n times , so chef has given you a number up to which you have calculate the prefix sum and this number is very large so chef has provided it to you in the form of binary strings L1, L2, L3 and a number N specifying that actual string is formed as L1+(L2 repeated N times)+L3 and now you have to identify how many times you have to access the fenwick tree.
for more go through the PROBLEM link.
EXPLAINATION:
For more detailed description of fenwick tree that how to create it ,update and query operations you can go through the youtube tutorial below.
For better understanding go through the PROBLEM link because post contains some terminology which might confuse you a little.
As we can go to the parent of any node by flipping the rightmost set bit(1 bit) by doing this continuously we can reach to zeroth index.
As Given in problem statement start = Fdown(i) = (i & (i + 1)) from this statement you can conclude that the zeroth node of fenwick tree is storing the sum till 0th index of array A.
similarly, first node of fenwick tree is storing the sum of zeroth and first node of given array A.
and so on..
Now, we will take each index one by one and try to find out how many times we have to access the tree.
Sum up to 0: for sum up to 0(Zero) we have to access tree only once as zeroth node is storing the sum till 0.
Sum up to 1: for sum up to 1 as we know first node is having sum of zeroth to first node so again we have to access tree only once.
Sum up to 2: for sum up to 2 as we know second node is having sum of second element only. So here we have to go to node 1 as it contains the value of zeroth to first element. So, total number of times tree accessed is 2.
Sum up to 3: for sum up to 3 as we know third node is storing the sum of zeroth to third element . So ,we have to access tree only once.
Sum up to 4: for sum up to 4 as we know fourth node is storing the sum of only fourth element . So, you have to come to node three and now you can get the total sum up to 4th element.
Now, there is a observation that number of times you accessed the tree is just count the number of ones in the binary representation of the number(till which you have to find the sum)+1.
Examples: for 1 (Binary representation =”1" now add 1 to it’s binary representation this will become “10” which has only 1 one so answer is 1) answer is 1.
for 2 (Binary representation =”10" now add 1 to it’s binary representation this will become “11” which has two 1’s so answer is 2) answer is 2.
for 4(Binary representation =”100" now add 1 to it’s binary representation this will become “101” which has two 1’s so answer is 2) answer is 2.
Examples from original question:
Test case 1:
L1 L2 L3 N
1000 1101 100 3
As per question the above string is actually 1000 1101 1101 1101 100 (L2 repeated 3 times) So,just add 1 to this binary representation which is1000 1101 1101 1101 101 and count number of ones in it which is 12 and so the answer.Test case 2:L1 L2 L3 N
1010 001 101 4As per question the above string is actually 1010 001 001 001 001 101 So,just add 1 to this binary representation which is1010 001 001 001 001 110 and count number of ones in it which is 8 and so the answer.
CODE in C/C++
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char l1[1001],l2[1001],l3[1001];
long long int n,sum;
int t,total,lenl1,lenl2,lenl3,i,z1,z2,z3,total1ofl2,countl2,countl1,countl3;
scanf("%d",&t);
while(t--)
{
scanf("%s %s %s %lld",l1,l2,l3,&n);
lenl3=strlen(l3);
lenl2=strlen(l2);
lenl1=strlen(l1);
z1=0;z2=0;z3=0;
total1ofl2=0;
countl2=0;countl1=0;countl3=0;
for(i=lenl3-1;i>=0;i--) //starting from third string's last character if any zero will come we will stop at that point
{
if(z3==1 && l3[i]=='1')
{
countl3++;
}
if(l3[i]=='0' && z3==0)
{
z3=1;
}
}
if(z3==1)
{
for(i=lenl2-1;i>=0;i--)
{
if(l2[i]=='1')
{
countl2++;// as 0 already encountered there is no need to check further count 1's in whole second srting
}
}
for(i=lenl1-1;i>=0;i--)
{
if(l1[i]=='1')// similarly count 1's in whole 2nd string
{
countl1++;
}
}
sum=countl1+countl2*n+countl3+1; // this additional 1 is for that bit which is previously zero but now becomes one because of adding one to the number
printf("%lld\n",sum);
}
else
{
for(i=lenl2-1;i>=0;i--) // if no 0 found in third string, find first occurrence of zero in second string
{
if(z2==1 && l2[i]=='1')
{
countl2++;
}
if(l2[i]=='0' && z2==0)
{
z2=1;
}
if(l2[i]=='1')
{
total1ofl2++;
}
}
if(z2==1)
{
for(i=lenl1-1;i>=0;i--)
{
if(l1[i]=='1')
{
countl1++;
}
}
sum=total1ofl2*(n-1)+countl2+countl1+1; // Trikiest part mostly done wrong as we have to find only first occurence of zero don't again and again add countl2 it will be added only once and rest n-1 times total1ofl2 will be added
printf("%lld\n",sum);
}
else
{
for(i=lenl1-1;i>=0;i--)// still not found 0 find zero in l1
{
if(z1==1 && l1[i]=='1')
{
countl1++;
}
if(l1[i]=='0' && z1==0)
{
z1=1;
}
}
if(z1==1)
{
sum=countl1+1;
printf("%lld\n",sum);
}
else
{
printf("1\n");
}
}
}
}
}
