Sum Of SubSet problem- NP Complete Problem

the subset sum problem is an important problem in complexity theory and cryptography. The problem is this: given a set of integers, is there a non-empty subset whose sum is exactly zero? For example, given the set { −7, −3, −2, 5, 8}, the answer is yes because the subset { −3, −2, 5} sums to zero. The problem is NP-complete.


A Simple Example

int C(int n,int k)
{
if (k==0 || k==n)
return 1;
return C(n-1,k-1) + C(n-1,k);
}


www.cs.binghamton.edu/~dima/cs333/backtracking.ppt
www.cs.umsl.edu/~sanjiv/classes/cs5130/lectures/bt.pdf
www.mgt.ncu.edu.tw/~ylchen/algorithm/chapter5.doc
max.cs.kzoo.edu/cs215/lectures/w5-graph-coloring.pdf
www.slidefinder.net/b/backtracking_sum_subsets_knapsack/7064040
www.cs.utep.edu/ofuentes/cs2402/backtrackingStack.doc

Bin Packing Problem . One of The My Fav. Problem NP Hard

n objects to be placed in bins of capacity L each.,Determine the minimum number of bins needed to accommodate all n objects.

Given: n objects to be placed in bins of capacity L each.
Object i requires li units of bin capacity.
Objective: determine the minimum number of bins needed to
accommodate all n objects.

eg. Let L = 10
l1=5 t4==7
l2=6 t5=5
l3=3 t6=4


Data Structure Used:Array

Theorem
Bin packing problem is NP complete when formulated as a decision problem.
As an optimization problem bin packing is NP-hard

Approximation Algorithm for Bin Packing:

1. First Fit (FF)
- Label bins as 1, 2, 3, . . .
- Objects are considered for packing in the order 1, 2, 3, . . .
- Pack object i in bin j where j is the least index such that
bin j can contain object i.

2. Best Fit (BF)
Same as FF, except that when object i is to be packed, find out
that bin which after accommodating object i will have the least
amount of space left.

3. First Fit Decreasing (FFD)
reorder objects so that
li>li+1 1<=i<=n then use FF. 4. Best Fit Decreasing (BFD) reorder objects as above and then use BF. Th. Packing generated by either FF or BF uses no more then 17/10 OPT + 2 Bins That by either FFD or BFD uses no more than 11/9 OPT+ 4 Bins 1/9=9/9+2/9 This is a very straightforward greedy approximation algorithm. The algorithm processes the items in arbitrary order. For each item, it attempts to place the item in the first bin that can accommodate the item. If no bin is found, it opens a new bin and puts the item within the new bin. It is rather simple to show this algorithm achieves an approximation factor of 2. This is due to the observation that at any given time, it is impossible for 2 bins to be at most half full. The reason is that if at some point a bin was at most half full, meaning it has at least a space of V / 2, the algorithm will not open a new bin for any item whose size is at most V / 2. Only after the bin fills with more than V / 2 or if an item with a size larger than V / 2 arrives, the algorithm may open a new bin. Thus if we have B bins, at least B − 1 bins are more than half full. Therefore \sum_{i=1}^n a_i>\tfrac{B-1}{2}V. Because \tfrac{\sum_{i=1}^n a_i}{V} is a lower bound of the optimum value OPT, we get that B − 1 < 2OPT and therefore B ≤ 2OPT.[1] See analysis below for better approximation results. float[] used = new float[n + 1]; //used[j] is the amount of space in bin j already used up. int i, j; Initialize all used entries to 0.0 Sort S into descending(nonincreasing)order, giving the sequence S1 >= S2 >= ... >= Sn.
for(i = 1; i <= n; i++)
//Look for a bin in which s[i] fits.
for(j = 1; j <= n; j++)
if (used[j]+si<+1.0)
bin[i] = j;
used[j] += si;
break; //exit for(j)
//continue for(i)


Time Complexity O(nlogn)
Space Complexity O(1)
Auxiliary Space O(n)

Run Here

Source:
A guide to the Theory of NP-Completeness by Michael R. Garey and David S. Johnson
http://en.wikipedia.org/wiki/Bin_packing_problem

Wap to Find Next Higher Number of Given NUmber , Containing Same Number of SetBits

# Problem

