Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example Input:
[-2,1,-3,4,-1,2,1,-5,4],
Example Output: 6
Explanation:
[4,-1,2,1] has the largest sum = 6.

Hint : can be solved in O(N)
*Read Solution* : http://codingclub.tech/event/solution-max-subarray-sum

Hello Everyone!!

Yet Another Number Game Problem Code: NUMGAME
Alice and Bob play the following game. They choose a number N to play with. The rules are as follows :
1) Alice plays first, and the two players alternate.
2) In his/her turn, a player can subtract from N any proper divisor (not equal to N) of N. The number thus obtained is the new N.
3) The person who cannot make a move in his/her turn loses the game.

Assuming both play optimally, who wins the game ?

Input : The first line contains the number of test cases T. Each of the next T lines contains an integer N.
Output : Output T lines, one for each test case, containing "ALICE" if Alice wins the game, or "BOB" otherwise.

Sample Input :
2
1
2

Sample Output :
BOB
ALICE

Constraints :
1 <= T <= 10000
1 <= N <= 1000000000

Note : For the first test case, Alice cannot make any move and hence Bob wins the game. For the second test case, Alice subtracts 1 from N. Now, Bob cannot make a move and loses the game.

Can you solve ?
PROBLEM

Editorial for Solution:
EDITORIAL


Happy Learning

Fast IO Optimization in C++

In competitive programming, it is important to optimize I/O methods as time limit of some problems is very strict.

You must have seen various problem statements saying: “Warning: Large I/O data, be careful with certain languages (though most should be OK if the algorithm is well designed)”. Key for such problems is to use Faster I/O techniques.

Lets say you have taken an input of 10^5 numbers, there are many methods for input/output

1. std::cin>>x;
std::cout<<x;

you can use std::cin and std::cout. How ever there are better methods

2.scanf("%d",&x);
printf ("%d",x);

scanf / printf are roughly thrice as fast as the cin/cout.

However, you can still use cin/cout and achieve the same speed as scanf/printf by including the following lines in your main function.

#include <bits/stdc++.h>
using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
return 0;
}

To know more about this read here.

3. FAST IO

void fastscan(int &x)
{
bool neg = false;
register int c;
x = 0;
c = getchar();
if(c == '-')
{
neg = true;
c = getchar();
}
for(;(c>47 && c<58);c=getchar()) x=(x<<1)+(x<<3)+c-48;
if(neg) x *=-1;
}

fastscan(x);

this is one of the fastest way to take an integer input from STDIN this is around 10 times faster than scanf() This is very useful in competetive programming.

Similiarly to print an integer, the following fastprint() function can be used.

void fastprint(int n)
{
if (n == 0)
{
putchar('0');
putchar('\n');
}
else if (n == -1)
{
putchar('-');
putchar('1');
putchar('\n');
}
else
{
int neg=0;
char buf[20];
if(n<0){
neg=1;
n=-n;
}
buf[10] = '\n';
int i = 9;
while (n)
{
buf[i--] = n % 10 + '0';
n /= 10;
}
if(neg)buf[i--]='-';
while (buf[i] != '\n')
putchar(buf[++i]);
}
}

fastprint(n);



We can test our input and output methods on the problem : PROBLEM

Solution:
CODE

For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Hello Everyone!!

Find the middle element of a linked list

Naive solution:
1. A simple way to determine the middle node would be
to fully pass through all nodes in the linked list
and count how many elements there are in total.
2. Then traverse the linked list again this time
stopping at the total/2 node.

For example,
the first time you traverse the linked list your program determines there are 10 nodes,
then the second pass through the linked list you stop at the 5th node,
which is the middle node.


This is a possible solution,
but there is a faster way.
Can you find it out ?

Read Optimal and Full Solution
SOLUTION


Happy Learning

Problem 1: You have n lists, each consisting of m integers sorted in ascending order. Merging these lists into a single sorted list will take time:

(a) O(nm log m) (b) O(mn log n)
(c) O(m + n) (d) O(mn)


