Given an array find all the groups that make the sum equal to an integer given n.

Example

100,10,30,20,90,70,55,80,15,60,0
Sum=100

Possible ways are 100+0, 20+80,10+20+70,60+30+10,55+15+10+20...and so on..


Source http://max.cs.kzoo.edu/cs215/lectures/w5-graph-coloring.pdf
http://max.cs.kzoo.edu/cs215/lectures/w5-graph-coloring.pdf

WAP to Finding The Minimum Window In An Array Which Contains All Given Elements (Need Not to be Contiguous)

Question: Given a set CHARS of characters and a string INPUT, find the minimum window in INPUT which will contain all the characters in CHARS in complexity O(n).

Ex:
INPUT = "ABBACBAA"
CHARS = "AAB"

Minimum window is "BAA".

For example
Test length
[A B B A] C B A A 4
A B B [A C B A] A 4
[A B B A] C [B A A] 3 answer


lgorithm
Input is the given array and chars is the array of character need to be found.

1) Make an integer array shouldfind[] of len 256 . i-th element of this array will have a the count how many times we need to find element of ASCII value i.
2) Make another array hasfound of 256 elements, which will have the count of required element found till now.
3) Count <= 0
4) While input[i]
. a. If input[i] element is not to be found -> continue
. b. If input[i] element is required => increase count by 1.
. c. If count is length of chars[] array, slide the window as much right as possible.
. d. If current window length is less than min length found till now. Update min length.
5) end



#include
#include
#include
#include
using namespace std;

#define MAX 256

void minlengthwindow(char input[], char chars[], int start, int finish)
{
int shouldfind[MAX] = {0,};
int hasfound[MAX] = {0,};
int cnt = 0;
int minwindow = INT_MAX;

int charlen = strlen(chars);
for (int i=0; i< charlen; i++)
shouldfind[chars[i]] += 1;

int iplen = strlen(input);
start = 0;
finish = iplen;
int j = 0;

for (int i=0; i< iplen; i++)
{
if (!shouldfind[input[i]])
continue;
hasfound[input[i]] += 1;

if (shouldfind[input[i]] >= hasfound[input[i]])
cnt++;

if (cnt == charlen)
{
while (shouldfind[input[j]] == 0 || hasfound[input[j]] > shouldfind[input[j]])
{
if (hasfound[input[j]] > shouldfind[input[j]])
hasfound[input[j]]--;
j++;
}
if (minwindow > (i - j +1))
{
minwindow = i - j +1;
finish = i;
start = j;
}
}
}
cout << start << " " << finish << endl;
}


int main()
{
char a[]="ABBACBAA";
int size=sizeof(a)/sizeof(int);
char chars[]="AAB";
minlengthwindow(a,chars,0,size);


}


TC O(N) If you walk through the code, i and j can traverse at most N steps (where N is input size size) in the worst case, adding to a total of 2N times. Therefore, time complexity is O(N).

SC O(1)
Run Here http://ideone.com/kJwMS

Suppose Your Are Writing a Message to Your Friends , Assume Simple Mobile of Old Time Where You Don't Had Seperate buttons for chars , so you have to type some digit and that show you number of possible chars , now suppose you press some random keys on mobile & send some fake message to your friendsCan You Device an algorithm that o/p: all possible letter strings based on the numbers you pressed.

e.g. if numbers pressed 9876124305 then output should be same as in this file https://ideone.com/VtoBo

Can You Device an algorithm that o/p: all possible letter strings based on the numbers you pressed. What Will Be Time and Space Complexity .

Follow Up:

Can You Output only those strings that are in a given dictionary. (and length of the dictionary is small.) What Will Be Complexity of Problem , Explain Clearly .

Algorithm:

Data Structure used : Array

Problem Solving Paradigm Used: Recursion

class Number2Text
{       // Mapping From 0-9 Number in to Corresponding Strings  
        // when you press 1 only 1 is showed , when you press 0 , 0 is showed 
        //those assume simple mobile else 1 used to show many chars then we can store 
       //chars in string and can pass thi string at 1st string in below array.
       //e.g. lest 1 may support 1 -> , . ! ~ @ # $ % ^ & * ( ) { } [ ] / ? : ; " ' etc.
       //so we can write String one=" ,.!~@#$%^&*(){}[]/?:;"' "; can pass one string 
       //to below 
         