* Given a number m find the next higher number r , that has same number of 1-bits.

* Ex : 3 (0000011) => 5(0000101)

* 6(0000110) => 9(0001001)

* 11(0001011) => 13(0001101)

* 23(0010111) => 27(0011011)

* 24(0011000) => 33(0100001)

* 44(0101100) => 49(0110001)

* 46(0101110) => 51(00110011)


1st Thinking(Algorithm)
1.count number of set bits in given number .
2. start from that number in loop & count number of set bits in all number > n untill we found the same set bits in any number, once found stop.

but problem with this algorithm is that it will take too much time for bignumber
O(N) where N is number of iteration untill we find number > N with same number of set bits.


2nd Solution (Most Optimized)

# Observations I

* Look at the input and the outputs again and see if you can make some algorithm out of it

* 3 (0000011) => 5(0000101)

* 6(0000110) => 9(0001001)

* 11(0001011) => 13(0001101)

* 23(0010111) => 27(0011011)

* 24(0011000) => 33(0100001)

* 44(0101100) => 49(0110001)

* 46(0101110) => 51(00110011)


# Observations II

* Hint : Now concentrate on the highlighted parts of input

* 3 (0000 011 ) => 5(0000 101 )

* 6(000 0110 ) => 9(000 1001 )

* 11(0001 011 ) => 13(0001 101 )

* 23(001 0111 ) => 27(001 1011 )

* 24(0 011000 ) => 33(0 100001 )

* 44(01 01100 ) => 49(01 10001 )

* 46(01 01110 ) => 51(01 10011 )

# Observations III

* As you can see,

o the non-highlighted part is same in i/p and o/p as well

o And the highlighted part is consecutive 1’s from the least-significant side (right hand side)

* 3 (0000 011 ) => 5(0000 101 )

* 6(000 0110 ) => 9(000 1001 )

* 11(0001 011 ) => 13(0001 101 )

* 23(001 0111 ) => 27(001 1011 )

* 24(0 011000 ) => 33(0 100001 )

* 44(01 01100 ) => 49(01 10001 )

* 46(01 01110 ) => 51(01 10011 )

# Observations IV

* As you can see, the non-highlighted part is same in i/p and o/p as well

* 3 (0000 011 ) => 5(0000 101 )

* 6(000 0110 ) => 9(000 1001 )

* 11(0001 011 ) => 13(0001 101 )

* 23(001 0111 ) => 27(001 1011 )

* 24(0 011000 ) => 33(0 100001 )

* 44(01 01100 ) => 49(01 10001 )

* 46(01 01110 ) => 51(01 10011 )

# Observations V

* Now lets just look at what changed

* 011 => 101

* 0110 => 1001

* 011 => 101

* 0111 => 1011

* 011000 => 100001

* 01100 => 10001

* 01110 => 10011

* Do you see a pattern?

# Observations VI

* Yes, as you have rightly observed, left hand side is :

o A 0 followed by

o One or more 1’s (say x) followed by

o Zero or more 0’s (say y)

* Is changed to

o A 1 followed by

o (y+1) zeroes followed by

o (x-1) 1’s

* 0 11 => 1 0 1

* 0 11 000 => 1 0 000 1

Algorithm

# Now let’s frame the algorithm

* Given a bit-pattern, start from right, find successive zeroes (xxxx01111 0000 )

* Followed by zeroes find successive 1’s (xxxx0 1111 0000 )

* Stop on hitting a zero (xxxx 0 1111 0000 )

* Interchange that zero with a 1 from successive 1’s (xxxx 1 0 111 0000 )

* Now move the remaining 1’s to extreme right, filling the gap with zeroes (xxxx 1 0 0000 111 )

# Doing it programmatically in C

* unsigned snoob(unsigned x) {

o unsigned smallest, ripple, ones;

o // x = xxx0 1111 0000

o smallest = x & -x; // 0000 0001 0000

o ripple = x + smallest; // xxx1 0000 0000

o ones = x ^ ripple; // 0001 1111 0000

o ones = (ones >> 2)/smallest; // 0000 0000 0111

o return ripple | ones; // xxx1 0000 0111

* }


Working Code:

#include

using namespace std;

typedef unsigned int uint_t;

