## Representation of a number in powers of other

Given two numbers w and m, we need to determine whether it is possible to represent m in terms of powers of w. The powers of number w can be added or subtracted to obtain m and each powers of w can be used only once .

Examples:

```Input : 3 7
Output : Yes
As 7 = 9 - 3 + 1 (3^2 - 3^1 + 3^0 )
so it is possible .

Input : 100 50
Output : No
As 50 is less than 100 so we can never
represent it in the powers of 100 .```

Here we have to represent m in terms of powers of w used only once so it can be shown through the following equation .
c0 + c1*w^1 + c2*w^2 + … = m —— (Equation 1)

Where each c0, c1, c2 … are either -1 (for subtracting that power of w ), 0 (not using that power of w ), 1 (for adding that power of w ) .

=> c1*w^1 + c2*w^2 + … = m – c0
=> w(c1 + c2*w^1 + c3*w^2 + … ) = m – c0
=> c1 + c2*w^1 + c3*w^2 + … = (m – c0)/w —— (Equation 2)

Now, notice equation 1 and equation 2 — we are trying to solve the same problem all over again. So we have to recurse till m > 0 . For such a solution to exist (m — ci) must be a multiple of w, where ci is the coefficient of the equation . The ci can be -1, 0, 1 . So we have to check for all three possibilities ( ( m – 1 ) % w == 0), ( ( m + 1 ) % w == 0) and ( m % w == 0) . If it is not, then there will not be any solution.

