Palindrome index

Problem Statement

You are given a string of lower case letters. Your task is to figure out the index of the character on whose removal it will make the string a palindrome. There will always be a valid solution.

In case the string is already a palindrome, then -1 is also a valid answer along with possible indices.

Input Format

The first line contains T, i.e. the number of test cases.
T lines follow, each containing a string.

Output Format

Print the position (0 index) of the letter by removing which the string turns into a palindrome. For a string, such as

bcbc

we can remove b at index 0 or c at index 3. Both answers are accepted.

Constraints
1≤T≤20
1≤ length of string ≤100005
All characters are Latin lower case indexed.

Sample Input

3
aaab
baa
aaa

Sample Output

3
0
-1

Explanation

In the given input, T = 3,

• For input aaab, we can see that removing b from the string makes the string a palindrome, hence the position 3.
• For input baa, removing b from the string makes the string palindrome, hence the position 0.
• As the string aaa is already a palindrome, you can output 0, 1 or 2 as removal of any of the characters still maintains the palindrome property. Or you can print -1 as this is already a palindrome.

JAVA Program 

import java.io.*;
import java.util.*;

public class Solution {
    
    public static int isPallindrome(String string){
        for(int i = 0; i< string.length()/2 ; i++){
            if(string.charAt(i) != string.charAt(string.length() - i -1)){
                return 0;
            }
        }
        return 1;
    }
    public static int pallindromeIndex(String string, int start, int end){
        if(start >= end-1){
            return -1;
        }else{
            if(string.charAt(start) == string.charAt(end-1)){
                return pallindromeIndex(string, start + 1, end - 1);
            }else{
                String temp = string.substring(start , end -1 );
                if(isPallindrome(temp) == 1){
                    return end - 1;
                }else{
                    return start;
                }
            }
        }
       
    }
    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in = new Scanner(System.in);
        int K = in.nextInt();
        for(int i = 0; i<K; i++){
            String string = in.next();
            int index = pallindromeIndex(string, 0, string.length());
            System.out.println(index);
        }
    }
}

================================================================

C Program :
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {

    /* Enter your code here. Read input from STDIN. Print output to STDOUT */ 
    int t, i;
    scanf("%d",&t);
    for( i = 0 ; i < t ; i ++ )
        {
        char *in;
        int len, j, k, index = -1; 
        scanf("%ms",&in);
        len = strlen(in);
        j = 0;
        k = len - 1; 
        while( j < len/2 )
            {
            if( in[k] != in[j] )
                {
                if( in[j + 1] == in[k] && in[k - 1] != in[j] )
                    {
                    index = j;
                    break;
                }
                else if( in[j + 1] != in[k] && in[k - 1] == in[j])
                    {
                    index = k;
                    break;
                }               
                else 
                    {
                    int l;
                    for( l = 2 ; j+l < len/2 && in[j+l] == in[k-l-1] ; l++);
                    if(j+l == len/2)
                        {
                        index = k;
                        break;
                    }
                    for( l = 3 ; j+l <= len/2 && in[j+l] == in[k-l+1] ; l++);
                    if(j+l == len/2 + 1)
                        {
                        index = j;
                        break;
                    }
                    
                }
                    
            }
            j++;
            k--;
        }
            printf("%d\n",index);
    }
    return 0;
}

Tree: Huffman Decoding

Problem Statement

Huffman coding assigns variable length codewords to fixed length input characters based on their frequencies. More frequent characters are assigned shorter codewords and less frequent characters are assigned longer codewords. A huffman tree is made for the input string and characters are decoded based on their position in the tree. We add a '0' to the codeword when we move left in the binary tree and a '1' when we move right in the binary tree. We assign codes to the leaf nodes which represent the input characters.

For example :

        {ϕ,5}
     0 /     \ 1
    {ϕ,2}   {A,3}
   0/   \1
{B,1}  {C,1}  

Input characters are only present on the leaves. Internal nodes have a character value of ϕ. Codewords:

