CareerCup

import math

def how_many_bits(x):
  count = 0
  while x:
    x = x & (x - 1)
    count += 1
  return count

def how_many_bit(x):
  return 1 + int(math.log(x,2))

def foo(x):
  top_bit = x&-x
  higher_bit_set = top_bit + x
  mask = higher_bit_set ^ x
  mask = mask>>how_many_bit(top_bit)
  mask = mask >> 1
  return mask + higher_bit_set

x = 3
for i in range(20):
  y = foo(x)
  print(y)
  if how_many_bits(y) != 2:
    print("something wrong", y, how_many_bits(y), bin(y))
  x = y

Simple backtracking will help
1. Sort the string (954311)
2. if sorted string is divided by 3, return the result.
3. remove one by one from the end and check if it is divisible by 3. In case of 954311, we start with removing last '1'. As 9431 is not divisible by 3 put the 1 back and do the same with same with next 1 and so on. You will realize only when you remove 5 you will get the rest of the number divisible by 3.
4. Concept is very similar to 8 queen problem but just here instead here the constraint is divisibility by 3.

Found a better solution:
Let's start with a element 'x'. Every element when you are adding to 'x' will either increase it by 1 or by 2 for sure right when doing mod by 3.Think about this.

Now all you have to do is to figure out which "bad" apples are causing the sum to be not divisible by 3.

sum of entire array mod 3 will let you know, how much offset you are from being divisible by 3. It can be either by 1 or by 2 right?
example 12331 sum of this is (1+2+3+3+1)%3=1

Now sort the entire array. This step is intuitive right? After that you just have to go from end to beginning figuring out which array element mod 3 is giving me the offset we calculated earlier.

You will also notice that maximum of 2 elements should be removed to make any digit greater than 2 to be divisible by 3. Right? As explained earlier, if you add any two random or same digits to existing sum the entire sum will be divisible by 3.
proof:
x + a + b
if x is not divisible by 3 then adding 'a' and adding 'b' will make it divisible by 3 because adding 'a' will increase the sum by either 0,1 or 2. and in all cases when adding 'a' and 'b' the entire sum becomes divisible by 3.

Code

def foo(a):
  a = sorted([int(i) for i in a], reverse=True)
  s = sum([int(i) for i in a])
  if s%3 == 0:
    return a
  
  mod = s%3
  n = len(a)
  index_to_be_removed = []
  #if no >= 3, there has to be answer 
  for i in range(2):
    if index_to_be_removed:
      break
    for j in range(n-1, 0, -1):
      if a[j]%3 == mod:
        index_to_be_removed.append(j)
        break
      if i:
        for k in range(j):
          if not a[k]%3 or not a[j]%3:
            continue
          if (a[j] + a[k])%3 == mod:
            index_to_be_removed.append(j)
            index_to_be_removed.append(k)
  for i in index_to_be_removed:
    a = a[0:i]+a[i+1:]  
  print("".join([str(i) for i in a]))

foo("6532")

It is the same question as "find out maximum in the window of size K in an array." To answer this you have to use the priority queue and such. Basically here what we have to do is this:
Use the queue for this and its size should be equal "K".
1. Put the first element in the queue.
2. Put the second element in the queue but before doing that compare its value to the top of the queue and see if its value is greater. If it is, then remove the top of the queue until the top of the queue is no longer more that the element which you are going to insert or there is no longer any element in the queue.
3. Do the same for all the successive elements.
4.After you have inserted K elements remove from the bottom of the queue and that will be the largest element in the queue. Do this for every window of size K i.e. after you have found the biggest element in the window size of K initially, you should do the same whenever you are inserting a new element. Why? Because the new element addition will be the new window of size K.

can you explain more with examples?

#include <stdio.h>

void swap(char *s, int i, int j)
{
	char temp = s[i];
	s[i] = s[j];
	s[j] = temp;
}

void foo(char *s, int j, int len)
{
	int i;
	if (j == len-1) {
		printf("%s\n", s);
		return;
	}
	for (i=j;i<len;i++) {
		swap(s, i, j);
		foo(s, j+1, len);
		swap(s, i, j);
	}
}

int main()
{
	char s[] = "abc";
	foo(s, 0, strlen(s));
}

nice logic.