// this function returns next higher number with same number of set bits as x.
uint_t snoob(uint_t x)
{

uint_t rightOne;
uint_t nextHigherOneBit;
uint_t rightOnesPattern;

uint_t next = 0;

if(x)
{

// right most set bit
rightOne = x & -(signed)x;

// reset the pattern and set next higher bit
// left part of x will be here
nextHigherOneBit = x + rightOne;

// nextHigherOneBit is now part [D] of the above explanation.

// isolate the pattern
rightOnesPattern = x ^ nextHigherOneBit;

// right adjust pattern
rightOnesPattern = (rightOnesPattern)/rightOne;

// correction factor
rightOnesPattern >>= 2;

// rightOnesPattern is now part [A] of the above explanation.

// integrate new pattern (Add [D] and [A])
next = nextHigherOneBit | rightOnesPattern;
}

return next;
}

int main()
{
int x = 156;
cout<<"Next higher number with same number of set bits is "<
getchar();
return 0;
}

Time Complexity O(1)
Space Complexity O(1)
Run Here https://ideone.com/8R2N2
Source http://www.gowrikumar.com

Implement a data structure SetOfStacks that mimics below problem.

Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore,
in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks
should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks.push() and SetOfStacks.pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack).

Describe how you could use a single array to implement three stacks..Optimize SOlution Needed

Approach 1:

Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: “[“ means inclusive, while “(“ means exclusive of the end point).
»»for stack 1, we will use [0, n/3)
»»for stack 2, we will use [n/3, 2n/3)
»»for stack 3, we will use [2n/3, n)
This solution is based on the assumption that we do not have any extra information about the usage of space by individual stacks and that we can’t either modify or use any


Approach 2:
In this approach, any stack can grow as long as there is any free space in the array.
We sequentially allocate space to the stacks and we link new blocks to the previous block. This means any new element in a stack keeps a pointer to the previous top element of that particular stack.
In this implementation, we face a problem of unused space. For example, if a stack deletes some of its elements, the deleted elements may not necessarily appear at the end of the array.
So, in that case, we would not be able to use those newly freed spaces.
To overcome this deficiency, we can maintain a free list and the whole array space would be given initially to the free list. For every insertion, we would delete an entry from the free list. In case of deletion, we would simply add the index of the free cell to the free list.
In this implementation we would be able to have flexibility in terms of variable space utilization
but we would need to increase the space complexity.

Wap to Replace all the instances of ’%’ with this string s,offered that the length of the array

Given an array of dimension n with very first l positions crammed with characters and a string s ,replace all the instances of ’%’ with this string s,offered that the length of the array is enough to deal with these substitutions.

input output

eg: abcdef%ghi%—— and “ppp” abcdefpppghippp



Although program is Simple but i am posting here as i found on one forum that it is asked by MS:)

Data Structure:Array

Algorithm:
1.count number of % character
2.increase size of array by lenth + 2* number op & chars.
3. scan through new array & replace all % occurance with "ppp"


class test
{
public static void ReplaceFun(char[] str, int length) {
int percentCount= 0, newLength, i = 0;
for (i = 0; i < length; i++)
{
         if (str[i] == '%')
        {
            percentCount++;
        }
}

newLength = length + percentCount* 2; str[newLength] = '\0';

for (i = length - 1; i >= 0; i--)
{
if (str[i] == '%')
{
str[newLength - 1] = 'p';
str[newLength - 2] = 'p';
str[newLength - 3] = 'p';
newLength = newLength - 3;
}
else
{
str[newLength - 1] = str[i];
newLength = newLength - 1;
}

}
System.out.println(str);
}
public static void main(String a[])
{
ReplaceFun(new char[]{'s','h','%','a','%','%','s','h','a','n','%','%','%','k'},15);

}
}

WAP to Create New Arrayfrom Given Array Suuch That array2[i] will hold the value of the left-most integer from the range array1[i+1] to array1[n-1] such that it is greater than array1[i]. If no such element exists, assign -1.

You are given an array of integers, say array1 of size n. You have to create another array (say array2) and fill its contents by following this rule: array2[i] will hold the value of the left-most integer from the range array1[i+1] to array1[n-1] such that it is greater than array1[i]. If no such element exists, assign -1.