Problem 2: A simple graph is one in which there are no self loops and each pair of distinct vertices is connected by at most one edge. Let G be a simple graph on 8 vertices such that there is a vertex of degree 1, a vertex of degree 2, a vertex of degree 3, a vertex of degree 4, a vertex of degree 5, a vertex of degree 6 and a vertex of degree 7. Which of the following can be the degree of the last vertex?

(a) 3 (b) 0
(c) 5 (d) 4


Problem 3: When a user submits a query, a search engine does the following. For every webpage that has been visited by the search engine, it computes a score indicating how relevant that page is to the query. Finally, it reports the pages with the top k scores on the screen, for a number k specified by the user. A good data structure for accumulating the scores and ranking them is:

(a) a queue (b) a heap
(c) a stack (d) a binary search tree


Problem 4: A complete graph on n vertices is an undirected graph in which every pair of distinct vertices is connected by an edge. A simple path in a graph is one in which no vertex is repeated. Let G be a complete graph on 10 vertices. Let u, v, w be three distinct vertices in G. How many simple paths are there from u to v going through w?


Solutions:
Answer 1: b) O(mn log n)

We can merge two sorted lists of size k and l in time
O(k +l). We begin by merging the lists in pairs to generate n/2 lists of size 2m each. To generate a list of size 2m we require O(m+m) time. Therefore to generate n/2 list the time required will be O(mn). If we repeat this, we get n/4 lists of size 4m each, again in total time O(mn). Thus, in O(log n) rounds, we converge to a single sorted list. Each round takes time O(mn), so the total time is O(mn log n).
Another strategy to achieve complexity O(mn log n) is to build a min-heap of size n, consisting the first element in each of the n lists. We then extract the minimum element from the heap to the output and replace it in the heap with the next element from the list from which the minimum came. Thus, it takes time O(log n) to generate each element in the output and there are O(mn) output elements in all, so the overall time
is O(mn log n).


Answer 2: d) 4

The number of odd degree vertices in any graph is even. Since we already have four
vertices of odd degree, the degree of the last vertex cannot be 3 or 5. It cannot be 0 either, since there is one vertex with degree 7, which means that it is a neighbour to all the other vertices, which implies that there is no isolated vertex in the graph. Thus the only possible degree of the last vertex is 4.


Answer 3: b) a heap

Let n be the number of pages visited by the search engine at the time a query is submitted. Assume that it takes constant time to compute the relevance score for each page w.r.t. a query. Then it takes O(n) time to compute the relevance scores, a further O(n) time to build a heap of n relevance scores, and O(k·log n) time for k delete-max operations to return the top k scores.

Answer 4: For every path from u to v, w is always present. Now, the no of nodes from the remaining 7 nodes (10 nodes -{u,v,w}) can be choosen in 7Ci ways and for each of the choosen i vertices, these nodes can be travelled in (i+1)! ways ( i+1 because we are including the w vertex also, along with the i vertices). Thus the total no of ways are:

=(7C0).(1!) + (7C1).(2!) + (7C2).(3!) + (7C3).(4!) + (7C4).(5!) + (7C5).(6!) + (7C6).(7!) + (7C7).(8!)

=95901.



Happy Coding!!!!

Hello Everyone!!

Problem Link: PROBLEM

Question
An archeologist seeking proof of the presence of extraterrestrials in the Earth’s past, stumbles upon a partially destroyed wall containing strange chains of numbers. The left-hand part of these lines of digits is always intact, but unfortunately the right-hand one is often lost by erosion of the stone. However, she notices that all the numbers with all its digits intact are powers of 2, so that the hypothesis that all of them are powers of 2 is obvious. To reinforce her belief, she selects a list of numbers on which it is apparent that the number of legible digits is strictly smaller than the number of lost ones, and asks you to find the smallest power of 2 (if any) whose first digits coincide with those of the list.
Thus you must write a program such that given an integer, it determines (if it exists) the smallest exponent E such that the first digits of 2^E coincide with the integer (remember that more than half of the digits are missing).