def frequency(input, n):
	for i in range(0, len(input)):
		input[i] *= (n+1)
	for i in range(0, len(input)):
		input[input[i]/(n+1)] += 1
	for i in range(0, len(input)):
		input[i] = input[i]%(n+1)
	return input

input = [1, 2, 3, 4, 1, 1, 2, 4, 7]
print(frequency(input, 7))

question is not clear.

import random as rd 
    
    def prob200(half):
    	if half >= 200:
    		return 0	
    	#f1 can be replaced by this rd.randint(0, 1)
    	toss_value = f1() 
    	# check if toss falls in this current half and then change the half for next recursion. 
    	# we change half from 1, 2, 4, 8, 16, 36, 64, 128
    	result = toss_value*half + prob200(half<<1)
    	if result > 200:
    		return prob200(1)
    	else:
    		return result
    
    for i in range(0, 10):
    	print(prob200(1))

def convert_to_alphabet(no, map):
    	no = int(no)
    	result = []
    	while no > 25:
    		rem = no%25
    		no = int(no/25)
    		result.append(map[str(rem)])
    	result.append(map[str(no)])
    	return result
    	
    map = {"0":"Z","1":"A", "2":"B", "3":"C", "4":"D", "5":"E", "6":"F", "7":"G", "8":"H", "9":"I", "10":"J", "11":"K","12":"L","13":"M","14":"N","15":"O","16":"P","17":"Q","18":"R","19":"S","20":"T","21":"U","22":"V","23":"W","24":"X","25":"Y"}
    input = "7 1 25 26 27 51 52 676"
    input = input.split(" ")
    print(input)
    for i in input:
    	print("".join(convert_to_alphabet(i, map)))

Sort it and then go to the middle of the array and pull out the element and put that in the end of the output array.

After sorting
1 2 3 4 5 6
If size of the array is even or odd you will do accordingly pull out the array element from the middle. After that you start going from mid to start and mid to end and pull out elements and put it in alternate places in the output array. You should use recursion or iterative approach, either will work.
6 1 5 2 4 3

def sort(value):
    map = {}
    result = ""
    print "input", value
    for i in value:
        if i in map.keys():
            map[i] += 1
        else:
            map[i] = 1
    for i in range(9, -1, -1):
        i = str(i)
        while i in map.keys() and map[i] > 0:
            result += i
            map[i] = int(map[i]) -1
    return result

result = sort("1244522398968")
print "output", result

This is a flawed question at best. Significance of sleep might be for mutual exclusion so that they don't interfere with printing.

import random as rd

class node:
			def __init__(self, data):
				self.data = data
				self.l = None
				self.r = None
				self.n = None
				self.next = None
				
class tree:
		def __init__(self):
			self.root = None
		
		def get_root(self):
			return self.root
		
		def add_node(self, node):
			if (self.root == None):
				self.root = node
			else:
				self.__add_node(self.root, node)
		
		def __add_node(self, root, node):
			if (node.data < root.data):
				if (root.l != None):
					self.__add_node(root.l, node)
				else:
					root.l = node
			else:
				if (root.r != None):
					self.__add_node(root.r, node)
				else:
					root.r = node

def height(node):
		if node == None:
			return 0
		else:
			return 1 + max(height(node.l), height(node.r))
			
def get_max(node):
	if node == None:
		return 0
	if node.l == None and node.r == None:
		return 1
	left = height(node.l)
	right = height(node.r)
	return max(get_max(node.l), max(get_max(node.r), 1 + left + right))

i = tree()
r = input("enter the number")
print("adding data to the tree")
for j in range(0, int(r)):
	number = rd.randint(0, 100)
	print(number)
	i.add_node(node(number))
print("max", get_max(i.get_root()))

how will you print the nodes on the same level as you don't have the root node? Is additional information missing such as the node also have pointer to the parent node?

do zig-zag breadth first search and connect right or left at each level

import random as rd

K = 2
k_bckup = K
''' it means we will first connect current node to the left node and then vice versa'''
left = 1

class node:
			def __init__(self, data):
				self.data = data
				self.l = None
				self.r = None
				self.n = None
				self.next = None
				