`// CPP program to check if m can be represented`
`// as powers of w.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`bool` `asPowerSum(``int` `w, ``int` `m)`
`{`
`    ``while` `(m) {`
`        ``if` `((m - 1) % w == 0) `
`            ``m = (m - 1) / w;`
`       ``else` `if` `((m + 1) % w == 0) `
`            ``m = (m + 1) / w;`
`        `
`        ``else` `if` `(m % w == 0) `
`            ``m = m / w;`
`        `
`        ``else`
`            ``break``; ``// None of 3 worked.`
`    ``}`
`    ``// If m is not zero means, it can't be `
`    ``// represented in terms of powers of w.`
`    ``return` `(m == 0);`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``int` `w = 3, m = 7;`
`    ``if` `(asPowerSum(w, m))`
`        ``cout << ``"Yes"` `<< endl;`
`    ``else`
`        ``cout << ``"No"` `<< endl;`
`   ``return` `0;`
`}`

Output:

```Yes

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/representation-number-powers/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Print Number series without using any loop

Problem – Givens Two number N and K, our task is to subtract a number K from N until number(N) is greater than zero, once the N becomes negative or zero then we start adding K until that number become the original number(N).
Note : Not allow to use any loop.

Examples :

```Input : N = 15 K = 5
Output : 15 10 5 0 1 5 10 15

Input : N = 20 K = 6
Output : 20 14 8 2 -4 2 8 14 20
```

Explanation – We can do it using recursion idea is that we call the function again and again until N is greater than zero (in every function call we subtract N by K). Once the number becomes negative or zero we start adding K in every function call until the number becomes the original number. Here we use a single function for both addition and subtraction but to switch between addition or subtraction function we used a Boolean flag.

Code –

`// C++ program to Print Number`
`// series without using loop`
`#include <iostream>`
`using` `namespace` `std;`
`// function print series`
`// using recursion`
`void` `PrintNumber(``int` `N, ``int` `Original, ``int` `K, ``bool` `flag)`
`{`
`    ``// print the number`
`    ``cout << N << ``" "``;`
`    ``// change flag if number`
`    ``// become negative`
`    ``if` `(N <= 0)`
`        ``flag = !flag;`
`    ``// base condition for`
`    ``// second_case (Adding K)`
`    ``if` `(N == Original && !flag)`
`        ``return``;`
`    ``// if flag is true`
`    ``// we subtract value until`
`    ``// number is greater then zero`
`    ``if` `(flag == ``true``) {`
`        ``PrintNumber(N - K, Original, K, flag);`
`        ``return``;`
`    ``}`
`    ``// second case (Addition )`
`    ``if` `(!flag) {`
`        ``PrintNumber(N + K, Original, K, flag);`
`        ``return``;`
`    ``}`
`}`
`// driver program`
`int` `main()`
`{`
`    ``int` `N = 20, K = 6;`
`    ``PrintNumber(N, N, K, ``true``);`
`    ``return` `0;`
`}`

Output :

```20 14 8 2 -4 2 8 14 20

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/print-number-series-without-using-loop/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Print all subsequences of a string | Iterative Method

Given a string s, print all possible subsequences of the given string in an iterative manner.
Examples:

```Input : abc
Output : a, b, c, ab, ac, bc, abc

Input : aab
Output : a, b, aa, ab, aab```

We use bit pattern from binary representation of 1 to 2^length(s) – 1.

input = “abc”
Binary representation to consider 1 to (2^3-1), i.e 1 to 7.
Start from left (MSB) to right (LSB) of binary representation and append characters from input string which corresponds to bit value 1 in binary representation to Final subsequence string sub.

Example:
001 => abc . Only c corresponds to bit 1. So, subsequence = c.
101 => abc . a and c corresponds to bit 1. So, subsequence = ac.

binary_representation (1) = 001 => c
binary_representation (2) = 010 => b
binary_representation (3) = 011 => bc
binary_representation (4) = 100 => a
binary_representation (5) = 101 => ac
binary_representation (6) = 110 => ab
binary_representation (7) = 111 => abc

Below is the implementation of above approach:

`// CPP program to print all Subsequences`
`// of a string in iterative manner`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// function to find subsequence`
`string subsequence(string s, ``int` `binary, ``int` `len)`
`{`
`    ``string sub = ``""``;`
`    ``for` `(``int` `j = 0; j < len; j++)`
`        ``// check if jth bit in binary is 1`
`        ``if` `(binary & (1 << j))`
`            ``// if jth bit is 1, include it`
`            ``// in subsequence`
`            ``sub += s[j];`
`    ``return` `sub;`
`}`
`// function to print all subsequences`
`void` `possibleSubsequences(string s){`
`    ``// map to store subsequence `
`    ``// lexicographically by length`
`    ``map<``int``, set<string> > sorted_subsequence;`
`    ``int` `len = s.size();`
`    `
`    ``// Total number of non-empty subsequence`
`    ``// in string is 2^len-1`
`    ``int` `limit = ``pow``(2, len);`
`    `
`    ``// i=0, corresponds to empty subsequence`
`    ``for` `(``int` `i = 1; i <= limit - 1; i++) { `
`        `
`        ``// subsequence for binary pattern i`
`        ``string sub = subsequence(s, i, len);`
`        `
`        ``// storing sub in map`
`        ``sorted_subsequence[sub.length()].insert(sub);`
`    ``}`
`    ``for` `(``auto` `it : sorted_subsequence) { `
`        `
`        ``// it.first is length of Subsequence`
`        ``// it.second is set<string>`
`        ``cout << ``"Subsequences of length = "`
`             ``<< it.first << ``" are:"` `<< endl;`
`             `
`        ``for` `(``auto` `ii : it.second)`
`            `
`            ``// ii is iterator of type set<string>`
`            ``cout << ii << ``" "``;`
`        `
`        ``cout << endl;`
`    ``}`
`}`
`// driver function`
`int` `main()`
`{`
`    ``string s = ``"aabc"``;`
`    ``possibleSubsequences(s);`
`    ``return` `0;`
`}`

Output:

```Subsequences of length = 1 are:
a b c
Subsequences of length = 2 are:
aa ab ac bc
Subsequences of length = 3 are:
aab aac abc
Subsequences of length = 4 are:
aabc

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/print-subsequences-string-iterative-method/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Print all subsequences of a strin

Given a string, we have to find out all subsequences of it. A String is a subsequence of a given String, that is generated by deleting some character of a given string without changing its order.

Examples:

```Input : abc
Output : a, b, c, ab, bc, ac, abc

Input : aaa
Output : a, aa, aaa```

Explanation :

```Step 1: Iterate over the entire String
Step 2: Iterate from the end of string
in order to generate different substring
add the subtring to the list
Step 3: Drop kth character from the substring obtained
from above to generate different subsequence.
Step 4: if the subsequence is not in the list then recur.

```

Below is the implementation of the approach.

`// Java Program to print all subsequence of a`
`// given string.`
`import` `java.util.HashSet;`
`public` `class` `Subsequence {`
`    `
`    ``// set to store all the subsequences`
`    ``static` `HashSet<String> st = ``new` `HashSet<>();`
`    ``// It computes all the subsequence of an string`
`    ``static` `void` `subsequence(String str)`
`    ``{`
`        ``// iterate over the entire string`
`        ``for` `(``int` `i = ``0``; i < str.length(); i++) {`
`            `
`            ``// iterate from the end of the string`
`            ``// to generate substrings`
`            ``for` `(``int` `j = str.length(); j > i; j--) {`
`                ``String sub_str = str.substring(i, j);`
`            `
`                ``if` `(!st.contains(sub_str))`
`                    ``st.add(sub_str);`
`                ``// drop kth character in the substring`
`                ``// and if its not in the set then recur`
`                ``for` `(``int` `k = ``1``; k < sub_str.length() - ``1``; k++) {`
`                    ``StringBuffer sb = ``new` `StringBuffer(sub_str);`
`                    ``// drop character from the string`
`                    ``sb.deleteCharAt(k);`
`                    ``if` `(!st.contains(sb))`
`                        ``;`
`                    ``subsequence(sb.toString());`
`                ``}`
`            ``}`
`        ``}`
`    ``}`
`    ``// Driver code`
`    ``public` `static` `void` `main(String[] args)`
`    ``{`
`        ``String s = ``"aabc"``;`
`        ``subsequence(s);`
`        ``System.out.println(st);`
`    ``}`
`}`

Output:

`[aa, a, ab, bc, ac, b, aac, abc, c, aab, aabc]`

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/print-subsequences-string/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Longest subsequence of the form 0*1*0* in a binary string

Given a binary string, find the longest subsequence of the form (0)*(1)*(0)* in it. Basically we need to divide the string into 3 non overlapping strings (these strings might be empty) without changing the order of letters. First and third strings are made up of only 0 and the second string is made up of only 1. These strings could be made by deleting some characters in original string. What is the maximum size of string, we can get?

Examples –

```Input : 000011100000
Output : 12
Explanation :
First part from 1 to 4.
Second part 5 to 7.
Third part from 8 to 12

Input : 100001100
Output : 8
Explanation :
Delete the first letter.
First part from 2 to 4.
Second part from 5 to 6.
Last part from 7.

Input : 00000
Output : 5
Explanation :
Special Case of Only 0

Input : 111111
Output : 6
Explanation :
Special Case of Only 1

Input : 0000001111011011110000
Output : 20
Explanation :
Second part is from 7 to 18.
Remove all the 0 between indices 7 to 18.```

simple solution is to generate all subsequences of given sequence. For every subsequence, check if it is in given form. If yes, compare it with result so far and update the result if needed.

This problem can be efficiently solved by pre-computing below arrays in O(n^2) time.

Let `pre_count_0[i]` be the count of letter 0 in the prefix of string till index i.
Let `pre_count_1[i]` be the count of letter 1 in the prefix of string till length i.
Let `post_count_0[i]` be the count of letter 0 in the suffix string from index i till index n (here n is the size of string).

Now we fix two two positions i and j, 1 <=i <= j <=n. We will remove all 0 from substring which starts at index i and ends in index j. Thus this makes the second substring of only 1. In the prefix before the index i and in the postfix after the index j we will delete all 1 and thus it will make first and third part of the string. then the maximum length of string attainable is max of `pre_count_0[i-1] + (pre_count_1[j]-pre_count_1[i-1]) + pre_count_1[j+1]`

Special cases : When String is made of only 0s or 1s, ans is n where n is length of string.

`// CPP program to find longest subsequence`
`// of the form 0*1*0* in a binary string`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`// Returns length of the longest subsequence`
`// of the form 0*1*0*`
`int` `longestSubseq(string s)`
`{`
`    ``int` `n = s.length();`
`    ``// Precomputing values in three arrays`
`    ``// pre_count_0[i] is going to store count`
`    ``//             of 0s in prefix str[0..i-1]`
`    ``// pre_count_1[i] is going to store count`
`    ``//             of 1s in prefix str[0..i-1]`
`    ``// post_count_0[i] is going to store count`
`    ``//             of 0s in suffix str[i-1..n-1]`
`    ``int` `pre_count_0[n + 2];`
`    ``int` `pre_count_1[n + 1];`
`    ``int` `post_count_0[n + 1];`
`    ``pre_count_0[0] = 0;`
`    ``post_count_0[n + 1] = 0;`
`    ``pre_count_1[0] = 0;`
`    ``for` `(``int` `j = 1; j <= n; j++)`
`    ``{`
`        ``pre_count_0[j] = pre_count_0[j - 1];`
`        ``pre_count_1[j] = pre_count_1[j - 1];`
`        ``post_count_0[n - j + 1] = post_count_0[n - j + 2];`
`        ``if` `(s[j - 1] == ``'0'``)`
`            ``pre_count_0[j]++;`
`        ``else`
`            ``pre_count_1[j]++;`
`        ``if` `(s[n - j] == ``'0'``)`
`           ``post_count_0[n - j + 1]++;`
`    ``}`
`    ``// string is made up of all 0s or all 1s`
`    ``if` `(pre_count_0[n] == n ||`
`        ``pre_count_0[n] == 0)`
`        ``return` `n;`
`    ``// Compute result using precomputed values`
`    ``int` `ans = 0;`
`    ``for` `(``int` `i = 1; i <= n; i++)`
`        ``for` `(``int` `j = i; j <= n; j++)`
`            ``ans = max(pre_count_0[i - 1]`
`                    ``+ pre_count_1[j]`
`                    ``- pre_count_1[i - 1]`
`                    ``+ post_count_0[j + 1],`
`                    ``ans);`
`    ``return` `ans;`
`}`
`// driver program`
`int` `main()`
`{`
`    ``string s = ``"000011100000"``;`
`    ``cout << longestSubseq(s);`
`    ``return` `0;`
`}`

Output :

```Output :20

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/longest-subsequence-of-the-form-010-in-a-binary-string/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Check if two expressions with brackets are same

Given two expressions in the form of strings. The task is to compare them and check if they are similar. Expressions consist of lowercase alphabets, ‘+’, ‘-‘ and ‘( )’.

Examples:

```Input  : exp1 = "-(a+b+c)"
exp2 = "-a-b-c"
Output : Yes

Input  : exp1 = "-(c+b+a)"
exp2 = "-c-b-a"
Output : Yes

Input  : exp1 = "a-b-(c-d)"
exp2 = "a-b-c-d"
Output : No
```

It may be assumed that there are at most 26 operands from ‘a’ to ‘z’ and every operand appears only once.

A simple idea behind is to keep a record of the Global and Local Sign(+/-) through the expression. The Global Sign here means the multiplicative sign at each operand. The resultant sign for an operand is local sign multiplied by the global sign at that operand.

For example, the expression a+b-(c-d) is evaluated as (+)+a(+)+b(-)+c(-)-d => a + b – c + d. The global sign (represented inside bracket) is multiplied to the local sign for each operand.

In the given solution, stack is used to keep record of the global signs. A count vector records the counts of the operands(lowercase Latin letters here). Two expressions are evaluated in opposite manners and finally, it is checked if the all entries in the count vector are zeros.

`// CPP program to check if two expressions`
`// evaluate to same.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`const` `int` `MAX_CHAR = 26;`
`// Return local sign of the operand. For example,`
`// in the expr a-b-(c), local signs of the operands`
`// are +a, -b, +c`
`bool` `adjSign(string s, ``int` `i)`
`{`
`    ``if` `(i == 0)`
`        ``return` `true``;`
`    ``if` `(s[i - 1] == ``'-'``)`
`        ``return` `false``;`
`    ``return` `true``;`
`};`
`// Evaluate expressions into the count vector of `
`// the 26 alphabets.If add is true, then add count`
`// to the count vector of the alphabets, else remove`
`// count from the count vector.`
`void` `eval(string s, vector<``int``>& v, ``bool` `add)`
`{`
`    ``// stack stores the global sign`
`    ``// for operands.`
`    ``stack<``bool``> stk;`
`    ``stk.push(``true``);`
`    ``// + means true`
`    ``// global sign is positive initially`
`    ``int` `i = 0;`
`    ``while` `(s[i] != ``'\0'``) {`
`        ``if` `(s[i] == ``'+'` `|| s[i] == ``'-'``) {`
`            ``i++;`
`            ``continue``;`
`        ``}`
`        ``if` `(s[i] == ``'('``) {`
`            ``// global sign for the bracket is`
`            ``// pushed to the stack`
`            ``if` `(adjSign(s, i)) `
`                ``stk.push(stk.top());`
`            ``else`
`                ``stk.push(!stk.top());`
`        ``}`
`        ``// global sign is popped out which`
`        ``// was pushed in for the last bracket`
`        ``else` `if` `(s[i] == ``')'``) `
`            ``stk.pop();`
`        `
`        ``else` `{`
`            ``// global sign is positive (we use different `
`            ``// values in two calls of functions so that`
`            ``// we finally check if all vector elements`
`            ``// are 0.`
`            ``if` `(stk.top())                 `
`                ``v[s[i] - ``'a'``] += (adjSign(s, i) ? add ? 1 : -1 : `
`                                                  ``add ? -1 : 1);`
`            ``// global sign is negative here`
`            ``else`
`                ``v[s[i] - ``'a'``] += (adjSign(s, i) ? add ? -1 : 1 : `
`                                                  ``add ? 1 : -1);`
`        ``}`
`        ``i++;`
`    ``}`
`};`
`// Returns true if expr1 and expr2 represent`
`// same expressions`
`bool` `areSame(string expr1, string expr2)`
`{`
`    ``// Create a vector for all operands and`
`    ``// initialize the vector as 0.`
`    ``vector<``int``> v(MAX_CHAR, 0);`
`    ``// Put signs of all operands in expr1`
`    ``eval(expr1, v, ``true``);`
`    ``// Subtract signs of operands in expr2`
`    ``eval(expr2, v, ``false``);`
`    ``// If expressions are same, vector must `
`    ``// be 0.`
`    ``for` `(``int` `i = 0; i < MAX_CHAR; i++) `
`        ``if` `(v[i] != 0) `
`            ``return` `false``;`
`    ``return` `true``;`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``string expr1 = ``"-(a+b+c)"``, expr2 = ``"-a-b-c"``;`
`    ``if` `(areSame(expr1, expr2))`
`        ``cout << ``"Yes\n"``;`
`    ``else`
`        ``cout << ``"No\n"``;`
`    ``return` `0;`
`}`

Output:

```YES

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/check-two-expressions-brackets/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Identify and mark unmatched parenthesis in an expression