Input
It is a set of lines with a positive integer N not bigger than 2147483648 in each of them.

Output
For every one of these integers a line containing the smallest positive integer E such that the first digits
of 2^E are precisely the digits of N, or, if there is no one, the sentence ‘no power of 2’.

Sample Input
1
2
10


Sample Output
7
8
20

Explanation
Input 1
2^7 = 128
input 2
2^8=256
input 3
2^20=1048576





Solution:
EDITORIAL

Pseudocode:

N=input 
T=floorl(log10(N)+2) 
A=log2(N)+T*log2(10) 
B=log2(N+1)+T*log2(10) 
while(ceill(A)>=B) 
        T=T+1 
        A=log2(N)+T*log2(10) 
        B=log2(N+1)+T*log2(10) 
print ceill(A)

Code:
CODE

For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

For enhancing the book reading, school distributed story books to students as part of the Children’s day celebrations.

To increase the reading habit, the class teacher decided to exchange the books every weeks so that everyone will have a different book to read. She wants to know how many possible exchanges are possible.

If they have 4 books and students, the possible exchanges are 9. Bi is the book of i-th student and after the exchange he should get a different book, other than Bi.

B1 B2 B3 B4 - first state, before exchange of the books

B2 B1 B4 B3

B2 B3 B4 B1

B2 B4 B1 B3

B3 B1 B4 B2

B3 B4 B1 B2

B3 B4 B2 B1

B4 B1 B2 B3

B4 B3 B1 B2

B4 B3 B2 B1

Find the number of possible exchanges, if the books are exchanged so that every student will receive a different book.


Solution
We have to apply derangement formula here.
DERANGEMENTS
Count Derangements :
SOLUTION

Happy Learning

Problem:
You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you have an army of friends to help you and each task can be done by either you or any of your friends, so you can complete as many tasks as possible in parallel, on the same day.
Some tasks depend on others: for instance, you cannot purchase foreign exchange till you have bought your ticket. If task B depends on task A, you can start B only after you complete A. A set of tasks with no pending dependencies can be completed in parallel.
You are given a list of n such tasks to be completed, where each task comes with a set of other tasks that it depends on. The set of tasks is feasible: there are no circular dependencies. You want to compute the minimum number of days needed to complete all the tasks, given the constraints.



Solutions:
Construct a graph in which the tasks are the vertices and there is an edge (i, j) if task i must be completed before starting task j. This is a directed graph without cycles, so it is a directed acyclic graph (dag). Any path (suppose v1->v2->v3->.....->vk of length k) of tasks would take a minimum of k days to complete because each edge in the path describes a dependency. Hence, the problem is one of finding the longest path in a dag.

In any dag, there must be some vertex with no incoming edge (indegree 0). Any vertex of indegree 0 represents a task that has no pending dependencies and can hence be immediately completed. Once it is completed, we can remove it from the graph and operate on the tasks that remain.
The algorithm is thus the following.
• Initialize a counter c to 0.
• While the dag is not empty
– Remove all vertices of indegree 0
– Recompute indegrees of remaining vertices
– Increment c

The final value of c is the answer we seek.
The complexity of this algorithm depends on how we represent the graph. For G = (V, E) let |V | = n and |E| = m. If we use an adjacency matrix, for each vertex we remove, we have to scan a row of the matrix to determine which indegrees to decrement, so it will take time O(n^2). If we use adjacency lists, for each vertex we delete, we can scan its list of outgoing edges and directly decrement indegrees for its outgoing neighbours. Across the n vertices we delete, we scan each of the m edges once, so the overall time is O(n + m).


Happy Coding!!!

Problem: Your final exams are over and you are catching up on watching sports on TV. You have a schedule of interesting matches coming up all over the world during the next week. You hate to start or stop watching a match midway, so your aim is to watch as many complete matches as possible during the week. Suppose there are n such matches scheduled during the coming week and you know the starting and finishing time for each match.
Describe an efficient algorithm to compute the following: for each match, what is the next match whose starting time is strictly later than the finishing time of the current match?