class tree:
		def __init__(self):
			self.root = None
		
		def get_root(self):
			return self.root
		
		def add_node(self, node):
			if (self.root == None):
				self.root = node
			else:
				self.__add_node(self.root, node)
		
		def __add_node(self, root, node):
			if (node.data < root.data):
				if (root.l != None):
					self.__add_node(root.l, node)
				else:
					root.l = node
			else:
				if (root.r != None):
					self.__add_node(root.r, node)
				else:
					root.r = node
		
		def printTree(self):
			if self.root != None:
				return self._printTree(self.root)
		
		def _printTree(self, node):
			if node != None:
				self._printTree(node.l)
				print(node.data)
				self._printTree(node.r)
		
		def printNext(self):
			if self.root != None:
				return self._printNext(self.root)
		
		def _printNext(self, node):
			if node != None:
				self._printNext(node.l)
				if node.next != None:
					print(node.data, "->", node.next.data)
				self._printNext(node.r)

def insert(q, node):
		if node != None and node.l != None:
			q.append(node.l)
		if node != None and node.r != None:
			q.append(node.r)			
			
i = tree()
print("adding data to the tree")
for j in range(0, 10):
	number = rd.randint(0, 100)
	print(number)
	i.add_node(node(number))

print("printing inorder tree")
i.printTree()

print("debug")
q = []
q.append(i.get_root())
while len(q) > 0:
	size = len(q)
	prev = None
	if K == 0:
		K = k_bckup
	K -= 1
	if left == 0:
		q.sort(key=lambda x:x.data)
		q.reverse()

	while size:
		temp1 = q.pop(0)
		insert(q, temp1)
		size -= 1
		if prev != None:
			prev.next = temp1
		if size == 0:
			break
		temp2 = q.pop(0)
		insert(q, temp2)
		size -=1 
		if K == 0:
			temp1.next = temp2
			temp2.next = None
			prev = temp2
			left = not left
	
print("next printing")
i.printNext()

can you clarify the question a bit more?

zr.roman: for more pedantic guys: ideone.com/HraPTu

int main(void) {
	char *chr_pointer = {"abcdef"};
	int *a = chr_pointer;
	while (*((char *)a)!= '\0') {
    	printf("%c\n", *((char *)a));
    	a = (char *)a + 1;
	}
	return 0;
}

Google for this question and you will get many links. Below is just simple plain implementation.

# your code goes here

def get_result(operator, operand1, operand2):
	operand1 = int(operand1)
	operand2 = int(operand2)
	
	if operator == str("*"):
		return operand1*operand2;
	if operator == str("+"):
		return operand1+operand2;
	if operator == str("-"):
		return operand1-operand2;	
	if operator == str("/"):
		return operand1/operand2;
	if operator == str("="):
		return operand1 == operand2;		
		
def evaluate(expr):
	stack = []
	operand_cound = 0
	operators = ['*', '+', '-', '/', '=']
	for i in expr[::-1]:
		print i
		operand1 = None
		operator = None
		if i not in operators:
			stack.append(i)
		elif i in operators:
			operand1 = stack.pop()
			operand2 = stack.pop()
			stack.append(get_result(i, operand1, operand2))
	return stack.pop()

print evaluate("-*+4325")

#include <stdio.h>

int map[100] = {0, 1, -1, -1, -1, -1, 9, -1, 8, 6};
int foo(char *s, int size)
{
    int i=0, ret = 1, found = 0;

    /* if size is odd */
    if (size & 1) {
        char c[2];
        c[0] = s[size/2];
        c[1] = '\0';
        if (map[atoi(&c)] == -1)
            return -1;
    }

    for (i=0;i<size/2;i++) {
        char c[2];
        char d[2];
        d[0] = s[size-1-i];
        c[0] = s[i];
        c[1] = d[1] = '\0';
        if ((map[atoi(c)] == -1 || map[atoi(d)] == -1)) {
            ret = 0;
            break;
        }

        if (atoi(c) == atoi(d) || (map[atoi(c)] == atoi(d))) {
            continue;
        }
        ret = 0;
        break;
    }
    return ret;
}

int main(void) {
    char *x = "9165910199916";
    printf("%s\n", foo(x, strlen(x))?"mirror":"not mirror");
    return 0;
}

Code based on above idea.

#define SIZE 26
struct tri{
    int complete;
    struct tri *child[SIZE];
};