Given an expression, find and mark matched and unmatched parenthesis in it. We need to replace all balanced opening parenthesis with 0, balanced closing parenthesis with 1 and all unbalanced with -1.

Examples:

```Input : ((a)
Output : -10a1

Input : (a))
Output : 10a-1

Input  : (((abc))((d)))))
Output : 000abc1100d111-1-1```

The idea is based on stack. We run a loop from the start of the string upto end and for every ‘(‘, we push it into stack. If stack is empty and we encounter an closing bracket ‘)’ the we replace -1 at that index of the strig. Else we replace all opening brackets ‘(‘ with 0 and closing brackets with 1. Then pop from the stack.

`// CPP program to mark balanced and unbalanced`
`// parenthesis.`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`void` `identifyParenthesis(string a)`
`{`
`    ``stack<``int``> st;`
`    ``// run the loop upto end of the string`
`    ``for` `(``int` `i = 0; i < a.length(); i++) {`
`        ``// if a[i] is opening bracket then push `
`        ``// into stack`
`        ``if` `(a[i] == ``'('``) `
`            ``st.push(i);`
`        `
`        ``// if a[i] is closing bracket ')' `
`        ``else` `if` `(a[i] == ``')'``) {`
`            ``// If this closing bracket is unmatched`
`            ``if` `(st.empty()) `
`                ``a.replace(i, 1, ``"-1"``);`
`            `
`            ``else` `{`
`                ``// replace all opening brackets with 0`
`                ``// and closing brackets with 1`
`                ``a.replace(i, 1, ``"1"``);`
`                ``a.replace(st.top(), 1, ``"0"``);`
`                ``st.pop();`
`            ``}`
`        ``}`
`    ``}`
`    ``// if stack is not empty then pop out all`
`    ``// elements from it and replace -1 at that`
`    ``// index of the string`
`    ``while` `(!st.empty()) {`
`        ``a.replace(st.top(), 1, ``"-1"``);`
`        ``st.pop();`
`    ``}`
`    ``// print final string`
`    ``cout << a << endl;`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``string str = ``"(a))"``;`
`    ``identifyParenthesis(str);`
`    ``return` `0;`
`}`

Output:

```0a1-1

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/identify-mark-unmatched-parenthesis-expression/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Move To Front Data Transform Algorithm