A - 1
B - 00
C - 01

No codeword appears as a prefix of any other codeword. Huffman encoding is a prefix free encoding technique.

Encoded String "1001011" represents the string "ABACA"

You have to decode an encoded string using the huffman tree.

You are given pointer to the root of the huffman tree and a binary coded string. You need to print the actual string.

Input Format

You are given a function,

void decode_huff(node * root, string s)
{

}

The structure for node is defined as :

struct node
{
    int freq;
    char data;
    node * left;
    node * right;

}node;    

Note: 
Internal nodes have data='\0'(ϕ )

Output Format

Output the decoded string on a single line.

Sample Input

         {ϕ,5}
      0 /     \ 1
     {ϕ,2}   {A,3}
    0/   \1
{B,1}  {C,1}  

S="1001011"

Sample Output

ABACA

Explanation

S="1001011"
Processing the string from left to right.
S[0]='1' : we move to the right child of the root. We encounter a leaf node with value 'A'. We add 'A' to the decoded string.
We move back to the root.

S[1]='0' : we move to the left child. 
S[2]='0' : we move to the left child. We encounter a leaf node with value 'B'. We add 'B' to the decoded string.
We move back to the root.

S[3] = '1' : we move to the right child of the root. We encounter a leaf node with value 'A'. We add 'A' to the decoded string.
We move back to the root.

S[4]='0' : we move to the left child. 
S[5]='1' : we move to the right child. We encounter a leaf node with value C'. We add 'C' to the decoded string.
We move back to the root.

 S[6] = '1' : we move to the right child of the root. We encounter a leaf node with value 'A'. We add 'A' to the decoded string.
We move back to the root.

Decoded String = "ABACA"

/* 
The structure of the node is

typedef struct node
{
    int freq;
    char data;
    node * left;
    node * right;
    
}node;

*/
void decode_huff(node * root,string s)
{
    int i = 0;
    node* temp = root;
    if(root == NULL){
        return;
    }
   
    while(s[i] == '0' || s[i] == '1'){
        if(s[i] == '0' && temp->left != NULL){
            temp = temp->left;
        }else if(s[i] == '1' && temp->right != NULL){
            temp = temp->right;
        }
        if(temp->left == NULL && temp->right == NULL){
            cout<<temp->data;
            temp = root;
        }
        i++;
    }
}

Fibonacci Modified

Problem Statement

A series is defined in the following manner:

Given the nth and (n+1)th terms, the (n+2)th can be computed by the following relation 
Tn+2 = (Tn+1)2 + Tn

So, if the first two terms of the series are 0 and 1: 
the third term = 12 + 0 = 1 
fourth term = 12 + 1 = 2 
fifth term = 22 + 1 = 5 
... And so on.

Given three integers A, B and N, such that the first two terms of the series (1st and 2nd terms) are A and B respectively, compute the Nth term of the series.

Input Format

You are given three space separated integers A, B and N on one line.

Input Constraints 
0 <= A,B <= 2 
3 <= N <= 20

Output Format

One integer. 
This integer is the Nth term of the given series when the first two terms are A and Brespectively.

Note

• Some output may even exceed the range of 64 bit integer.

Sample Input

0 1 5  

Sample Output

5

Explanation

The first two terms of the series are 0 and 1. The fifth term is 5. How we arrive at the fifth term, is explained step by step in the introductory sections.

import java.io.*;

import java.util.*;

import java.math.*;

public class Solution {

    public static void main(String[] args) {

        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */

        Scanner in = new Scanner(System.in);

        BigInteger A = in.nextBigInteger();

        BigInteger B = in.nextBigInteger();

        int N = in.nextInt();

        BigInteger[] table = new BigInteger[N];

        table[0] = A;

        table[1] = B;

        for(int i=2; i<N; i++){

            table[i] = table[i-1].pow(2).add(table[i-2]);

        }

        System.out.println(table[N-1]);

    }

}