         private static String[] mapping = {"0","1","ABC", "DEF", "GHI", "JKL", "MNO",
                        "PQRS", "TUV", "WXYZ"};
 
 
public static void combinations(int[] number, char[] buf, int numIndex) 
{
 
          for (int i = 0; i < mapping[number[numIndex]].length(); i++) 
         {
                        buf[numIndex] = mapping[number[numIndex]].charAt(i);
                        if (numIndex < number.length - 1) 
                        {
                                combinations(number, buf, numIndex + 1);
                        } 
                        else
                                System.out.println(buf);
         }
}
 
 
 
public static void main(String[] args)  
{
                int num[] ={9,8,7,6,1,2,4,3,0,5};// { 5, 8, 5, 5, 0, 3, 3, 4, 4, 7 };
                Number2Text.combinations(num, new char[num.length], 0); 
} 
 
}

Time Complexity O(4*T(n-1)) //Worst Case

Space Complexity O(N)

Run Here Small Input https://ideone.com/9T6yb

              Average Size Input https://ideone.com/T07Qy

              Large Input https://ideone.com/l4sbz

Aplplication : Frequently Used in Mobile Phone  , When You Type Message , it Show you Different Combinations. Its Great Code :) .

Feel Free to Comment on anything you like such that how we can improve complexity , other way to solve same problem or if anything wrong here , Thanks for visiting.

WAP a function to determine the number of bits required to convert integer A to integer B.

Write a function to determine the number of bits required to convert integer A to integer B.
Input: 31, 14
Output: 2

class digit_prob
{

public static int bitSwapRequired(int a, int b)
{
int count = 0;
for (int c = a ^ b; c != 0; c = c >> 1) {
count += c & 1;
}
return count;
}

public static void main(String a[])
{
System.out.println(bitSwapRequired(10,9));

}

}


TC O(n)
Sc O(1)
Run Here https://ideone.com/VaBTS

WAP to Print Binary Representation of Decimal Number Thats Passed as String to Function