void insert(char *c, struct tri **t)
{
    struct tri *current = *t;
    while(*c != '\0')
    {
        int i;
        int letter = *c - 'a';
        if(current->child[letter] == NULL) {
            current->child[letter] = malloc(sizeof(*current));
            memset(current->child[letter], 0, sizeof(struct tri));
        }
        current = current->child[letter];
        c++;
    }
    current->complete = 1;
}

struct tri *t;
int flag = 0;
int found(char *c, struct tri *tt)
{
    struct tri *current = tt;

    if (current == NULL)
        return 0;
    while(*c != '\0')
    {
        int i;
        int letter = *c - 'a';
        /* if this is the first char then recurse from begining*/
        if (t->child[letter] != NULL)
            flag = found(c+1, t->child[letter]);
        if (flag == 1)
            return 1;
        if(!flag && current->child[letter] == NULL) {
            return 0;
        }
        current = current->child[letter];
        c++;
    }
    return current->complete;
}

int main()
{
    int i;
    t = malloc(sizeof(*t));
    t->complete = 0;
    memset(t, 0, sizeof(struct tri));

    insert("weathez", &t);
    insert("eather", &t);
    insert("weather", &t);
    (1 ==found("weather", t))?printf("found\n"):printf("not found\n");
    return 0;
}

@boaznahum: You don't need to do that as "abxyz" and "xyw" both will be stored in try as

|            
          a   x
        b       y 
        x        w
        y
        z

So let's take your input "abxyzw". We start the search and we find we have all the element till 'x'. Moment you get 'x' you have two options:
1. Check if the current element is equal to the head of trie and If it is equal to head of trie then call recursive search.
2. Continue till the end of current word. In this case for your given input it will return false but for the recursive search we started in point 1, it will return true.

So it is basically your search function that you need to write properly. However you had found a test case which is extremely crucial to implement the search function.

Based on the suggestion python code:

def sort_by_first(x):
	return sorted(x, key=lambda first: first[0])
	
data = [[1, 5], [10, 20]]
sorted_list = sort_by_first(data)
print sorted_list
x = sorted_list[0][0]
print_last = 1
for i in xrange(1, len(sorted_list)):
	if int(int(sorted_list[i-1][1]) + 1) < int(sorted_list[i][0]):
		print x, sorted_list[i-1][1]
		x = sorted_list[i][0]
	else:
		#find if part of previous thing
		if i == len(sorted_list)-1:
			if int(int(sorted_list[i-1][1]) + 1) >= int(sorted_list[i][0]):
				print x, sorted_list[i][1]
			else:
				print sorted_list[i]
if x == sorted_list[len(sorted_list)-1][0]:
	print sorted_list[len(sorted_list)-1]

Inorder successor has two cases:
1. If the target node has right child then return minimum value from the right child node.
2. If the target node has no right child then we need to go from the root tree to the target node as one of the parent node will be the in-order successor of the target node. 
          There are two sub cases: 
                First is if the target node is the left child of the parent node and if parent node value is more than target node then we found the in order successor.
               Second case is when target node is the right child of the parent node then in that case we should have kept the information about the ancestor of the parent node as that would be the in order successor of the target node. Obviously the parent node ancestor should have been the left child otherwise in-order successor will be NULL.No? Think about it for 2 min.

list *get_successor(list *head, list *node)
        {
                /* if node has right node get the minimum from the right node tree*/
                if (node->right) {
                        return get_min(node->right);
                } else{
                        /*get the parent node whose left child is the current node for which we are trying to find out the successor*/
                        list *current_node = head;
                        list *successor = NULL;
                        while (node != current_node) {
                                if (node->data < current_node->data) {
                                        successor = current_node;
                                        current_node = current_node->left;
                                } else {
                                        current_node = current_node->right;
                                }
                        }
                        return successor;
                }
        }

Test Input: [4, 8], [3, 5], [-1 2], [10, 12]
Sort everything as below in an array: 'e' stand for end and 's' stand for start
[-1s 2e 3s 4s 5e 8e 10s 12e]
so we need to find consecutive and adjacent. Start from 0th index in array and look for end.
-1s matches with 2e [we found start and end]
then we see 3s and after that we see 4s so we know we can continue as both are consecutive then we look at 5e so we matched 3s with 5e but we had seen 4s which means that we again have to look for one "e" so we went till 8e.
[-1, 8] is the first answer.
After that we saw 10s which started a new interval and we matched that with 12e
[10, 12]
Look at the sorted array and look at the answer you will get the logic. Please comment if you don't understand and i will probably provide some more explanation but I may be missing some test cases which i didn't think about :)