What is the MTF transform?
The MTF (Move to Front) is a data transformation algorithm that restructures data in such a way that the transformed message is more compressible and therefore used as an extra step in compression. Technically, it is an invertible transform of a sequence of input characters to an array of output numbers.

Why MTF?
1. In many cases, the output array gives frequently repeated characters’ lower indexes which is useful in data compression algorithms.

2. It is first of the three steps to be performed in succession while implementing Burrows – Wheeler Data Compression algorithm that forms the basis of the Unix compression utility bzip2.

The main idea behind MTF:

1. The primary idea behind MTF is to maintain an ordered list of legal symbols (a to z, in our example).

2. Read one character at a time from input string .

3. Print out the position at which that character appears in the list.

4. Move that character to front of the list and repeat the process until indexes for all input characters are obtained.

```Illustration for "panama".
List initially contains English alphabets in order.
We one by one characters of input to front.

input_str chars   output_arr       list
p              15               abcdefghijklmnopqrstuvwxyz
a              15 1             pabcdefghijklmnoqrstuvwxyz
n              15 1 14          apbcdefghijklmnoqrstuvwxyz
a              15 1 14 1        napbcdefghijklmoqrstuvwxyz
m              15 1 14 1 14     anpbcdefghijklmoqrstuvwxyz
a              15 1 14 1 14     manpbcdefghijkloqrstuvwxyz
```

