WAP to Generate The Series of Ugly or Lucky Number

Question:Generate The Series of Lucky/Ugly Number or Find the First K Ugly/Lucky Number



eg. 1 2 4 8 10 16 20 25 32 64 100 125 128

Algorithm

Answer: Consider an array of first 10 ugly numbers: {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, , , , }

Next ugly number can be calculated by just multiplying one of all these numbers with 2 or 3 or 5.

The least number whose double is not present in the list is 8 (any number before this has its double present in the list). So one of the candidates for next ugly number is 8*2=16

The least number whose multiple by 3 is not present in the list is 5 (any number before this has its multiplied by 3 present in the list). So other candidate for next ugly number is 5*3 = 15.

The least number whose multiple by 5 is not present in the list is 3 (any number before this has its multiplied by 5 present in the list). So other candidate for next ugly number is 3*5 = 15.

Least of these three numbers (15) is our next ugly number.

Now how to choose next ugly number is pretty simple. Since our ugly number is 15 it means now 3*5 and 5*3 are present in the list. So next numbers whose multiple by 3 and 5 respectively are not present in the list are 6 and 4 respectively. The least number whose double is not present in the list remains unchanged at 8. So next candidates are 8*2, 6*3 and 4*5. We will continue in this manner for further list.
Lucky numbers are numbers whose prime factors are just 2, 3, 5. Find the first k lucky numbers.


Algorithm: Keep 3 pointers with you and keep track whose multiple by 2,3 and 5 are present and whose are not. Choose the least number of next candidates and increase the pointer by 1 for the chosen one. If 2 candidates are same, and we chose that number, increment both the pointers as in example above.


#include
#include
using namespace std;
#define k 20 //modify it

int Lucky[k], ptr2, ptr3, ptr5;

