Jit
BAN USER- 0of 0 votes
AnswersA certain string-processing language allows a programmer to break a string into two pieces. Because this operation copies the string, it costs n time units to break a string of n characters into two pieces. Suppose a programmer wants to break a string into many pieces. The order in which the breaks occur can affect the total amount of time used. For example, suppose that the programmer wants to break a 20-character string after characters 2, 8, and 10 (numbering the characters in ascending order from the left-hand end, starting from 1). If she programs the breaks to occur in left-to-right order, then the first break costs 20 time units, the second break costs 18 time units and the third break costs 12 time units, totaling 50 time units. If she programs the breaks to occur in right-to-left order, however, then the first break costs 20 time units, the second break costs 10 time units, and the third break costs 8 time units, totaling 38 time units. In yet another order, she could break first at 8 (costing 20), then break the left piece at 2 (costing 8), and finally the right piece at 10 (costing 12), for a total cost of 40. Design an algorithm that, given the numbers of characters after which to break, determines a least-cost way to sequence those breaks. More formally, given a string S with n characters and an array L[1..m] containing the break points, compute the lowest cost for a sequence of breaks, along with a sequence of breaks that achieves this cost. (Dynamic Programming solution)
- Jit| Report Duplicate | Flag | PURGE
Software Engineer / Developer Algorithm
#include <stdio.h>
#include <string.h>
#define FALSE 0
#define TRUE 1
int main()
{
/*
The logic is that maintain a histogram.
scan the first anagram and for each character
increase the correspoding entry in the histogram by 1.
now scan the second anagram and decrese the correspoding
entry in the first array by one. if at any point, the first array entry is
zero before decreasing then they can't be anagrams.
O(n) solution
*/
char wordString1[100];
char wordString2[100];
int histogram[256];
int index = 0;
int flag = TRUE;
int numberOfString = 0;
//printf("Enter the two anagrams..\n");
scanf("%d",&numberOfString);
scanf("%s%s",wordString1,wordString2);
if(strlen(wordString1) != strlen(wordString2))
{
printf("The two strings can't be anagrams..\n");
return FALSE;
}
bzero(histogram, 26*sizeof(int));
/*Scan first array and increment the new array entry*/
while(index < strlen(wordString1))
if(wordString1[index] >= 'A' && wordString1[index] <= 'Z')
{
histogram[wordString1[index] - 'A']++;
}
else if(wordString1[index] >= 'a' && wordString1[index] <= 'z')
{
histogram[wordString1[index] - 'a']++;
}
else
{
flag = FALSE;
break;
}
index++;
}
if(flag == FALSE)
{
printf("Two strings can't be anagrams..\n");
return 0;
}
index = 0;
while(index < strlen(wordString2))
{
if(wordString2[index] >= 'A' && wordString2[index] <= 'Z')
{
if(histogram[wordString2[index] - 'A'] != 0)
{
histogram[wordString2[index] - 'A']--;
}
else
{
flag = FALSE;
break;
}
}
else if(wordString2[index] >= 'a' && wordString2[index] <= 'z')
{
if(histogram[wordString2[index] - 'a'] != 0)
{
histogram[wordString2[index] - 'a']--;
}
else
{
flag = FALSE;
break;
}
}
index++;
}
if(flag == FALSE)
{
printf("Two strings are not anagrams..\n");
}
else
{
printf("Two strings are anagrams..\n");
}
return 0;
}
The solution is to sort the numbers. O(nlogn)
Then start from start and end of the array. If the sum of the first and last element exceeds the given number then the last number can't be in a pair. So, decrement the last index. else if the sum is less than the given number, then first number can't be in a pair. So, increment the first index. continue this until first index is less than last index.
void MergeTwoSortedList(node** list1, node** list2)
{
node* temp = NULL;
node* slow = NULL;
node* fast = NULL;
while(*list1)
{
if((*list1)->val <= (*list2)->val)
{
temp = *list1;
*list1 = (*list1)->next;
temp->next = NULL;
temp->next = *list2;
*list2 = temp;
}
else
{
slow = *list2;
fast = (*list2)->next;
while(fast != NULL && fast->val <= (*list1)->val)
{
slow = slow->next;
fast = fast->next;
}
temp = *list1;
*list1 = (*list1)->next;
temp->next = fast;
}
}
}
The list "list2" contains the merged list of list1 and list2.
- Jit January 30, 2011Making the -ve numbers +ve won't give you the desired solution. Let's say the array has the following numbers {2,3,4,5,6,7}.
Making the odd numbers -ve yields {2, -3, 4, -5, 6, -7}.
After sorting it yields {-7, -5, -3, 2, 4, 6}.
Now converting -ve numbers into +ve yields {7, 5, 3, 2, 4, 6} which does not conform to the desired solution. well, you need to sort the first half (7, 5, 3) again to get the solution.
I guess the solution could be first partitioning the original array into odd and even numbers and then employing any sorting technique on both part (odd and even) of the array would result in the desired ouput.
1. when the list is sorted
void removeDuplicatesFromSortedList(node* list)
{
node* current = list;
node* nextNext = NULL;
while(current->next != NULL)
{
if(current->val == current->next->val)
{
nextNext = current->next->next;
free(current->next);
current->next = nextNext;
}
else
{
current = current->next;
}
}
}
/*
Given a number N.
Now you have to find the next
highest number that is a palindrome.
*/
#include <stdio.h>
#include <string.h>
void AddOne(char str[], int len);
void MakeMirror(char str[], int high, int low);
int main()
{
int strLen = 0; /*String Length*/
int lIndex = 0; /*Low Index*/
int hIndex = 0; /*High Index*/
int kIndex = 0; /*temporary index to traverse the string*/
char str[10];
//fflush(stdin);
gets(str); /*Dangerous to use, instead use fgets with appropriate modifications.*/
strLen = strlen(str);
AddOne(str, strLen-1);
lIndex = strLen/2;
/*The number consist of all 9's*/
if(str[0] == '9'+1)
{
str[0] = '1';
str[strLen] = '1';
}
/*The number does not have all 9's as its digits*/
else
{
if(lIndex == (strLen + 1)/2)
{
/*The lenght of the string is even*/
hIndex = lIndex - 1;
}
else
{
/*The length of the string is odd*/
hIndex = lIndex;
}
while(str[hIndex - kIndex] == str[lIndex + kIndex])
{
kIndex++;
}
if(str[hIndex - kIndex] < str[lIndex + kIndex])
{
AddOne(str, hIndex);
}
MakeMirror(str, hIndex, lIndex);
}
printf("[%s]\n",str);
}
/*
This function checks whether all the digits are 9.
If all the digits are 9, then all except the MSB is set to 0.
MSB is set to ('9'+1)
*/
void AddOne(char pStr[], int pLen)
{
while((pStr[pLen] == '9') && (pLen > 0))
{
pStr[pLen] = '0';
pLen--;
}
pStr[pLen]++;
}
/*
This function makes the lower half of the string a mirror
copy of the higher half of the string, thereby making a
palindrome.
*/
void MakeMirror(char str[ ], int high, int low)
{
while(str[low])
{
str[low] = str[high];
low++;
high--;
}
}
Sort the elements of the array using merge sort technique.
This operation takes O(nlogn) time.
Now let's say "i" is the first index of the array and "j" is the last index of the array. use the following algorithm.
while(i < j)
{
if((arr[i] + arr[j]) == key)
{
printf("(%d,%d)",arr[i],arr[j]);
i++;
j++;
}
else((arr[i] + arr[j]) > key)
{
j--;
}
else
{
i++;
}
}
This operation takes O(n) time.
So, overall complexity of the algorithm is O(nlogn).
#include <stdio.h>
int division(int x, int y);
int main()
{
int numerator = 0;
int denominator = 0;
int res = 0;
printf("Enter numerator and denominator: \n");
scanf("%d%d",&numerator,&denominator);
if(denominator == 0)
{
printf("Denominator can't be zero in a division..\n");
return 1;
}
res = division(numerator, denominator);
printf("Integer Division Result= [%d]\n",res);
return 0;
}
int division(int numerator,int denominator)
{
int count = 0;
if(numerator < denominator)
{
return count;
}
while(numerator > denominator)
{
numerator = numerator - denominator;
count++;
}
}
Guys, there is some amount of repeated code. Any optimized version would be highly appreciated..
Please suggest any other better approach..
Time Complexity is O(n).
#include <stdio.h>
#include <stdlib.h>
struct Number
{
int key;
struct Number* next;
};
typedef struct Number node;
void createDigits(node **);
void printDigits(node *);
void reverseDigits(node **);
void addDigits(node *, node *, node **);
int main()
{
node* head1 = NULL;
node* head2 = NULL;
node* head3 = NULL;
printf("Create the first number..\n");
createDigits(&head1);
if(head1 == NULL)
{
printf("First Input is not correct..\n");
return 1;
}
printf("Create the second number..\n");
createDigits(&head2);
if(head2 == NULL)
{
printf("Second Input is not correct..\n");
return 1;
}
printf("Number 1: \n");
printDigits(head1);
printf("\n");
printf("Number 2: \n");
printDigits(head2);
printf("\n");
printf("Number 1 reversed..\n");
reverseDigits(&head1);
printDigits(head1);
printf("\n");
printf("Number 2 reversed..\n");
reverseDigits(&head2);
printDigits(head2);
printf("\n");
printf("Add the two reversed numbers node by node..\n");
addDigits(head1, head2, &head3);
printf("Reversing the result to get the actual result..\n");
reverseDigits(&head3);
printf("sum of two numbers in linked representation is: \n");
printDigits(head3);
printf("\n");
return 0;
}
void createDigits(node **list)
{
int digit = 0;
node* tNode = NULL;
printf("Enter positive digits to insert..(enter -999 to exit)\n");
scanf("%d",&digit);
if(digit == -999)
{
printf("Input completed..\n");
}
else
{
if(NULL == *list)
{
*list = (node *)malloc(sizeof(node));
(*list)->key = digit;
(*list)->next = NULL;
createDigits(list);
}
else
{
tNode = *list;
while(tNode->next != NULL)
tNode = tNode->next;
tNode->next = (node *)malloc(sizeof(node));
tNode = tNode->next;
tNode->key = digit;
tNode->next = NULL;
createDigits(list);
}
}
}
void printDigits(node* list)
{
if(list->next != NULL)
{
printf("%d->",list->key);
printDigits(list->next);
}
else if(list->next == NULL && list->key != -999)
{
printf("%d\n",list->key);
}
else
{
printf("Empty List..\n");
}
}
void reverseDigits(node** list)
{
node* temp1 = *list;
node* temp2 = NULL;
node* temp3 = NULL;
while(temp1)
{
*list = temp1;
temp2 = temp1->next;
temp1->next = temp3;
temp3 = temp1;
temp1 = temp2;
}
//return *list;
}
void addDigits(node* head1, node* head2, node** head3)
{
node* temp = NULL;
int keyVal = 0;
static int pass = 0;
if(head1 != NULL && head2 != NULL)
{
keyVal = head1->key + head2->key + pass;
if(*head3 == NULL)
{
*head3 = (node *)malloc(sizeof(node));
if(*head3 == NULL)
{
printf("Memory Allocation Failed..\n");
}
if(keyVal >= 10)
{
(*head3)->key = keyVal-10;
pass = 1;
}
else
{
(*head3)->key = keyVal;
pass = 0;
}
(*head3)->next = NULL;
}
else
{
temp = *head3;
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
if(keyVal >= 10)
{
temp->key = keyVal-10;
pass = 1;
}
else
{
temp->key = keyVal;
pass = 0;
}
temp->next = NULL;
}
head1 = head1->next;
head2 = head2->next;
addDigits(head1, head2, head3);
}
else if(head1 == NULL && head2 != NULL)
{
keyVal = head2->key + pass;
if(*head3 == NULL)
{
*head3 = (node *)malloc(sizeof(node));
if(*head3 == NULL)
{
printf("Memory Allocation Failed..\n");
}
if(keyVal >= 10)
{
(*head3)->key = keyVal-10;
pass = 1;
}
else
{
(*head3)->key = keyVal;
pass = 0;
}
(*head3)->next = NULL;
}
else
{
temp = *head3;
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
if(keyVal >= 10)
{
temp->key = keyVal%10;
pass = 1;
}
else
{
temp->key = keyVal;
pass = 0;
}
temp->next = NULL;
}
head2 = head2->next;
addDigits(head1, head2, head3);
}
else if(head1 != NULL && head2 == NULL)
{
keyVal = head1->key + pass;
if(*head3 == NULL)
{
*head3 = (node *)malloc(sizeof(node));
if(*head3 == NULL)
{
printf("Memory Allocation Failed..\n");
}
if(keyVal >= 10)
{
(*head3)->key = keyVal-10;
pass = 1;
}
else
{
(*head3)->key = keyVal;
pass = 0;
}
(*head3)->next = NULL;
}
else
{
temp = *head3;
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
if(keyVal >= 10)
{
temp->key = keyVal-10;
pass = 1;
}
else
{
temp->key = keyVal;
pass = 0;
}
temp->next = NULL;
}
head1 = head1->next;
addDigits(head1, head2, head3);
}
else if(pass == 1)
{
temp = *head3;
while(temp->next != NULL)
temp = temp->next;
temp->next = (node *)malloc(sizeof(node));
if(temp->next == NULL)
{
printf("Memory Allocation Failed..\n");
}
temp = temp->next;
temp->key = pass;
temp->next = NULL;
}
}
lets say the numbers are 1->2->3 and 1->2
After reversing the lists look like 3->2->1 and 2->1
Now add the two lists node by node and properly take care of the carry over of the addition of the nodes, if any.
so, the resultant added list will look like 5->3->1
Now reverse the "resultant added list" to get the result of addition of two original lists. That is 1->3->5 is the actual answer.
The above code with a little modification..
#include <stdio.h>
#include <string.h>
void encrypt_decrypt_String(int kShift, int pOption);
int main()
{
int option = 0;
int shift = 0;
printf("Enter the shift for caeser cipher..\n");
scanf("%d",&shift);
printf("Enter 1 to encrypt and 0 to decrypt..\n");
scanf("%d",&option);
while(getchar() != '\n');
encrypt_decrypt_String(shift, option);
}
void encrypt_decrypt_String(int kShift, int pOption)
{
char ch;
ch = getchar();
while(ch != '\n')
{
if(ch == ' ')
{
putchar(' ');
}
else
{
if(pOption == 1)
{
if(isupper(ch))
{
putchar('A' + (ch + kShift - 'A')%26);
}
else
{
putchar('a' + (ch + kShift - 'a')%26);
}
}
else if(pOption == 0)
{
if(isupper(ch))
{
putchar('Z' + (ch - kShift - 'Z')%26);
}
else
{
putchar('z' + (ch - kShift - 'z')%26);
}
}
else
{
printf("Option not supported..\n");
break;
}
}
ch = getchar();
}
putchar(ch);
}
#include <stdio.h>
void encrypt_decrypt_String(int kShift, int pOption);
int main()
{
int option = 0;
int shift = 0;
printf("Enter the shift for caeser cipher..\n");
scanf("%d",&shift);
printf("Enter 1 to encrypt and 0 to decrypt..\n");
scanf("%d",&option);
while(getchar() != '\n');
encrypt_decrypt_String(shift, option);
}
void encrypt_decrypt_String(int kShift, int pOption)
{
char ch;
ch = getchar();
while(ch != '\n')
{
if(ch == ' ')
{
putchar(' ');
}
else
{
if(pOption == 1)
putchar(ch + kShift);
else if(pOption == 0)
putchar(ch - kShift);
else
{
printf("Option not supported..\n");
break;
}
}
ch = getchar();
}
putchar(ch);
}
To generalize the idea, let's say the random number generator generates from number 1 to 100. Then as per the question, the number of sequences that could be our desired output is (1..10) or (2..11) or (3..12) and so on till (91-100). So, there are 91 sequences. The total number of solution space that we have is 100^10.
The probability is 91/(100^10).
Guys, correct me if I am wrong.
#include <stdio.h>
#include <string.h>
void reverse_string(char str[], int i, int j);
int main()
{
int left = 0;
int right = 0;
char pString[100];
bzero(pString, 100*sizeof(char));
printf("Enter the string..\n");
scanf("%s",pString);
right = strlen(pString) - 1;
reverse_string(pString, left, right);
printf("Reversed string is [%s]\n", pString);
return 0;
}
void reverse_string(char str [ ], int start, int end)
{
char buf[1];
bzero(buf, sizeof(char));
if(start < end)
{
buf[0] = str[start];
str[start] = str[end];
str[end] = buf[0];
start++;
end--;
reverse_string(str, start, end);
}
}
#include <stdio.h>
void decimal_to_roman(int num); /*Main function which processes the number and calls print_D2R().
It also calls itself RECURSIVELY to process the residual number*/
void print_D2R(char ch, int x); /*Prints the character ch x times (ch ch ch...(x times)) */
int main()
{
int val = 0;
printf("Enter the number..\n");
scanf("%d",&val);
decimal_to_roman(val);
printf("\n");
return 0;
}
void decimal_to_roman(int num)
{
int quotient = 0;
int remainder = 0;
int index = 0;
int temp = 0;
if(num >= 1000)
{
quotient = num/1000;
remainder = num%1000;
if(remainder == 0)
{
print_D2R('M', quotient);
}
else
{
print_D2R('M', quotient);
decimal_to_roman(remainder);
}
}
else if(num >= 500 && num < 1000)
{
if(num >= 900 && num < 1000)
{
temp = num - 900;
print_D2R('C', 1);
print_D2R('M', 1);
decimal_to_roman(temp);
temp = 0;
}
else
{
quotient = num/500;
remainder = num%500;
if(remainder == 0)
{
print_D2R('D', quotient);
}
else
{
print_D2R('D', quotient);
decimal_to_roman(remainder);
}
}
}
else if(num >= 100 && num < 500)
{
if(num >= 400 && num < 500)
{
temp = num - 400;
print_D2R('C', 1);
print_D2R('D', 1);
decimal_to_roman(temp);
temp = 0;
}
else
{
quotient = num/100;
remainder = num%100;
if(remainder == 0)
{
print_D2R('C', quotient);
}
else
{
print_D2R('C', quotient);
decimal_to_roman(remainder);
}
}
}
else if(num >= 50 && num < 100)
{
if(num >= 90 && num < 100)
{
temp = num - 90;
print_D2R('X', 1);
print_D2R('C', 1);
decimal_to_roman(temp);
temp = 0;
}
else
{
quotient = num/50;
remainder = num%50;
if(remainder == 0)
{
print_D2R('L', quotient);
}
else
{
print_D2R('L', quotient);
decimal_to_roman(remainder);
}
}
}
else if(num >= 10 && num < 50)
{
if(num >= 40 && num < 50)
{
temp = num - 40;
print_D2R('X', 1);
print_D2R('L', 1);
decimal_to_roman(temp);
temp = 0;
}
else
{
quotient = num/10;
remainder = num%10;
if(remainder == 0)
{
print_D2R('X', quotient);
}
else
{
print_D2R('X', quotient);
decimal_to_roman(remainder);
}
}
}
else if(num < 10)
{
switch (num)
{
case 1:
printf("I");
break;
case 2:
printf("II");
break;
case 3:
printf("III");
break;
case 4:
printf("IV");
break;
case 5:
printf("V");
break;
case 6:
printf("VI");
break;
case 7:
printf("VII");
break;
case 8:
printf("VIII");
break;
case 9:
printf("IX");
break;
default:
break;
}
}
}
void print_D2R(char ch, int times)
{
int tIndex = 0;
for(tIndex = 0; tIndex < times; tIndex++)
{
printf("%c",ch);
}
}
well, if the list has more than n/2 elements repeated, then that, repeated, element would be the median of the list when sorted. So, we can apply selection algorithm to find the median of the list in O(n) time. That means we need to find out the (n/2)th rank element in the list. Similarly, we can find (n/4)th rank element in O(n) time.
- Jit August 15, 2011Guys, if you have any better solution, please share.