Inference:
1. If the letters occur many times in the input, then many of the output values will be small integers such as 0, 1, 2 etc.

2. Thus, encoding extremely high frequency of these letters makes an ideal scenario forHuffman Coding.

Examples:

```Input : panama
Output : 15 1 14 1 14 1
```

Following is the code for idea explained above:

`// C program to find move to front transform of`
`// a given string`
`#include <stdio.h>`
`#include <stdlib.h>`
`#include <string.h>`
`// Returns index at which character of the input text`
`// exists in the list`
`int` `search(``char` `input_char, ``char``* list)`
`{`
`    ``int` `i;`
`    ``for` `(i = 0; i < ``strlen``(list); i++) {`
`        ``if` `(list[i] == input_char) {`
`            ``return` `i;`
`            ``break``;`
`        ``}`
`    ``}`
`}`
`// Takes curr_index of input_char as argument`
`// to bring that character to the front of the list`
`void` `moveToFront(``int` `curr_index, ``char``* list)`
`{`
`    ``char``* record = (``char``*)``malloc``(``sizeof``(``char``) * 26);`
`    ``strcpy``(record, list);`
`    ``// Characters pushed one position right`
`    ``// in the list up until curr_index`
`    ``strncpy``(list + 1, record, curr_index);`
`    ``// Character at curr_index stored at 0th position`
`    ``list[0] = record[curr_index];`
`}`
`// Move to Front Encoding`
`void` `mtfEncode(``char``* input_text, ``int` `len_text, ``char``* list)`
`{`
`    ``int` `i;`
`    ``int``* output_arr = (``int``*)``malloc``(len_text * ``sizeof``(``int``));`
`    ``for` `(i = 0; i < len_text; i++) {`
`        ``// Linear Searches the characters of input_text `
`        ``// in list`
`        ``output_arr[i] = search(input_text[i], list);`
`        ``// Printing the Move to Front Transform`
`        ``printf``(``"%d "``, output_arr[i]);`
`        ``// Moves the searched character to the front `
`        ``// of the list`
`        ``moveToFront(output_arr[i], list);`
`    ``}`
`}`
`// Driver program to test functions above`
`int` `main()`
`{`
`    ``char``* input_text = ``"panama"``;`
`    ``int` `len_text = ``strlen``(input_text);`
`    ``// Maintains an ordered list of legal symbols`
`    ``char``* list = (``char``*)``malloc``(``sizeof``(``char``) * 26);`
`    ``strcpy``(list, ``"abcdefghijklmnopqrstuvwxyz"``);`
`    ``printf``(``"Input text: %s"``, input_text);`
`    ``printf``(``"\nMove to Front Transform: "``);`
`    ``// Computes Move to Front transform of given text`
`    ``mtfEncode(input_text, len_text, list);`
`  `
`    ``return` `0;`
`}`

Output:

