Katya has a sequence of integers a1,a2,…,an and an integer m.
She defines a good sequence of integers as a non-empty sequence such that the sums of all its non-empty subsequences are divisible by m.
Katya wants to know the number of good subsequences of the sequence a. Can you help her?
I have written a code for this question...but its showing wrong answer. Now i dont want source code for this question.. I just want to know whats wrong in my source code???
#include<bits/stdc++.h>
usingnamespace std;
// Return sum of sum of all sub-sequence.
int sum(int arr[], int n)
{
int ans = 0;
// Finding sum of the array.
for (int i = 0; i < n; i++)
ans += arr[i];
return ans * pow(2, n - 1);
}
// Driver Code
int main()
{
int arr[] = { 6, 7, 8 };
int n = sizeof(arr)/sizeof(arr[0]);
cout << sum(arr, n) << endl;
return 0;
}
#include<bits/stdc++.h>
usingnamespace std;
void printSubsequences(int arr[], int n)
{
/* Number of subsequences is (2**n -1)*/
unsignedint opsize = pow(2, n);
/* Run from counter 000..1 to 111..1*/
for (int counter = 1; counter < opsize; counter++)
{
for (int j = 0; j < n; j++)
{
/* Check if jth bit in the counter is set
If set then print jth element from arr[] */
if (counter & (1<<j))
cout << arr[j] << " ";
}
cout << endl;
}
}
// Driver program
int main()
{
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "All Non-empty Subsequences\n";
printSubsequences(arr, n);
return 0;
}
You are given a string S of lowercase English letters with length N. You are allowed to (but don't have to) choose one index in this string and change the letter at this index to any other lowercase English letter. The cost of this operation is the absolute value of the difference of ASCII values of the new letter and the original letter; let's denote it by X.
Next, consider the number of pairs of indices (i,j) in the resulting string (the string after changing one letter, or the original string if no letter was changed) such that 1≤i<j≤N and Si<Sj. Let's denote it by Y.
You are given a string S of lowercase English letters with length N. You are allowed to (but don't have to) choose one index in this string and change the letter at this index to any other lowercase English letter. The cost of this operation is the absolute value of the difference of ASCII values of the new letter and the original letter; let's denote it by X.
Next, consider the number of pairs of indices (i,j) in the resulting string (the string after changing one letter, or the original string if no letter was changed) such that 1≤i<j≤N and Si<Sj. Let's denote it by Y.
In this way the number of comparisons are reduced by many many factors as compared to alcatraz code. TLE is now not coming but still this is WA. When inputs are a[n]=1,2,3,4,5 and M=3, my output is 6 and alcatraz output is 10. I know from my friends that 6 is not correct output, But I am not sure about 10.
Can anyone give idea how to improve this code.
Alcatraz goes with 2^n , max = 10^9;
My code does n^3 at max, max=30^3=27000;
Now, I get it. Just do one thing ,if any one is lagging somewhere. count the number of numbers that are divisible by m, then count the number of possibilities of those number.
Try, search, try, search......till you get correct answer.
There is no need to write such complex codes. The problem is very simple once you understand the meaning of the question. You have to find the number of sub-arrays of the given array such that :
1. all the elements in the sub-array are divisible by the given number.
2. Sum of the elements in sub-array is divisible by given number(this is automatically satisfied if
u satisfy the first condition.So, dont bother about this.)
So, now you know what to do. You have to count the number of elements in the main array which are divisible by the required number(let it be x). And find the number of sequences you can generate by using these x elements(which is (2^x)-1).
Is 1 , 2 with m=3 a good subsequence? I am confused by the definition of a good sequence as sum of all its subsequences ("1"+"2"+"1,2") is 6 which is divisible by 3. But according to the question "1","2","1,2" all of them must be divisible by 3 which is not satisfied.
@imrajkumar
Please read the two conditions I have mentioned above.
Both the sum and the individual elements must be divisible by m.
here, if u consider the sub array {1,2}, only the sum(which is 3) is divisible by m.
But the individual elements(which are 1,2) are not divisible by m.
so, it cannot be considered as a required sub-sequence.
Example : If u consider array {1,2,3,4,5,6} with m=3
Only 3,6 are divisible by 3. so count=2
no.of subsequences=(2^2)-1=3 which are {3}{6}{3,6}. Hence 3 is the answer.
Note that , both the sum of these subsequences and individual elements are now divisible by m.
I hope u understood now.