Solution: We can accumulate information about the matches in the order in which they appear in the TV schedule. Hence, we can assume that the starting times and ending times of the matches are recorded in two arrays B[1..n] and E[1..n], where B[i] and E[i] are the beginning and ending time, respectively, of match i and B is sorted in ascending order. For each match i, we use binary search in B to find the earliest match j such that E[i] ≤ B[j] and set Next[i] = j. We do n binary searches, so this takes time O(n log n).



Happy Coding!!!!

Problem 1: Let A be an array of n integers, sorted so that A[1] ≤ A[2] ≤ · · · ≤ A[n]. You are given a number x. The aim is to find out if there are indices k and l such that A[k] + A[l] = x. Design an algorithm for this problem that works in time O(n).

Problem 2: Let A be array of n integers that is assumed to be sorted. You are given a number x. The aim is to find out if there are indices k, l and m such that
A[k] + A[l] + A[m] = x. Design an algorithm for this problem that works in time O(n^2).





Solution 1: Consider the two endpoints A[1] and A[n].
• If A[1] + A[n] > x, A[n] is useless since it cannot be paired with any number to achieve the sum—any sum A[i] + A[n], i > 1, will be greater than or equal to A[1] + A[n] since A[i] ≥ A[1].
• Likewise, if A[1] + A[n] < x, A[1] is useless since it cannot be paired with any number to achieve the sum.
Hence, we start with two pointers left and right, with left = 1 and right = n initially. At each stage, we check the sum A[left] + A[right]. If this sum exceeds x, we decrement right and if this sum is less than x we increment left. Eventually, either left and right meet and there is no solution, or we find the indices k and that we are looking for.
This takes a single scan of A, so the overall time is O(n).


Solution 2: Suppose we fix the first index k = 1. Then the problem reduces to finding l and m in 2, 3, . . . , n such that A[l] +A[m] = x−A[1]. This can be solved in time O(n)
by the solution 1 discuss earlier in this post. . We vary k from 1, 2, . . . , n−3, and check for l and m in k+1, k+2, . . . , n such that A[l] + A[m] = x − A[k]. This takes time (n−1) +(n−2) + (n−3) + · · · · · · · + 1 = O(n^2).


Happy Coding!!!!

Hello Everyone!!

Problem Link: TOWER

Question
There are N cities in Magic land arranged as a one dimensional array. For simplicity we can assume an array of size N as N cities. The king of Magic land is now installing new 4G internet towers in various cities. Let us consider the array is A1 , A2 , A3 , A4 ,......, AN. Now, consider the following statement:

If Ai is equal to 0 then it means there is no tower in the city.
If Ai is equal to k (k is a positive integer), then there is a tower in ith city and the range of the tower is k. It means the city from A max ( 1 , i - k ) to A min ( N , i + k ) will get the internet connection.
Suppose, A5 = 1 , then A4 , A5 and A6 will get the internet connection even if there is no tower in A4 or A6.

The installation of towers is over now. The king wants to know how many cities are there without internet connection.

Input
•The first line contains an integer N denoting the number of cities
•The second line contains N spaced seperated integers denoting A1 , A2 , A3 , . . . . . . , AN

Output
•The one and only line contains an integer denoting the number of cities without any internet connections

Constraints
•1 ≤ N ≤ 106
•0 ≤ Ai ≤ 109

Sample Input 1
4
0 0 1 0
Sample output 1
1

Sample Input 2
7
0 2 0 0 0 0 1
Sample output 2
1

Explanation

For sample input 1 :
There is only one tower in city 3 whose range is 1. City 2 , 3 and 4 gets the internet connection from this tower but city 1 doesnot get it hence the output is 1.

For sample input 2:
There is a tower at city 2 whose range is 2. City 1 , 2 , 3 and 4 gets the internet connection from this tower. Similarly city 6 and 7 get internet connection from the tower at city 7. But city 5 doesnot get internet connection at all. Hence the output is 1.