```Input text: panama
Move to Front Transform: 15 1 14 1 14 1
```

Time Complexity: O(n^2)

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/move-front-data-transform-algorithm/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Palindrome Substring Queries

Given a string and several queries on the substrings of the given input string to check whether the substring is a palindrome or not.

Examples :
Suppose our input string is “abaaabaaaba” and the queries- [0, 10], [5, 8], [2, 5], [5, 9]

We have to tell that the substring having the starting and ending indices as above is a palindrome or not.

[0, 10] → Substring is “abaaabaaaba” which is a palindrome.
[5, 8] → Substring is “baaa” which is not a palindrome.
[2, 5] → Substring is “aaab” which is not a palindrome.
[5, 9] → Substring is “baaab” which is a palindrome.

Let us assume that there are Q such queries to be answered and N be the length of our input string. There are the following two ways to answer these queries

Method 1 (Naive)

One by one we go through all the substrings of the queries and check whether the substring under consideration is a palindrome or not.

Since there are Q queries and each query can take O(N) worse case time to answer, this method takes O(Q.N) time in the worst case. Although this is an in-place/space-efficient algorithm, but still there are more efficient method to do this.

Method 2 (Cumulative Hash)

The idea is similar to Rabin Karp string matching. We use string hashing. What we do is that we calculate cumulative hash values of the string in the original string as well as the reversed string in two arrays- prefix[] and suffix[].

How to calculate the cumulative hash values ?

Suppose our string is str[], then the cumulative hash function to fill our prefix[] array used is-

```prefix[0] = 0
prefix[i] = str[0] + str[1] * 101 + str[2] * 1012 +
...... + str[i-1] * 101i-1

For example, take the string- “abaaabxyaba”

prefix[0] = 0
prefix[1] = 97  (ASCII Value of ‘a’ is 97)
prefix[2] = 97 + 98 * 101
prefix[3] = 97 + 98 * 101 + 97 * 1012
...........................
...........................
prefix[11] = 97 + 98 * 101 + 97 * 1012 +
........+ 97 * 10110```

Now the reason to store in that way is that we can easily find the hash value of any substring in O(1) time using-

``` hash(L, R) = prefix[R+1] – prefix[L]
```

For example, hash (1, 5) = hash (“baaab”) = prefix[6] – prefix[1] = 98 * 101 + 97 * 1012 + 97 * 1013 + 97 * 1014 + 98 * 1015 = 1040184646587 [We will use this weird value later to explain what’s happening].

Similar to this we will fill our suffix[] array as-

```suffix[0] = 0
suffix[i] = str[n-1] + str[n-2] * 101 + str[n-3] * 1012 +
...... + str[n-i] * 101i-1

For example, take the string- “abaaabxyaba”

suffix[0] = 0
suffix[1] = 97  (ASCII Value of ‘a’ is 97)
suffix[2] = 97 + 98 * 101
suffix[3] = 97 + 98 * 101 + 97 * 1012
...........................
...........................
suffix[11] = 97 + 98 * 101 + 97 * 1012 + ........+ 97 * 10110```

Now the reason to store in that way is that we can easily find the reverse hash value of any substring in O(1) time using

`reverse_hash(L, R) = hash (R, L) = suffix[n-L] – suffix[n-R-1]`

where n = length of string.

For “abaaabxyaba”, n = 11
reverse_hash(1,5) = reverse_hash(“baaab”) = hash(“baaab”) [Reversing “baaab” gives “baaab”]

hash(“baaab”) = suffix[11-1] – suffix[11-5-1] = suffix[10] – suffix[5] = 98 * 1015 + 97 * 1016 + 97 * 1017 + 97 * 1018 + 98 * 1019 = 108242031437886501387

Now there doesn’t seem to be any relation between these two weird integers – 1040184646587 and 108242031437886501387

Think again. Is there any relation between these two massive integers ?

Yes, there is and this observation is the core of this program/article.

1040184646587 * 1014 = 108242031437886501387

Try thinking about this and you will find that any substring starting at index- L and ending at index- R (both inclusive) will be a palindrome if

```(prefix[R + 1] – prefix[L]) / (101L)  =
(suffix [n - L] – suffix [n – R- 1] ) / (101n – R - 1)
```

The rest part is just implementation.

The function computerPowers() in the program computes the powers of 101 using dynamic programming.

Overflow Issues:
As, we can see that the hash values and the reverse hash values can become huge for even the small strings of length – 8. Since C and C++ doesn’t provide support for such large numbers, so it will cause overflows. To avoid this we will take modulo of a prime (a prime number is chosen for some specific mathematical reasons). We choose the biggest possible prime which fits in an integer value. The best such value is 1000000007. Hence all the operations are done modulo 1000000007.

However Java and Python has no such issues and can be implemented without the modulo operator.

The fundamental modulo operations which are used extensively in the program are listed below.
(a + b) %M = (a %M + b % M) % M
(a + b + c) % M = (a % M + b % M + c % M) % M
(a + b + c + d) % M = (a % M + b % M + c % M+ d% M) % M
…. ….. ….. ……
…. ….. ….. ……

