R
We are given two strings P and Q, each consisting of N lowercase English letters. For each position in the strings, we have to choose one letter from either P or Q, in order to construct a new string S, such that the number of distinct letters in S is minimal. Our task is to find the number of distinct letters in the resulting string S.
For example, if P = "ca" and Q = "ab", S can be equal to: "ca", "cb", "aa" or "ab". String "aa" has only one distinct letter ('a'), so the answer is 1 (which is minimal among those strings).
Write a function:
int solution(char *P, char *Q);
that, given two strings P and Q, both of length N, returns the minimum number of distinct letters of a string S, that can be constructed from P and Q as described above.
Examples:
1. Given P = "abc", Q = "bcd", your function should return 2. All possible strings S that can be constructed are: "abc", "abd", "acc", "acd", "bbc", "bbd", "bcc", "bcd". The minimum number of distinct letters is 2, which be obtained by constructing the following strings: "acc", "bbc", "bbd", "bcc".
2. Given P = "axxz", Q = "yzwy", your function should return 2. String S must consist of at least two distinct letters in this case. We can construct S = "yxxy", where the number of distinct letters is equal to 2, and this is the only optimal solution.
3. Given P = "bacad", Q = "abada", your function should return 1. We can choose the letter 'a' in each position, so S can be equal to "aaaaa".
4. Given P = "amz", Q = "amz", your function should return 3. The input strings are identical, so the only possible S that can be constructed is "amz", and its number of distinct letters is 3.
Write an efficient algorithm for the following assumptions:
N is an integer within the range [1..200,000];
strings P and Q are both of length N;
strings P and Q are made only of lowercase letters (a−z);
strings P and Q contain a total of at most 20 distinct letters.
How to solve this code ?
Naveen
Hello guys,
Can anyone please help to solve this problem in O(N) time complexity?
Problem Statement
You are given an array(Arr) of N Distinct integers. You have to find the sum of minimum element of all the subarrays (continous) in that array. See Sample for better understanding.
Input
The first line of input contains N, the size of the array
The second line of input contains N space-separated integers
Constraints
2 ≤ N ≤ 100000
1 ≤ Arr[i] ≤ 1000000000
Output
The output should contain single integers, the sum of minimum element of all the subarrays in that array.
Example
Sample Input
3
1 2 3
Sample Output
10
Explaination
all subarrays [1] [1,2] [1,2,3] [2] [2,3] [3]
Sum of minimums : 1 + 1 + 1 + 2 + 2 + 3 = 10
Anonymous
And can you explain to me what *FILE and (stdin) have to do with all this, they are the things that confuse me the most.
Ok. So you are talking about Streams concept in C. Streams in C++ is different abstraction which is what I was talking about earlier.
Streams in C is a generic concept that allows us to perform I/O operations on it.
Generally when using C on *nix environments, you can work with files using a file descriptor that the OS returns to you or you can use a FILE* object. The functions that you call to work on the descriptor and the FILE* object are different. The C standard library and the POSIX library allows us to get a descriptor from a FILE* object and vice versa.
The FILE* object is what is commonly referred to as a stream in the C world. stdin, stdout and stderr are all FILE* objects.
As for the difference between a FILE (stream) and a naked file descriptor, the FILE object is provided by the C library which adds additional things like buffering, error detection, EOF detection and so on to make I/O more performing and easier to use. When you work with naked file descriptors, you generally work at the level of system calls and rely on OS. Calls like fflush are used to flush the C library buffers, while calls like fsync are used to flush the kernel buffers.
You can think of streams (FILE* objects) as an abstraction on top of the naked file descriptors that help improve the speed and ease of reading and writing to and from files. They minimize the overhead of multiple system calls
Streams in C++ is an abstraction at a slightly higher layer than streams in C. They help with formatted input, output and provide slightly more features than the ones provided by the C library like for ex automatic closure of the underlying file when the fstream object leaves the scope and so on.
That is about it.
I_Guess_You_Are_
#include <stdio.h>
void getinput() {
int matriculation_number;
printf("what is your matriculation number?';
scanf("%d"&matriculation_number);
printf("My matriculation number is %d", matriculation_number);
}
Tommaso
#include <stdio.h>
void getinput() {
int matriculation_number;
printf("what is your matriculation number?”);
scanf("%d",&matriculation_number);
printf("My matriculation number is %d", matriculation_number);
}
Anonymous
Hello, how do I print coordinates (x,y) in the cartesian plane in the console? I have an exercise that asks to print the coordinates on the plane.
Ilya
if (status=='F')
{
printf("Full-Time\n");
if (Year_serviced < 5)
{
new_salary= (0.04*salary)+ salary;
printf("your new salary is %.2f\n", new_salary);
}
if (Year_serviced >= 5)
{
new_salary= (0.05*salary)+ salary;
printf("your new salary is %.2f\n", new_salary);
}
}