Solution:
EDITORIAL

Pseudocode:

n=number of cities
A=array
n,A=input

for i = 0 to n-1
  if Ai>0
        Ai++

Leftc[n]
Rightc[n]
c=0

for i=0 to n-1
  c=c-1
  c=max(c,A[i])
  Rightc[i]=c

c=0

for i=n-1 to 0
  c=c-1
  c=max(c,A[i])
  Leftc[i]=c

count=0

for i=0 to n-1
  if(Leftc[i]==0 && Rightc[i]==0)
    count++

print count

Code:
CODE

For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Question:

Take an input array, say A and print the maximum value of x
where x = |(A[i] – A[j]) + (i – j)| .

Constraints:
Max array size: 20000
Time limit: 0.1s

Time limit is a major factor in this question.


Hint:
https://imgur.com/0jhFcBi

Solution Approach:
https://imgur.com/5xc5AO2

Complete Solution:
https://imgur.com/abadlKe

Happy Learning

Question
Given an array of strings with R, G & B as characters. Sort the array such that all R comes first, followed by Gs & followed by Bs.
Do it in O(n) time complexity.

For eg. array is:
I/P: G G R B R B B G R B R
O/P: R R R R G G G B B B B

Read Solution:
DNF algorithm

Happy Learning

problem: You are given an array A of size n. You are told that A comprises three consecutive runs – first a run of ’a’s, then a run of ’b’s and finally a run of ’c’s. Moreover, you are provided an index i such that A[i] = b. Design an O(log n) time algorithm to determine the number of ’b’s (i.e.,
length of the second run) in A.


Solution: We will use modified binary search to find the first occurrence of 'b'. In the similar manner we will find the last occurrence of 'b'. The final answer is (last occurrence - first occurrence +1).
Now, to find the first occurrence we have to check that if the current element is 'b' and the element before this current element is 'a'. If yes, then we got our first occurrence else we search on the right segment if the current element is 'a', else we search in the left segment.
Pseudo Code:

first_occurrence(A[],low,high)
   mid=(low+high)/2
   if(A[mid]=='b' && A[mid-1]=='a'):
       return mid
   else if(A[i]=='a'):
       return first_occurrence(A,mid+1,high)
   else:
       return first_occurrence(A,low,mid-1)

In the similar manner we can find the last occurrence. If the current element is 'b' and the next element is 'c' then it is the last occurrence of 'b'. Else we search on the left segment if the current element is 'c'. Otherwise we search the right segment.
Pseudo Code:

last_occurrence(A[],low,high)
  mid=(low+high)/2
  if(A[mid]=='b' && A[mid+1]=='c'):
      return mid
  else if(A[i]=='b'):
      return last_occurrence(A,mid+1,high)
  else:
      return last_occurrence(A,low,mid-1)

Happy Coding!!!

Asked in Microsoft Interview
Count ways to express a number as sum of consecutive numbers

Example
Input :15
Output :3
15 can be represented as:
1+2+3+4+5
4+5+6
7+8

Input :10
Output :1
10 can only be represented as:
1+2+3+4

Read solution:
SOLUTION


Happy Learning

Problem: Give an efficient implementation for a data structure STACK_MAX to support an operation maximum() that reports the current maximum among all elements in the stack. Usual stack operations (createEmpty(), push(), pop()) are also to be supported.




Solution: Instead of an array of integers, we will maintain an array of structure. The structure will comprise of 2 member variables. One that holds current element and the other holds the maximum element uptill now. The prototype is as follows:

struct Stack{
    int cur_element;
    int cur_max;
};

Stack s[MAX_SIZE];

We just need to modify the push() function a little bit.
The pseudo code for push function is as follows:

push(x,top)
    if (top==MAX_SIZE) :
       //Stack is full 
        print("Stack overflow")
    else if(top==-1) :
        //Stack has no elements
        top=0
        s[top].cur_element=x
        s[top].cur_max=x
    else :
        top=top+1
        s[top].cur_element=x
        s[top].cur_max=max(x,s[top-1].cur_max)
    return