2) Multiplication-
(a * b) % M = (a * b) % M
(a * b * c) % M = ((a * b) % M * c % M) % M
(a * b * c * d) % M = ((((a * b) % M * c) % M) * d) % M
…. ….. ….. ……
…. ….. ….. ……

This property is used by modPow() function which computes power of a number modulo M
3) Mixture of addition and multiplication-
(a * x + b * y + c) % M = ( (a * x) % M +(b * y) % M+ c % M ) % M

4) Subtraction-
(a – b) % M = (a % M – b % M + M) % M [Correct]
(a – b) % M = (a % M – b % M) % M [Wrong]

5) Division-
(a / b) % M = (a * MMI(b)) % M

Where MMI() is a function to calculate Modulo Multiplicative Inverse. In our program this is implemented by the function- findMMI().

`/* A C++ program to answer queries to check whether`
`   ``the substrings are palindrome or not efficiently */`
`#include<bits/stdc++.h>`
`using` `namespace` `std;`
`#define p 101`
`#define MOD 1000000007`
`// Structure to represent a query. A query consists`
`// of (L,R) and we have to answer whether the substring`
`// from index-L to R is a palindrome or not`
`struct` `Query`
`{`
`    ``int` `L, R;`
`};`
`// A function to check if a string str is palindrome`
`// in the ranfe L to R`
`bool` `isPalindrome(string str, ``int` `L, ``int` `R)`
`{`
`    ``// Keep comparing characters while they are same`
`    ``while` `(R > L)`
`        ``if` `(str[L++] != str[R--])`
`            ``return``(``false``);`
`    ``return``(``true``);`
`}`
`// A Function to find pow (base, exponent) % MOD`
`// in log (exponent) time`
`unsigned ``long` `long` `int` `modPow(unsigned ``long` `long` `int` `base,`
`                              ``unsigned ``long` `long` `int` `exponent)`
`{`
`    ``if` `(exponent == 0)`
`        ``return` `1;`
`    ``if` `(exponent == 1)`
`        ``return` `base;`
`    ``unsigned ``long` `long` `int` `temp = modPow(base, exponent/2);`
`    ``if` `(exponent %2 ==0)`
`        ``return` `(temp%MOD * temp%MOD) % MOD;`
`    ``else`
`        ``return` `((( temp%MOD * temp%MOD)%MOD) * base%MOD) % MOD;`
`}`
`// A Function to calculate Modulo Multiplicative Inverse of 'n'`
`unsigned ``long` `long` `int` `findMMI(unsigned ``long` `long` `int` `n)`
`{`
`    ``return` `modPow(n, MOD-2);`
`}`
`// A Function to calculate the prefix hash`
`void` `computePrefixHash(string str, ``int` `n, unsigned ``long` `long`
`                       ``int` `prefix[], unsigned ``long` `long` `int` `power[])`
`{`
`    ``prefix[0] = 0;`
`    ``prefix[1] = str[0];`
`    ``for` `(``int` `i=2; i<=n; i++)`
`        ``prefix[i] = (prefix[i-1]%MOD +`
`                    ``(str[i-1]%MOD * power[i-1]%MOD)%MOD)%MOD;`
`    ``return``;`
`}`
`// A Function to calculate the suffix hash`
`// Suffix hash is nothing but the prefix hash of`
`// the reversed string`
`void` `computeSuffixHash(string str, ``int` `n,`
`                       ``unsigned ``long` `long` `int` `suffix[],`
`                       ``unsigned ``long` `long` `int` `power[])`
`{`
`    ``suffix[0] = 0;`
`    ``suffix[1] = str[n-1];`
`    ``for` `(``int` `i=n-2, j=2; i>=0 && j<=n; i--,j++)`
`        ``suffix[j] = (suffix[j-1]%MOD +`
`                     ``(str[i]%MOD * power[j-1]%MOD)%MOD)%MOD;`
`    ``return``;`
`}`
`// A Function to answer the Queries`
`void` `queryResults(string str, Query q[], ``int` `m, ``int` `n,`
`                  ``unsigned ``long` `long` `int` `prefix[],`
`                  ``unsigned ``long` `long` `int` `suffix[],`
`                  ``unsigned ``long` `long` `int` `power[])`
`{`
`    ``for` `(``int` `i=0; i<=m-1; i++)`
`    ``{`
`        ``int` `L = q[i].L;`
`        ``int` `R = q[i].R;`
`        ``// Hash Value of Substring [L,R]`
`        ``unsigned ``long` `long` `hash_LR =`
`            ``((prefix[R+1]-prefix[L]+MOD)%MOD *`
`             ``findMMI(power[L])%MOD)%MOD;`
`        ``// Reverse Hash Value of Substring [L,R]`
`        ``unsigned ``long` `long` `reverse_hash_LR =`
`            ``((suffix[n-L]-suffix[n-R-1]+MOD)%MOD *`
`             ``findMMI(power[n-R-1])%MOD)%MOD;`
`        ``// If both are equal then the substring is a palindrome`
`        ``if` `(hash_LR == reverse_hash_LR )`
`        ``{`
`            ``if` `(isPalindrome(str, L, R) == ``true``)`
`                ``printf``(``"The Substring [%d %d] is a "`
`                       ``"palindrome\n"``, L, R);`
`            ``else`
`                ``printf``(``"The Substring [%d %d] is not a "`
`                       ``"palindrome\n"``, L, R);`
`        ``}`
`        ``else`
`            ``printf``(``"The Substring [%d %d] is not a "`
`                   ``"palindrome\n"``, L, R);`
`    ``}`
`    ``return``;`
`}`
`// A Dynamic Programming Based Approach to compute the`
`// powers of 101`
`void` `computePowers(unsigned ``long` `long` `int` `power[], ``int` `n)`
`{`
`    ``// 101^0 = 1`
`    ``power[0] = 1;`
`    ``for``(``int` `i=1; i<=n; i++)`
`        ``power[i] = (power[i-1]%MOD * p%MOD)%MOD;`
`    ``return``;`
`}`
`/* Driver program to test above function */`
`int` `main()`
`{`
`    ``string str = ``"abaaabaaaba"``;`
`    ``int` `n = str.length();`
`    ``// A Table to store the powers of 101`
`    ``unsigned ``long` `long` `int` `power[n+1];`
`    ``computePowers(power, n);`
`    ``// Arrays to hold prefix and suffix hash values`
`    ``unsigned ``long` `long` `int` `prefix[n+1], suffix[n+1];`
`    ``// Compute Prefix Hash and Suffix Hash Arrays`
`    ``computePrefixHash(str, n, prefix, power);`
`    ``computeSuffixHash(str, n, suffix, power);`
`    ``Query q[] = {{0, 10}, {5, 8}, {2, 5}, {5, 9}};`
`    ``int` `m = ``sizeof``(q)/``sizeof``(q[0]);`
`    ``queryResults(str, q, m, n, prefix, suffix, power);`
`    ``return` `(0);`
`}`