Given a (decimal - e.g. 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”

Note: Review Needed

First, let’s start off by asking ourselves what a non-integer number in binary looks like. By analogy to a decimal number, the number n = 0.101 = 1 * (1/2^1) + 0 * (1/2^2) + 1 * (1/2^3).
Printing the int part of n is straight-forward (see below). To print the decimal part, we can multiply by 2 and check if the 2*n is greater than or equal to one. This is essentially “shifting” the fractional sum. That is:
r = 2*n = 2*0.101 = 1*(1 / 2^0) + 0*(1 / 2^1) + 1*(1 / 2^2) = 1.01
If r >= 1, then we know that n had a 1 right after the decimal point. By doing this continuously,we can check every digit.

class digit_prob
{

public static String printBinary(String n)
{

int intPart = Integer.parseInt(n.substring(0, n.indexOf('.')));
double decPart = Double.parseDouble(
n.substring(n.indexOf('.'), n.length()));
String int_string ="";
while (intPart > 0) {
int r = intPart % 2;
intPart >>= 1;
int_string = r + int_string;
}
StringBuffer dec_string = new StringBuffer();
while (decPart > 0) {
if (dec_string.length() > 32) return "ERROR";
if (decPart == 1) {
dec_string.append((int)decPart);
break;
}
double r = decPart * 2;
if (r >= 1) {
dec_string.append(1);
decPart = r - 1;
} else {
dec_string.append(0);
decPart = r;
}
}
return int_string + "." + dec_string.toString();
}
public static void main(String a[])
{
System.out.println(printBinary("3.5"));

}

}

TC O(K) k= length of number e.g digits in number
SC O(1)
Run Here https://ideone.com/7yjsH

WAP to Find a String in Sorted Array of String " Containing Large number of empty Strings in it Efficiently....Think of O(logn) ??

Given a sorted array of strings which is interspersed with empty strings, write a method
to find the location of a given string.
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

class stringSearch
{
 

public static int search(String[] strings, String str,

 int first, int last) 
 {
        while (first <= last) 
        {
                // Ensure there is something at the end
          while (first <= last && strings[last] =="") 
                {
                        --last;
                }
                
                if (last < first) 
                {
                        return -1;  

// this block was empty, so fail
                }
                 int mid = (last + first) >> 1;
                
                 while (strings[mid] =="") 
                {
                         ++mid;  

// will always find one
                }
                
                 int r = strings[mid].compareTo(str);
                 if (r == 0) return mid;
                 
                 if (r < 0) 
                 {
                         first = mid + 1;
                 }
                 else 
                {
                         last = mid - 1;
                 }
         }
 return -1;
 }
 
 public static int search(String[] strings, String str) 
 {
         if (strings == null || str == null) return -1;
         if (str =="") 
         {
              for (int i = 0; i < strings.length; i++) 
                {
                      if (strings[i] == "") return i;
                }
                 return -1;
         }
         return search(strings, str, 0, strings.length - 1);
 }
 
   public static void main(String a[])
  {
  String str_arr[]=new String[]{"at", "", "", "",  

"ball", "", "", "car", "", "", "dad", "", ""};
     String str="ball";
     System.out.println(search(str_arr,str));
  
  }
}

TC O(n) when all array having empty string the 1st inner loop will run n time
SC O(1)
Run Here https://ideone.com/f9FcL

WAP to Calculate nth Prime Number Efficiently

java program

class nth
{

public static void main(String a[])
{
nthfindPrime(5);
}
static void nthfindPrime(int n)
{
int i=0,count=2;
if(n==1)
{
System.out.println("1st prime =2");
return;
}
if(n==2)
{
System.out.println("2nd prime =3");
return;
}

while(true)
{
for(int j=2;j<=i/2;j++)
{
if(i%j==0)
break;
else if(j==i/2)
{
count++;
}
}
if(count==n)
{
System.out.println(n+"th prime ="+i);
break;
}
i++;
}
}
}

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

Run Here https://ideone.com/OHmO9


A More Efficient Version

#include
#include
using namespace std;

int main()
{
int i=0,count=2;int n=60;
if(n==1)
{
cout << "1st Prime Number = 2\n";
return 1;
}
if(n==2)
{
cout << "2nd Prime Number = 3\n";
return 2;
}
i=5;
float root2 = sqrt(2);
int limit;
while(true)
{
limit = (int)(i/root2);
for(int j=2;j<=limit;j++)
{
if(i%j==0)
break;
else if(j==i/2)
{
count++;
}
}
if(count==n)
{
cout << n << "th Prime No. : " << i << endl;
break;
}
i++;
}
}

http://en.wikipedia.org/wiki/Prime_number_theorem#Approximations_for_the_nth_prime_number

But number of Instruction Reduced
Time Complexity O(n)
Space Complexity O(1)
Run Here https://ideone.com/ncfzh

WAP to Convert it to a sorted array with minimum cost. You are given an array of positive integers.

You are given an array of positive integers. Convert it to a sorted
array with minimum cost. Only valid operation are
1) Decrement -> cost = 1
2) Delete an element completely from the array -> cost = value of
element
For example:
4,3,5,6, -> cost 1
10,3,11,12 -> cost 3


we can make the DP more efficient You don't need to scan the whole previous column when calculating costs of decrementing. Rather there are only two
possibilities.

Algorithm Given By Gene