Code in c:

#define SIZE(x) sizeof(x)/sizeof(x[0])
int result[100] = {0};
int result_size;

void find_missing(int a[], int start, int end)
{
        if (start >= end)
                return;
        if (end-start == 1) {
                if ((a[end] - a[start]) > 1) {
                        int step = a[end] - a[start];
                        int missingNum = a[start] + 1;
                        result[result_size++] = missingNum;
                }
                return;
        }
        int mid = (start + end)/2;
        find_missing(a, start, mid);
        find_missing(a, mid, end);
}

int main()
{
        int a[] = {1, 2, 3, 4, 5, 6, 8};
        find_missing(a, 0, SIZE(a)-1);
        while(result_size)
                printf("%d\n", result[--result_size]);
        return 0;
}

I think this is very elegant code.

cis.upenn.edu/~matuszek/cit594-2002/Assignments/5-expressions.html

wow this is a nice answer.

#!/usr/bin/python
import sys

def isPalini(string):
        return string == string[::-1]

def count_freq(string):
        count_list = {}
        for i in string:
                if count_list.has_key(str(i)) == False:
                        count_list[str(i)] = 1
                else:
                        value = count_list.get(str(i))
                        value += 1
                        count_list[str(i)] = value
        return count_list

def make_palin(string, unique, recur_flag):
        if isPalini(string) == True:
                return True, str("None"), str("None")
        c_list = count_freq(string)
        print len(string)
        if len(string)%2 == 0:
                char = 0
                dup = []
                for i in string:
                        if c_list[i]%2 != 0:
                                return False, None
                        else:
                                dup.append(i)
                if recur_flag == "set":
                        return True, dup, unique
                else:
                        return True, dup, False
        else:
                char = 0
                for i in string:
                        if c_list[i]%2 != 0:
                                return make_palin(str(string[:string.find(i)]) + (string[string.find(i)+1:]), i, str("set"))
if __name__ == "__main__":
        token = make_palin(sys.argv[1], 0, str("not set"))
        if token[0] == 1:
                if token[2] == str("None"):
                        print "palindrome"
                else:
                        print "palindrome"
                        get_dup = set(token[1])
                        unique = token[2]
                        l = ('').join(get_dup)
                        if unique != 0:
                                print l + str(token[2]) + l[::-1]
                        else:
                                print l + l[::-1]

I think it is all about getting the factors of the number N and then sort it in increasing order. Right now I am not able to think in which cases it won't work.

@Victor: Code in c to support your statement

#include <stdio.h>

struct node_{
        int data;
        struct node_ *next;
};

typedef struct node_ node;
node *head = NULL;

int add(node **head,int no)
{
        node *temp,*head_ref;
        head_ref = *head;
        temp = malloc(sizeof(struct node_));
        temp->data = no;
        temp->next = NULL;
        if(*head == NULL){
                *head = temp;
        } else {
                while(head_ref->next != NULL)
                {
                        head_ref = head_ref->next;
                }
                head_ref->next = temp;
        }
        return 0;
}

void print(node *head)
{
        while(head != NULL)
        {
                printf("node no %d \n",head->data);
                head = head->next;
        }
}
void add_alt_nodes(node *temp, node **list)
{
        if(temp == NULL)
                return;
        add(list, temp->data);
}

void add_alt_data(int data, node **list)
{
        add(list, data);
}

void push(node **list, int data)
{
        node *temp = *list;
        node *t = malloc(sizeof(*t));
        t->data = data;
        t->next = NULL;
        if(temp == NULL) {
                *list = t;
        } else {
                /* find the top most element */
                t->next = *list;
                *list = t;
        }
}

int pop(node **list)
{
        int data;
        if(!*list)
                return -1;
        data = (*list)->data;
        (*list) = (*list)->next;
        return data;
}
int main()
{
        int i = 0;int found;int data=0;
        node *temp;
        node *s_list=NULL;
        node *s_list_1=NULL;
        for(i=0;i<20;i++)
                add(&head, i);
        for(temp=head;temp && temp->next;temp=temp->next->next) {
                add_alt_nodes(temp, &s_list);
        }
        add_alt_nodes(temp, &s_list);
        for(temp=head->next;temp && temp->next;temp=temp->next->next) {
                push(&s_list_1, temp->data);
        }
        if(temp)
                push(&s_list_1, temp->data);
        while(1) {
                data = pop(&s_list_1);
                if(data == -1)
                        break;
                add_alt_data(data, &s_list);
        }
        print(s_list);
        return 0;
}