Output :

```The Substring [0 10] is a palindrome
The Substring [5 8] is not a palindrome
The Substring [2 5] is not a palindrome
The Substring [5 9] is a palindrome

```

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/palindrome-substring-queries/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at

#technicalguide

## Find if there is a subarray with 0 sum

Given an array of positive and negative numbers, find if there is a subarray (of size at-least one) with 0 sum.

Examples:

```Input: {4, 2, -3, 1, 6}
Output: true
There is a subarray with zero sum from index 1 to 3.

Input: {4, 2, 0, 1, 6}
Output: true
There is a subarray with zero sum from index 2 to 2.

Input: {-3, 2, 3, 1, 6}
Output: false
There is no subarray with zero sum.```

simple solution is to consider all subarrays one by one and check the sum of every subarray. We can run two loops: the outer loop picks a starting point i and the inner loop tries all subarrays starting from i. Time complexity of this method is O(n2).

We can also use hashing. The idea is to iterate through the array and for every element arr[i], calculate sum of elements form 0 to i (this can simply be done as sum += arr[i]). If the current sum has been seen before, then there is a zero sum array. Hashing is used to store the sum values, so that we can quickly store sum and find out whether the current sum is seen before or not.

Example :

```arr[] = {1, 4, -2, -2, 5, -4, 3}

If we consider all prefix sums, we can
notice that there is a subarray with 0
sum when :
1) Either a prefix sum repeats or
2) Or prefix sum becomes 0.

Prefix sums for above array are:
1, 5, 3, 1, 6, 2, 5

Since prefix sum 1 repeats, we have a subarray
with 0 sum.
```

Following is implementation of the above approach.

`// A C++ program to find if there is a zero sum`
`// subarray`
`#include <bits/stdc++.h>`
`using` `namespace` `std;`
`bool` `subArrayExists(``int` `arr[], ``int` `n)`
`{`
`    ``unordered_map<``int``,``bool``> sumMap;`
`    ``// Traverse throught array and store prefix sums`
`    ``int` `sum = 0;`
`    ``for` `(``int` `i = 0 ; i < n ; i++)`
`    ``{`
`        ``sum += arr[i];`
`        ``// If prefix sum is 0 or it is already present`
`        ``if` `(sum == 0 || sumMap[sum] == ``true``)`
`            ``return` `true``;`
`        ``sumMap[sum] = ``true``;`
`    ``}`
`    ``return` `false``;`
`}`
`// Driver code`
`int` `main()`
`{`
`    ``int` `arr[] =  {-3, 2, 3, 1, 6};`
`    ``int` `n = ``sizeof``(arr)/``sizeof``(arr[0]);`
`    ``if` `(subArrayExists(arr, n))`
`        ``cout << ``"Found a subarray with 0 sum"``;`
`    ``else`
`        ``cout << ``"No Such Sub Array Exists!"``;`
`    ``return` `0;`
`}`

Output:

`Found a subarray with 0 sum`

Time Complexity of this solution can be considered as O(n) under the assumption that we have good hashing function that allows insertion and retrieval operations in O(1) time.

Disclaimer: This does not belong to TechCodeBit, its an article taken from the below
source and credits.
source and credits:http://www.geeksforgeeks.org/find-if-there-is-a-subarray-with-0-sum/
We have built the accelerating growth-oriented website for budding engineers and aspiring job holders of technology companies such as Google, Facebook, and Amazon
If you would like to study our free courses you can join us at