int minimum(int x,int y,int z)
{
if (x return (y}

int nextLucky(int num)
{
int num2,num3,num5;
if(num==0)
{
Lucky[num]=1;
ptr2=ptr3=ptr5=0;
return Lucky[num];
}

num2=Lucky[ptr2]*2;
num3=Lucky[ptr3]*3;
num5=Lucky[ptr5]*5;

Lucky[num]=minimum(num2,num3,num5);

if(Lucky[num]==num2) ptr2++;
if(Lucky[num]==num3) ptr3++;
if(Lucky[num]==num5) ptr5++;

return Lucky[num];
}

int main()
{
int i;

for(i=0; i printf("Lucky number no. %d is %d\n", i+1,nextLucky(i));
}

Dynamic Programming
TC O(n)
SC O(n)
Run Here https://ideone.com/B8rCN


Variation
Google Interview Question in different Way:
Given expression E=(2^i * 5^j), increment i and j to ensure the output is sorted.
so above logic will remain same except we need multiples of 2's & 5's thats it

TC O(n)
SC O(n)
Run Here https://ideone.com/M2Bmz

Given integer n decide if it is possible to represent it.SPOJ Prob. 91 as a sum of two squares of integers.

In number theory, Pierre de Fermat's theorem on sums of two squares states that an odd prime p is expressible as
x^2+y^2=c
with x and y integers, if and only if

For example, the primes 5, 13, 17, 29, 37 and 41 are all congruent to 1 modulo 4, and they can be expressed as sums of two squares in the following ways:

On the other hand, the primes 3, 7, 11, 19, 23 and 31 are all congruent to 3 modulo 4, and none of them can be expressed as the sum of two squares.

More Info http://en.wikipedia.org/wiki/Fermat's_theorem_on_sums_of_two_squares


I used Above Fact to Solve the Question(to Solve SPOJ problem You have to Modify the program )

#include
#include

int isSquare(int c)
{
int a=0;int b=sqrt(c);
if(c%4==1)//remove this to solve spoj probelm
{
while(a<=sqrt(c))
{ int pows=pow(a,2)+pow(b,2);
if(a!=b && pows==c ) //a!=b means 1^1+1^1=2 not allowed
{ printf(" yes Possible \t %d %d ", a,b);
return 1;
}
else if(pows a++;
else b--;

printf( " %d %d %d \n", a,b,pows);
}

}
else
{ printf( "not Possible");
return 0;
}
return 0;
}

int main()
{
printf(" %d ", isSquare(29));
}


TC O(sqrt(n))
SC O(1)
Run Here https://ideone.com/nLGDs

WAP to design an efficient algorithm to find whether String s3 is formed from the interleaving of String s1 and String s2

Design an algorithm to find whether a given string is formed by the
interleaving of two given strings or not.
s1= aabccabc
s2= dbbabc
s3= aabdbbccababcc

If I am Correct a Similer Iterative Approahc can be written as

bool test(A,B,C)
{
i=j=k=0;
while(k < C.size()) { if(i < A.size() && C[k]==A[i]) {i++,k++; } else if(j < B.size() && C[k]==B[j]) { j++,k++; } else return false } return (i == A.size() && j == B.size()); } Similer Recursive Apparoahc in Which Interviewer Show More Interest bool interleaved(char *s1, char *s2, char *s3) { // Base case, all strings are empty return (!s1[0] && !s2[0] && !s3[0]) || // First character of s1 is next in s3 (s1[0] && (s1[0] == s3[0]) && interleaved(s1+1,s2,s3+1)) || // First character of s2 is next in s3 (s2[0] && (s2[0] == s3[0]) && interleaved(s1,s2+1,s3+1)); } No Doubt This Problem Requires DP (Top-Down memozation will be Best )Approach & I had Solved It Using the Same. Below is one of The Possible Approach. I found A Good Discussion Here AlgoGeek


TC O(N) length of Bigger String thats S3 Need to Check
SC O(1)
Run Here http://ideone.com/n6RLc

WAP to Check That Binary Representation of Given Number is Palindrome of NOt

Here i Found an Algorithm for This

Algorithm
take two varible i -0 & j=N (number)
keep storing bits of number from lsb in reverse order (e.g. shift i left & do or operation with j&1 (mind shud click this the way to extract right most set bit from number :)
keep shifting j right while j is not equals to 0

Explaintion

The first while loop reverses the rightmost bits of the number, stopping after the leftmost 1-bit. It does this by anding out the low-order bit of the number j and oring it into a new number, i. Then j is shifted right. E.g., the number j = 01101 becomes 01011. If the number j matches the input number, then the input number is a palindrome, and the procedure returns TRUE. If the reversed number is less than the input number, it may be that the input number has trailing zeros. E.g., 0110 has reversal 0011. Since this is less than the input number, we shift it left until it is no longer less, giving 0110. Since this equals the input number, we call the number a palindrome. If you don't want to consider the leading zeros, then you leave out the second while loop and say that the number 0110 is not a palindrome.


#include

bool isPalindrome(int N)
{
int i = 0, j = N;
while(j)
{
i = (i << 1) | (j & 1); j >>= 1;
}
return(i == N);
}

int main()
{
printf( " %d ", isPalindrome(9));

}


TC O(logn) as You Know that n=logk(base 2)
Sc O(1)
Run Here http://ideone.com/ddovS


Most Optimized Way can Be Find Here http://www-graphics.stanford.edu/~seander/bithacks.html#BitReverseTable in O(1) :)

WAP Search An Element in N-Ary Tree Efficiently

Given an n-ary tree , you have to search for an element in the tree without using recursion.
int FindNum(node *head, int num)
{

}

Note: Review Needed...??

Using BFS is Absolutely Efficient Way to Solve it..kep in Mind Recursion(DFS) is not good because it needs memory stack.

#include
#include
#define MAX_Q_SIZE 500
 
/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
    int data;
    struct node *child[];
   
};
 
/* frunction prototypes */
struct node** createQueue(int *, int *);
void enQueue(struct node **, int *, struct node *);
struct node *deQueue(struct node **, int *);
 
/* Given a binary tree, print its nodes in level order
   using array for implementing queue */
void printLevelOrder(struct node* root,int val)
{
  int rear, front;
  struct node **queue = createQueue(&front, &rear);
  struct node *temp_node = root;
  int i=0;
  while(temp_node)
  {
     if(temp_node->data==val)
printf("item found");
else
printf(" Item DNE");

  i=0;
    /*Enqueue left child */
if(temp_node->child[i])
{
     while(temp_node->child[i)
{
       enQueue(queue, &rear, temp_node->left);
i++;
}
 
    
 
    /*Dequeue node and make it temp_node*/
    temp_node = deQueue(queue, &front);
  }
}
 
/*UTILITY FUNCTIONS*/
struct node** createQueue(int *front, int *rear)
{
  struct node **queue =
   (struct node **)malloc(sizeof(struct node*)*MAX_Q_SIZE); 
 
  *front = *rear = 0;
  return queue;
}
 
void enQueue(struct node **queue, int *rear, struct node *new_node)
{
  queue[*rear] = new_node;
  (*rear)++;
}    
 
struct node *deQueue(struct node **queue, int *front)
{
  (*front)++;
  return queue[*front - 1];
}    
 
/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->data = data;
  node->left = NULL;
  node->right = NULL;
 
  return(node);
}
 
/* Driver program to test above functions*/
int main()
{
  struct node *root = newNode(11);
int i=0,j=0;int k=1;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
   root->child[i]= newNode(k);
k++;
}
k++;
root=root->child[i];
}
  
  printf("Level Order traversal of binary tree is \n");
  printLevelOrder(root);
 
  getchar();
  return 0;
}

TC O(nlogn)
SC O(1)
Run Here

WAP to convert a given string to its palindrome string by appending min chars at the right side of string.

Example
e.g. i/p is abc , o/p should be abcba
i/p is aaba , o/p should be aabaa.

aaba is not a palindrome

aaaa is a palindorme (so it does not require anything)

aabaa is also a palindrome (so it does not require anything)

Example 1:
-------------
str = abcbad;
revStr = dabcba;
output = abcbadabcba

Example 2:
----------------
str = abcb;
revStr = bcba;
output = abcba;

Ecample 3
str = rrrr
revstr=rrrr
output=rrrr

You have a note to write by cutting and pasting necessary letters from the book, write an algorithm to see if you can write the note.

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

public class NoteChecker
{

private final File noteFile;
private final File bookFile;

private int noteTotalLength = 0;

private void checkIfFileExists(File file)
{
if( ! file.exists() )
{
throw new IllegalArgumentException("File doesn't exists '" + file.getPath() + "'");
}
}

public NoteChecker(String noteFilePath, String bookFilePath){
super();

noteFile = new File(noteFilePath);
checkIfFileExists(noteFile);

bookFile = new File(bookFilePath);
checkIfFileExists(bookFile);
}

private int[] getRequiredLetters()
{

final int[] requiredLetters = new int[128];

Scanner noteSc = null;

try{

noteSc = new Scanner(noteFile);

while( noteSc.hasNextLine() ){
String line = noteSc.nextLine();

for(int i =0; i < line.length(); i++ ){
char ch = line.charAt(i);
++requiredLetters[ch];
++noteTotalLength;
}
}
}
catch(Exception ex ){
ex.printStackTrace();
return requiredLetters;
}
finally {
if( noteSc != null ){
noteSc.close();
}
}

return requiredLetters;
}

public boolean canCreateNote()
{

final int[] requiredLetters = getRequiredLetters();

Scanner bookSc = null;

try
{

bookSc = new Scanner(bookFile);

while( bookSc.hasNextLine() )
{
String line = bookSc.nextLine();

for(int i =0; i < line.length() && noteTotalLength > 0; i++ )
{
char ch = line.charAt(i);

if( requiredLetters[ch] > 0 )
{
--requiredLetters[ch];
--noteTotalLength;
}
}
}
}
catch(Exception ex)
{

ex.printStackTrace();
return false;
}
finally
{
if( bookSc != null )
{
bookSc.close();
}
}
return noteTotalLength == 0 ? true : false;
}



public static void main(String a[])
{

NoteChecker ob=new NoteChecker("E:/ubuntu/note.txt","E:/ubuntu/Input.txt");
System.out.println(ob.canCreateNote());


}
}
Above Solution is provided By Max

TC O(m+n)
SC O(1)

WAP to Find Maximum and minimum of an array using minimum number of comparisons

Write a C function to return minimum and maximum in an array. You program should make minimum number of comparisons.

First of all, how do we return multiple values from a C function? We can do it either using structures or pointers.

We have created a structure named pair (which contains min and max) to return multiple values.

?
struct pair
{
int min;
int max;
};
And the function declaration becomes: struct pair getMinMax(int arr[], int n) where arr[] is the array of size n whose minimum and maximum are needed.


Method 1

Initialize values of min and max as minimum and maximum of the first two elements respectively. Starting from 3rd, compare each element with max and min, and change max and min accordingly (i.e., if the element is smaller than min then change min, else if the element is greater than max then change max, else ignore the element)

/* structure is used to return two values from minMax() */
#include
struct pair
{
int min;
int max;
};

struct pair getMinMax(int arr[], int n)
{
struct pair minmax;
int i;

/*If there is only one element then return it as min and max both*/
if(n == 1)
{
minmax.max = arr[0];
minmax.min = arr[0];
return minmax;
}

/* If there are more than one elements, then initialize min
and max*/
if(arr[0] > arr[1])
{
minmax.max = arr[0];
minmax.min = arr[1];
}
else
{
minmax.max = arr[0];
minmax.min = arr[1];
}

for(i = 2; i {
if(arr[i] > minmax.max)
minmax.max = arr[i];

else if(arr[i] < minmax.min)
minmax.min = arr[i];
}

return minmax;
}

/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax (arr, arr_size);
printf("\nMinimum element is %d", minmax.min);
printf("\nMaximum element is %d", minmax.max);
getchar();
}

Time Complexity: O(n)
Space Complexity O(1)
Run Here https://ideone.com/yFZNJ

In this method, total number of comparisons is 1 + 2(n-2) in worst case and 1 + n – 2 in best case.
In the above implementation, worst case occurs when elements are sorted in descending order and best case occurs when elements are sorted in ascending order.



METHOD 2 (Tournament Method) (Efficient)

Divide the array into two parts and compare the maximums and minimums of the the two parts to get the maximum and the minimum of the the whole array.

Pair MaxMin(array, array_size)
if array_size = 1
return element as both max and min
else if arry_size = 2
one comparison to determine max and min
return that pair
else /* array_size > 2 */
recur for max and min of left half
recur for max and min of right half
one comparison determines true max of the two candidates
one comparison determines true min of the two candidates
return the pair of max and min
Implementation

/* structure is used to return two values from minMax() */
#include
struct pair
{
int min;
int max;
};

struct pair getMinMax(int arr[], int low, int high)
{
struct pair minmax, mml, mmr;
int mid;

/* If there is only on element */
if(low == high)
{
minmax.max = arr[low];
minmax.min = arr[low];
return minmax;
}

/* If there are two elements */
if(high == low + 1)
{
if(arr[low] > arr[high])
{
minmax.max = arr[low];
minmax.min = arr[high];
}
else
{
minmax.max = arr[high];
minmax.min = arr[low];
}
return minmax;
}

/* If there are more than 2 elements */
mid = (low + high)/2;
mml = getMinMax(arr, low, mid);
mmr = getMinMax(arr, mid+1, high);

/* compare minimums of two parts*/
if(mml.min < mmr.min)
minmax.min = mml.min;
else
minmax.min = mmr.min;

/* compare maximums of two parts*/
if(mml.max > mmr.max)
minmax.max = mml.max;
else
minmax.max = mmr.max;

return minmax;
}

/* Driver program to test above function */
int main()
{
int arr[] = {1000, 11, 445, 1, 330, 3000};
int arr_size = 6;
struct pair minmax = getMinMax(arr, 0, arr_size-1);
printf("\nMinimum element is %d", minmax.min);
printf("\nMaximum element is %d", minmax.max);
getchar();
}

Number of Instruction Executed less
Time Complexity: O(n)
Space Complexity
Run Here https://ideone.com/jB3tu

Total number of comparisons: let number of comparisons be T(n). T(n) can be written as follows:
Algorithmic Paradigm: Divide and Conquer

T(n) = T(floor(n/2)) + T(ceil(n/2)) + 2
T(2) = 1
T(1) = 0
If n is a power of 2, then we can write T(n) as:

T(n) = 2T(n/2) + 2
After solving above recursion, we get

T(n) = 3/2n -2
Thus, the approach does 3/2n -2 comparisons if n is a power of 2. And it does more than 3/2n -2 comparisons if n is not a power of 2.

WAP to generate the Dyck Word from given string.??

A Dyck word is a string consisting of n X's and n Y's such that no initial segment of the string has more Y's than X's

It Can Be Solved by Catalan Number Cn=2nCn/(n+1)=2n!/n!*n+1!

Cn is the number of Dyck words of length 2n. A For example, the following are the Dyck words of length 6:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY.


class DyckWord
{
public static void printDyckWord(int xnum, int ynum, char[] str, int count)
{
if (xnum < 0 || ynum < xnum) return; // invalid state
if (xnum == 0 && ynum == 0)
{
System.out.println(str); // found one, so print it
}
else
{
if (xnum > 0) { // try a left paren, if there are some available
str[count] = 'X';
printDyckWord(xnum - 1, ynum, str, count + 1);
}
if (ynum > xnum) { // try a right paren, if there’s a matching left
str[count] = 'Y';
printDyckWord(xnum, ynum - 1, str, count + 1);
}
}
}

public static void printDyckWord(int count)
{
char[] str = new char[count*2];//As DyckWord is 2n length nX + nY
printDyckWord(count, count, str, 0);
}
public static void main(String a[])
{
printDyckWord(3);
}
}

Time Complexity O(n)
Space Complexity O(1)
Run Here http://www.ideone.com/pBgGO

WAP to Calculate the next Smallest Prime Number From Given Number Efficiently

Given a number n, compute the smallest prime that is bigger than n. For example, n=8, then the smallest prime that bigger than 8 is 11. n=23 o/p is 29 & so on

#include

int power(int x, int y)
{
int temp;
if( y == 0)
return 1;
temp = power(x, y/2);
if (y%2 == 0)
return temp*temp;
else
return x*temp*temp;
}


double sqrt(const double s)
{

double xn = s / 2.0;
double lastX = 0.0;

// Looping this way ensures we perform only as many calculations as necessary.
// Can be replaced with a static for loop if you really want to.
while(xn != lastX) {
lastX = xn;
xn = (xn + s/xn) / 2.0;
}

return xn;

}
bool is_prime(int x)
{
if(x <= 1)
return false;
int s = (int) sqrt(x);
for(int i = 2; i <= s; i++)
if(x%i == 0)
return false;
return true;
}

int next_prime(int n)
{
int i=n+1;


/*The largest known Mersenne prime (243,112,609 − 1) is also the largest known prime
number,else // no such prime exist explain above
int pow=power(2,243112609)−1;
if(n>pow)
return 0; this line wont execute overflow*/

while(true)
{

if(is_prime(i))
break;
i++;

}
return i;
}
int main()
{
printf( " %d ", next_prime(23));
return 0;

}


TC of isprime is O(sqrt(n))
TC of sqrt is log(n)
TC of pow function is O(logn)
TC of next prime O(k*sqrt(n) where k is number of iteration used to find next smallest prime so k is constant & so overall time complexity of this algo is O(sqrt(n))

TC O(sqrt(n))
SC O(1)
Run Here https://ideone.com/5ViQe

Feel Free to Comment or Optimize the solution or if any issue with time complexity