The pop() function remains the same. In the maximum() function we just return s[top].cur_max if the stack is not empty. The time complexity for maximum() function is O(1). The overall space complexity is O(n).


Happy Coding!!!

Asked in Google Internship Interview :
Find Median from Data Stream

Design a data structure that supports the following two operations:
void addNum(int num) - Add a integer number from the data stream to the data structure.
double findMedian() - Return the median of all elements so far.

Median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value. So the median is the mean of the two middle value.

For example:
[2,3,4], the median is 3

[2,3], the median is (2 + 3) / 2 = 2.5

Hint and solution :
bit.ly/solution-running-median

Happy Learning

Your are given an array of integers and an integer k of window size, you need to find minimum value in this window.
Ex. A: 1 2 3 4 5 6 and k = 3
Then output will be: 1 2 3 4
This question is similar to Maximum of all subarrays of size k

Read Optimal and Brute force solution
SOLUTION



Happy Learning

Question: A bipartite graph is a (simple) undirected graph G = (V, E) whose vertex set V can be partitioned in two disjoint subsets V1 and V2 such that V = (v1 U V2), no two vertices in V1 are connected by an edge, and no two vertices in V2 are connected by an edge. You are given a connected bipartite graph (V, E), but the sets V1 and V2 are not supplied to you. Design an efficient algorithm to compute V1 and V2. Deduce the running time of your algorithm.


Solution: The given graph is a bipartite graph, we need to figure out all the vertices in the set V1 and V2. We will use bfs ( breadth first search) here. We will maintain a bool variable (let it be named bool_flag) inside every node and then we start to travel the graph. We can choose any vertex as the source vertex here. For simplicity lets choose 1 as the source vertex. We set bool_flag for vertex 1 to 0 and for every adjacent vertex of vertex 1 we set the bool_flag to 1. We then travel all the other nodes and set bool_flag to 1 if its parent's bool_flag is 0 else we set bool_flag to 0 if its parent's bool_flag is 1. Note, since the graph is bipartite hence we will not have any cycle of odd length in the graph, hence if two vertices share an edge then the bool_flag of both of them cannot be the same or in another word, if the bool_flag of one of them is 1 then the other will have 0 as its bool_flag. After the whole process, every vertex will have either bool_flag as 0 or as 1. The vertices having bool_flag as 0 makes up one set and the vertices having bool_flag as 1 makes up another set.
The time complexity for the bfs algorithm is O(V+E).
Note: we can also use dfs for travelling the vertices instead of bfs.



Happy Coding!!!

Sliding Window Maximum (Maximum of all subarrays of size k)

Given an array and an integer K, find the maximum for each and every contiguous subarray of size k.

Examples:
Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3
Output: 3 3 4 5 5 5 6

Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4
Output: 10 10 10 15 15 90 90

We have discussed the brute force and optimal solutions in a previous post.
In this post we focus on the O(n) solution and analyse time complexity of the solution.



Explanation:
We create a Deque Q of size k and maintain the following conditions:
1. Q contains only the useful elements of current window.
2. Q contains the elements in descending order.

Now what are useful elements?

Suppose the array is
{10,5,4,3,1,7,6} and k=6

We start traversing input array from index 0 and as we reach index 4 our deque Q contains
{10,5,4,3,1} as all the elements are useful.
Now after we read 7 at index 5 the elements 5,4,3,1 become useless here.
For any window afterwards if it contains 5,it will also contain 7.As 7 is greater than 5 and we are looking for maximum , 5 is useless.Similiarly 4,3,1 are also useless.
So Q contains {10,7}.
Now our window size is 6. For the next element in the array 10 is outside of the window.So We print 10 and pop it from the Q.
Q contains {7,6}.
We process all array elements one by one and maintain Q to contain useful elements of current window and these useful elements are maintained in descending order. The element at front of the Q is the largest of current window.