very good answer for a confused question

@anonymous: would you mind explaining how BFS would work here. Ideally BFS should work as we just need to transition from a to b state but how it will fit in here is a bit of concern.

@Mark Tang: will it give minimum number of steps?

@thelineofcode: first of all what is the logic here? Second: will your algo gives you the minimum number of steps?

Solution for second problem: concatenate the string with itself and search for the given string in the concatenated string.

def find(string, l_s):
        if l_s in string:
                return 1
        else:
                return 0

def main(string, l_s):
        t_string = string + string
        check = find(t_string, l_s)
        print check

if __name__ == "__main__":
        main(sys.argv[1], sys.argv[2])

Solution for first problem:
consider array of size 5 , and i want to shift each element n times then:
(5+n+ i) %5 where i is the actual position of a value in the array. This equation will give the new location to the array.

def rotate(string, shift):
        i = 0
        if shift == len(string):
                return
        for i in range(0, len(string)):
                print string[(len(string)+shift+i)%len(string)]
        rotate(string, shift+1)
def main(string, l_s):
        rotate(string, 0)

if __name__ == "__main__":
        main(sys.argv[1])

@Super Mario: very good explanation.Keep it up.

Can we use binary search in this?
max value for this a^3 + b^3 will be N and mininum value will be 0.
I am sure the below code is not going to work for some cases but right now not able to figure out.
So search will be like this:

#include <math.h>
int power(int no, int power)
{
        int sum = 1;int i;
        for(i=0;i<power;i++) {
                sum = sum*no;
        }
        return sum;
}

void bsearch(int low, int high, int no) {
        printf("low %d high %d\n", low, high);
	/* base cases */
        if(low < 0 || high > no || high < 0 || low > no)
                return;
        if(power(low, 3) + power(high, 3) == no) {
                printf("%d %d\n", low, high);
                return;
        } else if(power(low, 3) + power(high, 3) >= no) {
                bsearch(low, high-1, no);
        } else
                bsearch(low+1, high, no);
}

int main()
{
        bsearch(0, 9/2, 9);
}

Question is definitely not formatted well.Actual question is: Write a function to set 'm' bits of integer 'X' in between two bit positions of integer 'Y'.

/* 
 *(pos_b-pos_a) bits starting from 0 bit of 'y'
 * is being set between pos_a and pos_b of x.
 */
int replace_bits(int pos_a, int pos_b, int x, int y)
{
        /* pos_a is the lowest position i.e. LSB*/
        int total_bits = pos_b - pos_a;
        /*
         * right shifting is basically multiplying
         * and then subtracting by 1
         */
        int mask = (2 << total_bits) - 1;
        printf("mask %d\n", mask);
        x = (x&~((mask)<<pos_a)) | (y&mask);
        return y;
}

here is the code:

#include <stdio.h>
int main()
{
        int n;
        printf("enter the number to check\n");
        scanf("%d", &n);
        if(n < 4)
                printf("not a perfect square\n");
        else {
                int first_sq, first_n, next_sq=0;
                if(n == 4) {
                        printf("perfect square\n");
                        goto end;
                }
                first_sq = 4;
                first_n = 2;
                /* next square will be 2*n+1 more than first_sq*/
                while(1){
                        next_sq = first_sq + 2*first_n + 1;
                        first_sq = next_sq;
                        first_n++;
                        if(next_sq >= n)
                                break;
                }
                if(next_sq == n)
                        printf("perfect square\n");
                else
                        printf("not perfect square\n");
        }
end:
        return 0;
}