DP is better for this problem.
Remember C(n, m) is the cost of making a[1 .. n] into a non-decreasing
sequence with the last element being no more than m. And we always
draw m from the set V of values in a.
So here is the new DP:
C(1, m) = max(a[1] - m, 0) // first row only decrement is possible
C(n, m) = min (
a[n] + C(n - 1, m), // delete
(a[n] <= m) ? C(n - 1, a[n]) : C(n - 1, m) + a[n] - m // decrement
)
In case you don't follow, the "//delete" line is saying that we
already know the cost of making everything up to element n-1 non-
decreasing and no more than m. This, by recursive assumption, is just
C(n-1,m). The additional cost of deleting a[n] is a[n].
The "//decrement" line is similar, but there are 2 cases. If a[n] is
more than m, we must decrement it. The cost here consists of making
everything up to n-1 non-decreasing and no more than m, i.e. C(n-1,m).
Plus we have the cost of chopping a[n] down to m, which is a[n]-m.
In the other case, a[n] is m or less. So there's no need to
decrement, but we must get the elements a[1..n-1] to be no more than
a[n]. Again by recursive assumption this cost is C(n-1,a[n]).
Here is an example. Suppose we have a = [5, 1, 1, 1, 3, 1]. The
least cost here is obtained by decrementing the 5 to 1 (cost 4) and
deleting the final 1 (cost 1) for a total cost of 5.
So let's try the algorithm. (You must view this with a fixed font.)
Table of C(n, m) values:
m = 1 3 5
n = 1 : 4 2 0
n = 2 : 4 3* 1*
n = 3 : 4 4 2*
n = 4 : 4 4 3*
n = 5 : 6m 4 4
n = 6 : 6 5* 5*
Here * means C resulted from decrementing and "m" means that a
decrement was based on the value of m rather than a[n].
We take the answer from C(6,5) = 5.
Implementing this is a little tricky because m values are drawn from
V. You could use a hash table for the m-axis. But it's more
efficient to store V in an array and convert all the values of m in
the DP into indices of V. Because all the indices lie in [ 1 .. |
V| ], we can use simple arrays rather than hash tables to represent
the rows of the table C.
We only need 2 rows at a time, so O(|V|) storage does the job.
For C, we also need to convert all the indices to origin 0.
So here's the final O(n^2) code. I think this is a correct
implementation. If anyone has an example that breaks it, I'd like to
see.
#include
#define NMAX 10000
int cost(int *a, int N)
{
int i, j, max, Nv;
int V[NMAX], A[NMAX], B[NMAX];
int *Cm = A, *Cn = B; // (n-1)'th and n'th rows of C
// Compute set V with no duplicates.
// Remember where max element is.
Nv = max = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < Nv; j++)
if (a[i] == V[j])
break;
if (j == Nv) {
V[Nv++] = a[i];
if (V[j] > V[max])
max = j;
}
a[i] = j; // Convert a to indices.
}
// Fill in first row of C.
for (i = 0; i < Nv; i++)
Cm[i] = (V[a[0]] >= V[i]) ? V[a[0]] - V[i] : 0;
// Fill in the rest of the rows of C.
for (i = 1; i < N; i++) {
for (j = 0; j < Nv; j++) {
int del = Cm[j] + V[a[i]];
int dec = (V[a[i]] <= V[j]) ? Cm[a[i]] : Cm[j] + V[a[i]] - V[j];
Cn[j] = (del < dec) ? del : dec;
}
// Swap row buffers so current becomes previous.
int *tmp = Cn; Cn = Cm; Cm = tmp;
}
return Cm[max];
}

int main(void)
{
static int a[] = { 5, 1, 1, 1, 3, 1 };
printf("Min cost = %d\n", cost(a, sizeof a / sizeof a[0]));
return 0;
}
TC O(N^2)
Sc O(n)
Run Here https://ideone.com/VdsC0

WAP to Find a Word in Dictionary at ith Position Efficiently

If you have a dictionary (sorted list of words) of unknown size and given a function which returns the word in the dictionary at a specified 'i'th location. Suggest an algorithm for finding a word.

We can think of finding the size of dictionary by exponentially getting (2^i)th element (incrementing i each time till the word is lexicographically higher than the given word) and then simply applying binary search from 0 to 2^i.

WAP a Program By Choosing Best Data structure which is supposed to log number of user requests per second.

Make a data structure which is supposed to log number of user requests per second. At any point of time your boss can ask you the number of hits for the last 60 seconds. It can be at any time for example he will say at 71st second that tell me how many hits for past 30 seconds or something, but this window can go maximum upto 60 seconds to in the previous example 11 to 71.