Pseudocode:
n=size of array
a=array
a=input
Q=deque //We will store the indices of useful elements in the deque
for i=0 to k-1:
while(!Q.empty() and a[i]>=a[Q.rear()]):
Q.pop_back()
Q.push_back(i)
for i=k to n:
print a[Q.front()]
while(!Q.empty() and Q.front()<=i-k):
Q.pop_front()
while(!Q.empty() and a[i]>=a[Q.rear()]):
Q.pop_back()
Q.push_back(i)
print a[Q.front()]



Time Complexity:
Suppose 1st k elements of input array are in descending order.So after passing through 1st k elements of input array deque contains k elements.
Let's say each of remaining (n-k) elements will be greater than half of elements present in deque.To insert (k+1)th element we have to make (k/2+1) comparisons and after insertion there will be(k/2) elements in the deque. To insert (k+2)th element we have to make (k/4+1) comparisons and after insertion there will be (k/4) elements in the deque.So to insert all the elements of input array in the deque total number of comparisons will be:
k+((k/2+1)+(k/4+1)+(k/8+1)+......(n-k) terms....)
= (k + k/2 + k/4 + ....(n-k+1) terms.....) +(n-k)
= ( k * (1 - (1/2)^ (n-k+1)) / (1-1/2) ) +(n-k)
= 2 * k * (2 ^ (n-k+1)-1) / (2^(n-k+1)) +(n-k)
≅ 2 * k *(2^(n-k+1)) / (2^(n-k+1)) +(n-k)
≅ 2*k + n - k
≅ n + k
So time complexity of above algorithm is O(n+k) i.e O(n) as (k<=n).



Code:
CODE


For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning

Range update query
Consider an array A[] of integers and following two types of queries.

update(l, r, x) : l is left index, r is right index and x is value to be added i.e add x to all values from A[l] to A[r] (both inclusive).
printArray() : Prints the current modified array.


Solution:

Using Prefix Array:
Take an array pref of same size as input array.Initialize it with 0.

1.Upadate(l,r,x):
Add x to pref[l] and substract it from pref[r+1]
i.e we do pref[l]+=x , pref[r+1]-=x

2.PrintArray():
Take prefix sum of pref array i.e
for i=1 to n-1
pref[i]=pref[i]+pref[i-1]
Now, for all elements of input array
do A[i]=A[i]+pref[i] and print them

Here update range operation is performed in O(1).
printArray is performed in O(n).


Pseudocode:

n=size of array
A=array
pref=array
initialize pref with 0
A=input

update(l,r,x):
  pref[l]+=x
  if(r+1<n)
    pref[r+1]-=x

printArray():
  for i=1 to n-1
    pref[i]=pref[i]+pref[i-1]
  for i=0 to n-1
    A[i]=A[i]+pref[i]
  for i=0 to n-1
    print A[i]
    print " "
  print "\n"

Code:
CODE



Using Difference Array:
Difference array D[i] of a given array A[i] is defined as D[i] = A[i]-A[i-1] (for 0 < i < N ) and D[0] = A[0]

1.Upadate(l,r,x):
Add x to D[l] and substract it from D[r+1]
i.e we do D[l]+=x , D[r+1]-=x

2.printArray():
Do A[0] = D[0] and print it.
For rest of the elements, do A[i] = A[i-1] + D[i] and print them.

update range operation is performed in O(1).
printArray is performed in O(n).

Pseudocode:
n=size of array
A=array
D=array
A=input

D[0]=A[0]
for i=1 to n-1
D[i]=A[i]-A[i-1]


update(l,r,x):
D[l]+=x
if(r+1<n)
D[r+1]-=x

printArray():
A[0]=D[0]
for i=1 to n-1
A[i]=A[i-1]+D[i]
for i=0 to n-1
print A[i]
print " "
print "\n"

Code:
CODE


For any doubt or correction feel free to contact me:
@saranyanaharoy

Happy Learning