@m@}{: your solution seems to be the most elegant one if I am not missing anything.

3 bits - to represent 'quarter' (0,1,2,3)
3 bits - to represent 'x' inside quarter (0,1,2,3)
3 bits - to represent 'y' inside quarter (0,1,2,3)

Just modified subset sum problem.
Subset sum problem is done using tree traversal maintaining visited node.

int a[] = {1, 2, 3, 4, 5};

int k=0;
int visited[100]={0};

void subset_sum(int i, int target)
{
        /*if((i >= sizeof(a)/sizeof(a[0])) || i < 0 || target < 0){
                return;
        }*/
        if((i > sizeof(a)/sizeof(a[0])) || i < 0)
                return;
        if(target <= 0) {
                int j;
                for(j=0;j<sizeof(a)/sizeof(a[0]);j++)
                        if(visited[j] == 1)
                                printf("%4d", a[j]);
                printf("\n");
                return;
        }
        visited[i] = 1;
        subset_sum(i+1, target-a[i]);
        visited[i] = 0;
        subset_sum(i+1, target);
}

int main()
{
        subset_sum(0, 5);
}

Basically recursion is used below but I think Dynamic programming approach is also good but that takes a lot of space.

int a[] = {1, 2, 3, 4, 5, 6, 7};

int k=0;
int visited[100]={0};

void subset_sum(int i, int target)
{
        if((i >= sizeof(a)/sizeof(a[0])) || i < 0 || target < 0){
                return;
        }
        if(target == 0) {
                int j;
                for(j=0;j<sizeof(a)/sizeof(a[0]);j++)
                        if(visited[j] == 1)
                                printf("%4d", j);
                printf("\n");
                return;
        }
        visited[i] = 1;
        subset_sum(i+1, target-a[i]);
        visited[i] = 0;
        subset_sum(i+1, target);
}

int main()
{
        subset_sum(0, 10);
}

@prity: gen-y-s answer is correct please read his reply.

@Dumbo:cs.berkeley.edu/~vazirani/algorithms/all.pdf. this approach coded below but i guess making DAG is taking O(n^2).

#include <stdio.h>

#define SIZE(x) (sizeof(x)/sizeof(x[0]))
int maxi(int a,int b)
{
        return a>b?a:b;
}

int a[] = {10,5,2,5,2,13,17,15,16,19,20,21};

/* LIS using constructing a DAG */
void DAG()
{
        int i, j, max=0,index;
        int d[100] = {0};
        int dag[100][100] = {0};
        int prev[100] = {0};

        for(i=0;i<SIZE(a);i++) {
                d[i]=1;prev[i]=0;
        }
        for(i=0;i<SIZE(a);i++)
                for(j=0;j<SIZE(a);j++)
                        dag[i][j] = 0;
        for(i=0;i<SIZE(a);i++)
                for(j=i+1;j<SIZE(a);j++)
                        if(a[i] <= a[j])
                                dag[i][j] = 1;

        d[0]=1;
        for(i=0;i<SIZE(a);i++)
                for(j=0;j<SIZE(a);j++) {
                        if(dag[i][j] == 1) {
                                if(d[j] <= 1+d[i]) {
                                       d[j] = 1+d[i];
                                       prev[j] = i;
                                }
                        }
                }
        for(i=0;i<SIZE(a);i++)
                if(max < d[i]) {
                        index = i;
                        max = d[i];
                }
        printf("max index %d and greatest total elements %d\n", index, max);
        printf("%d\n", a[index]);
        while(--max){
                index = prev[index];
                printf("%d\n", a[index]);
        }
}

int main()
{
        DAG();
}

isn't two compliement of a negative number is the postive number itself.

int main()
{
int x=-1;
printf("%x\n", x);
printf("%x\n", ~x+1);
}

Just a try:
Sum of arithmetic progression is n/2(2*a+(n-1)*d)

So we know the total sum for the series i.e. in the below case which is 10:
aababcabcd = a + ab + abc + abcd

10 = n/2(2*a+(n-1)*d);
20=n(2*a+(n-1))

Try different values for n and you will see that it for all the number except 4 it is giving a fraction number.Once we get n then it is easy to check if the arithmetic pattern is as we want or not i.e. between two consecutive pattern(p1 and p2) there should be a difference of 1 character and likewise for p2 and p3.

I don't know this will work for all cases or not but suggestions are most welcome.

ok, so here is the code.

int main()
{
    int x = 4454412;
    int y = 56;
    char *x_8 = (char *)&x;
    char *y_8 = (char *)&y;
    printf("%d\n", (*x_8+*y_8)>>1);
    printf("%d %d\n", *x_8, *y_8);
}

What is wrong with binary addition and doing right shift by one?