Example ar[]={4,5,2,25}
4 --> 5
5 --> 25
2 --> 25
25 --> -1
arr[]=1 21 8 11 13 9 6
1- 21
21- -1
8 11
11 13
13 -1
9 -1
6 -1

Data Structure:

Algorithm:


Time Complexity O(N^2)
Space Complexity O(1)
Run here

Optimize Approach



Time Complexity O(N)
Space Complexity O(N) Stack Space
Run here

Detect 1% Duplicate Entry in a File of 13 Million Entries Efficiently.

We have a text file with 13 Million entries, all numbers in the range from 1.000.000 to 100.000.000. Each line has only one number. The file is unordered and we have about 1% duplicate entries. Remove the duplicates.

As We have a Huge Data obvious things that should come into mind is using bit array or bit set where ith bit represent the position of number in array of size 13* 2^20

before start solving question i suggest you people to check basics of bit operations here

#include
#include
using namespace std;
int main()
{
int i=0,j=0,k=0;
int n=18;
n|=1<<3;//Set the ith bit here i=3
printf( " %d ", n);
n&=~(1<<3);//clear ith bit
printf( " %d ", n);
n^=1<<1;//toggle ith bit
printf( " %d ", n);
i=n&(1<<4)?1:0;//check ith (i=4)bit set or not
printf( " %d ", i);
return 0;
}


Data Structure:Bit Array

Algorithm:
1.set ith bit n bit arry when reading number 1 by one from file .
2.if ith bit corrosponding to number is already set then number is duplicate .
& we are done.

as we are using bit array here so When using an array of bytes to represent set of bits, i.e., a bit array or bitset, the index of the byte in the array associated with a bit n can be calculated using division:

ith index / CHAR_BIT (number represented by 32 bit or 64 bit etc)

where n is the index of the given bit and CHAR_BIT gives the number of bits in a C char.

"this will give position of byte element in array elements"

The index of the bit within the byte indexed by the above can be calculated via a modulo operation:

n % CHAR_BIT

"so this will give us position of bit inside byte."

so then we can write the following method to find 1% duplicates

bool setBit(int a[], int i)
{
int index = i / 8; //position number in array
int offset = i % 8;//position of bit in byte
if (a[index] & (1<< offset))//check bit is set or not
return false;//when ith bit is already set
a[index] |= 1< return true;
}

Time Complexity O(N) size of file
Feel Free to Comment or Optmize the Solution

Given a 1D Array (linear) , you have to convert it in to 2D array & then find sum of each column.you have given number of rows K & number of elemnets N in array.

You are given a 1D array of integers, such as: int[] array = [3,4,7,2,2,6,0,9];
Suppose you need to treat this array as a 2D table with a given number of rows.
You want to sum the columns of the table.One value of numRows is 4..in that case the resultant array would look like

what if numRows==4?
3 4
7 2
2 6
0 9
—-
12 21

Data Structure : 2D Array


Algorithm:
1.As we have given Number of elements N in array & number of rows k to make 2D
Array we can easily find out number of column C=N/k
2.Then using two for loop down the 2D array 1st loop run for coumns & inner loop
work for rows.(A Tricky Mind Needed here although so Simple

).as in inner loop
we will increment by value of column we get.

Working Code:

#include
#include
using namespace std;
int main()
{
int i=0,j=0,k=0,sum=0;
int r=3;//row
int a[]={3,4,7,2,2,6,0,9,5,8,11};
int n=sizeof(a)/sizeof(int);
j=n/r;//column

while(k {
for(i=k;i {
sum=sum+a[i];
}
cout< sum=0;
k++;
}

return 0;
}

Time Complexity O(column*row)=O(N) see above relation C=N/r
Space Complexity O(1)
Run Here https://ideone.com/RWjEf

Given ‘n’ no of sets and each set is of a variable size. Find out the cross product of these ‘n’ of sets.

For eg. {1,2} , {3,4} , {5,6,7} these are the three sets.The cross product of these sets would be as below.
{1,3,5},{1,3,6},{1,3,7},{1,4,5},{1,4,6},{1,4,7},{2,3,5},{2,3,6},{2,3,7},{2,4,5},
{2,4,6},{2,4,7}.


Data Structure: Binary Tree

Algorithm:


Working Code:






Time Complexity
Space Complexity
Run Here