ninhnnsoc
BAN USERFor input a = 173, b=10000003210005, my answer is 1246892717288.
Look at my implementation first, ignore below explanation.
Suppose the input is 64 bits.
We can see that there are only 9 Fibonacci numbers less than 64: 1, 2, 3, 5, 8, 13, 21, 34, 55.
My solution uses combinatorial formula.
The number C of all numbers of length N bits and have bit sum of R is:
C(N,R) = N_choose_R = N! / (R! * (N-R)!);
This can be efficiently computed using "Pascal Triangle" without overflow.
The hard part is how to count the answer for all numbers that less than a number Y.
Lets take a concrete example:
Count the number of numbers less than Y=106 that have bit sum of R=3.
Y = 106 = 1101010 in binary; N = 7 bits.
R = 3
Consider numbers in following forms Y1, Y2, Y3, Y4:
Y = 1101010
Y1 = 0xxxxxx // turn first '1' off
Y2 = 10xxxxx // turn second '1' off
Y3 = 1100xxx // turn third '1' off
Y4 = 110100x // turn last '1' off
where x can be any bit.
Then, numbers in forms of Y1, Y2, Y3, Y4 have 3 properties:
1. All are less than Y;
2. They are non-overlap;
3. They cover all possible numbers less than Y.
Thus, now I have to count how many numbers in each form that satisfy the requirement
For Y1: there are C(6,3) such numbers;
For Y2: there are C(5,2) such numbers;
For Y3: there are C(3,1) such numbers;
For Y4: There are C(1,0) such numbers;
The final answer is: there are C(6,3) + C(5,2) + C(3,1) + C(1,0) = 34 numbers that less than 106 and have bit sum of 3.
To answer the original question, we have to do for all 9 Fibonacci numbers.
And a trick:
[a,b] = [0, b+1) - [0,a)
EDITED:
Time complexity: O(log b * log log b)
Reasons:
Number of bits in the number b is n = log b
Number of Fibonacci numbers that are less than n is O(log n).
CODE:
#include <iostream>
#include <string.h>
//typedef unsigned long long ull;
using namespace std;
unsigned long long a,b; // must be >=0
unsigned long long NCR[66][66]; // number of combinations N_choose_R
const int nFibo = 9;
int Fibo[9] = {1, 2, 3, 5, 8, 13, 21, 34, 55};
//--------------------------------------
void PascalTriangle(int Nmax){ // Pascal Triangle is the best for avoiding overflow!
memset(NCR,0,sizeof(NCR));
NCR[1][1] = 1;
for(int i = 2; i<=Nmax; i++){
for(int j = 1; j<=i; j++){
NCR[i][j] = NCR[i-1][j-1] + NCR[i-1][j];
};
};
/*
for(int i = 1; i<=Nmax; i++){
for(int j = 1; j<=i; j++) cout <<NCR[i][j]<<" ";
cout <<endl;
}
*/
};
//--------------------------------------
unsigned long long NCR_Of(int n, int r){
return NCR[n+1][r+1];
}
//--------------------------------------
string binaryOf(unsigned long long x){
string ans = "";
if (x ==0) return "0";
while(x>0){
int bit = x%2;
x = x/2;
ans = char('0'+bit) + ans;
}
return ans;
}
//--------------------------------------
unsigned long long countResult(unsigned long long X){
// count the number of (numbers that are less than X) and (their bit-sums are fibonacci)
string bin = binaryOf(X);
int n = bin.length();
unsigned long long ans = 0;
for(int k = 0; k<nFibo; k++){// for each fibo number:
if (n<Fibo[k]) break;
int remainBits = Fibo[k];
for(int i = 0; i<n; i++){// for each bit
if (remainBits <0) break;
int remainLen = n - i-1;
if (bin[i] == '1'){
ans += NCR_Of(remainLen, remainBits); //number of answers if turn this bit off.
remainBits--; //
}
}; // for i
}; //for k
return ans;
}
// My Solution:
//--------------------------------------
unsigned long long solve(unsigned long long a, unsigned long long b){
if (a>b) return 0;
return countResult(b+1) - countResult(a);
}
// Naive solution: loop and count:
//--------------------------------------
int sumBits(long x){
string b = binaryOf(x);
int res = 0;
for (int i = 0; i<b.length(); i++)
res += b[i]=='1'?1:0;
return res;
}
//--------------------------------------
bool isFibo(int x){
for(int i = 0; i<nFibo; i++)
if (Fibo[i] == x) return true;
return false;
}
//--------------------------------------
long solve_Naive(long a, long b){
long res = 0;
for(long i =a; i<=b; i++){
int s = sumBits(i);
if (isFibo(s)) res++;
};
return res;
}
//--------------------------------------
int main()
{
PascalTriangle(65);
cin >>a>>b;
cout <<"answer by MY solution = " <<solve(a,b)<<endl;
cout <<"answer by Naive solution = " <<solve_Naive(a,b)<<endl;
return 0;
}
If each row of the input matrix has at least one 1 already, then I will output the whole matrix as the answer, since it is the largest submatrix satisfied the constraint.
If there are rows that have zero number of 1: I "slice" the matrix by these zero rows, and find the answer among the resulting sliced submatrices.
Does it answer the question?
This is a duplicated question with 5433150784143360
I had an O(logn) algorithm, posted in the original question.
Let X be the median of the first list, Y be the median of the second list. We can find X, Y in O(1) time, since lists are SORTED.
L1 = {-------X-------}
L2 = {-------Y-------}
We have: numbers in the left of X (or Y) are not bigger than X (or Y); and the number in the right of X (or Y) are not smaller than X (or Y).
So, if X == Y we can conclude that the median should be equal to X.
If X < Y, the median cannot be in the left of X, and cannot be in the right of Y. Thus we can eliminate the left side of X and right side of Y, and recursively do for two remaining lists.
If X > Y, we eliminate the right side of X and left side of Y, and recursively do for two remaining lists.
We can stop when each list remains no more than 2 numbers, and find the median separately, in constant time. (I chose 2 to avoid boundary cases, you can choose 1 if you want).
This WORKs because each time we eliminate the same number of elements in right side and in left side, thus makes sure that the median always stays in the remaining lists.
This takes O(logn) because each time we eliminate half of the numbers...
Pseudo code may look like:
findMedian(st1, ed1, st2, ed2):
{
if (ed1-st1 <=2 ) return find_Median_By_Hand(st1, ed1, st2, ed2);
mid1 = (st1+ed1)/2;
X = L1[mid1];
mid1 = (st2+ed2)/2;
Y = L2[mid2];
if (X==Y) return X;
else
if (X>Y) return findMedian(st1, mid1, mid2, ed2);
else
if (X<Y) return findMedian(mid1, ed1, st2, mid2);
}
The answer is:
res = findMedian (0, n, 0, n);
Good question, Shrima!
For negative numbers, we need to change the DP formula. Obviously we can ignore the negative numbers, since they reduce the sum.
Define the optimization function:
S[k] = the maximum sum of the satisfied sub-sequence for the input array from A[0] to A[k];
Initial values:
S[0] = max (A[0], 0);
S[1] = max (A[1], S[0]);
Recursive formula:
For k>=2:
S[k] = S[k-1], if A[k] <=0; //i.e.: ignore A[k]
S[k] = max(A[k] + S[k-2], S[k-1]) , if A[k]>0 //i.e.: consider whether picking A[k] gives better sum.
From the definition of S[k], we can infer that:
S[u] >= S[u-1], for all u;
Thus, the recursive formula can be deduced to
S[k] = max( A[k] + S[k-2], S[k-1]);
The answer will be
ans = S[n];
To print out the sequence, we need to find out which position is picked in order to get the maximum sum. This can be done back-ward basing on the S[k] formula.
- ninhnnsoc April 29, 2014Follow the link oeis.org/A006886 you will find the definition:
Kaprekar numbers: n such that:
n=q+r and n^2=q*10^m+r,
for some m >= 1, q>=0 and 0<=r<10^m,
with n != 10^a, a>=1
For example: n = 297 is a Kaprekar because (q = 88, m = 3, r = 209)
297^2 = 88209 = 88*10^3 + 209
and
297 = 88 + 209;
First 10 Kaprekar numbers are:
1, 9, 45, 55, 99, 297, 703, 999, 2223, 2728
I can prove that if n is a Kaprekar number then n % 9 is either 0 or 1, as follow:
Let k = n % 9. Then (n^2) % 9 == (k^2) % 9;
Since n^2 =q*10^m+r, for some m >= 1, q>=0 and 0<=r<10^m, we have
(k^2) % 9 = (n^2) % 9
= (q*10^m+r) % 9
= (q%9 * 10^m % 9 + r%9) %9
= (q%9 + r%9) % 9
= (q+r) %9
= n%9
= k
Thus: (k^2) % 9 = k
This happens only with k = 0 or 1.
Thus, if n is a Kaprekar number, then n%9 will be either 0 or 1.
Interesting!
Let X be a Kaprekar number. Let s(X) = sum of digits of X, recursively.
For example,
s(9) = 9;
s(703) = s(7+0+3) = s(10) = s(1+0) = 1; ...
I found that for all Kaprekar number X from 1 to 10^51, s(X) is either 1 or 9.
It means that (X % 9) will be 1 or 0.
This will speed up your search significantly!
suppose your init values are:
S[0] = a[0];
S[1] = a[1]; (?)
Let calculate S[] by your formula for this input: 9,2,1,8:
S[0] = 9;
S[1] = 2; (?)
S[2] = max(S[0] + 1, S[1]) = max(9 + 1, 2) = 10. Good!
S[3] = max(S[1] + 8, S[2]) = max(2 + 8,10) = 10, Not good!
Your formula is correct or not depends on how you define the meaning of S[k], and the initiated values.
(In my definition above, I force the subsequence must be ending at k, it's easier for logic and for printing out subsequence later).
You will correct if you define S[k] as the maximum sum of the satisfied subsequence of the array a[0] .. a[k], where the subsequence may or may not ending at k.
And the init value should be:
S[0] = a[0];
S[1] = max(a[0], a[1]); (!)
Recursive formula can be:
S[k] = max(S[k-1], S[k-2] + a[k]), for k>=2;
The answer will be:
ans = S[n];
However, it's a little bit more complicated for printing out the subsequence.
DP O(n) solution:
Let S[k] = maximum sum of the subsequence that: (1) finishes at position k, and (2) satisfies the constraint.
Init values:
S[0] = arr[0];
S[1] = arr[1];
S[2] = arr[2] + arr[0];
Recursive formula:
S[k] = arr[k] + max(S[k-2], S[k-3]), for k >=3;
Note: we don't need to care about S[k-4], since if it is in optimal solution, it must be included in S[k-2] already.
The answer is
ans = max (S[n], S[n-1], S[n-2]);
DP table can be computed in O(n) time.
To print the subsequence, we need to record the position where the maximum is achieved, using an array Prev[], like this:
S[k] = arr[k] + max(S[k-2], S[k-3]);
Prev[k] = (S[k-2] > S[k-3] ? k-2 : k-3);
I don't really understand the question, but I think it can be done using graph theory.
That is, model the relationship between spreadsheet cells by a directed graph. Then, a "recursive formula" must correspond to a circle in that graph, and vice versa.
Detecting circles in a directed graph is not a complicated problem.
For the maximum product CONTINUOUS SUBSEQUENCE problem: it's little bit more complicated.
We can do it by DP:
Let define two arrays Ne[] and Po[] as follow:
Ne[i] = minimum negative product of continuous subsequence that finishes at i-th number;
Po[i] = maximum positive product of continuous subsequence that finishes at i-th number;
Initial values:
Ne[0] = min(-1,arr[0]);
Po[0] = max(1,arr[0]);
Recursive formula:
Ne[i] = min ( arr[i], arr[i] * Po[i-1], arr[i] * Ne[i-1]);
Po[i] = max ( arr[i], arr[i] * Po[i-1], arr[i] * Ne[i-1]);
The answer is
res = max(Po[i]);
To avoid integer representation overflow when multiplying, we can store the (+,-) sign separately, and working on logarithmic values of positive numbers only, with note: log (a*b) = log a + log b;
Please correct me if I am wrong, thanks!
1. To find maximum sum SUBSET: eliminate all negative integers, keep only positive ones. If all numbers are negative, choose the empty subset.
2. To find maximum sum of continuous subsequence: keep summing up numbers and record maximum sum. If the sum is negative, reset it to be 0.
sum = 0;
maxSum = 0;
for i = 1..n
sum += array[i];
maxSum = max (maxSum, sum);
if (sum<=0) sum = 0;
My O(logn) solution:
Let X be the median of the first list, Y be the median of the second list. We can find X, Y in O(1) time, since lists are SORTED.
L1 = {-------X-------}
L2 = {-------Y-------}
We have: numbers in the left of X (or Y) are not bigger than X (or Y); and the number in the right of X (or Y) are not smaller than X (or Y).
So, if X == Y we can conclude that the median should be equal to X.
If X < Y, the median cannot be in the left of X, and cannot be in the right of Y. Thus we can eliminate the left side of X and right side of Y, and recursively do for two remaining lists.
If X > Y, we eliminate the right side of X and left side of Y, and recursively do for two remaining lists.
We can stop when each list remains no more than 2 numbers, and find the median separately, in constant time. (I chose 2 to avoid boundary cases, you can choose 1 if you want).
This WORKs because each time we eliminate the same number of elements in right side and in left side, thus makes sure that the median always stays in the remaining lists.
This takes O(logn) because each time we eliminate half of the numbers...
Pseudo code may look like:
findMedian(st1, ed1, st2, ed2):
{
if (ed1-st1 <=2 ) return find_Median_By_Hand(st1, ed1, st2, ed2);
mid1 = (st1+ed1)/2;
X = L1[mid1];
mid1 = (st2+ed2)/2;
Y = L2[mid2];
if (X==Y) return X;
else
if (X>Y) return findMedian(st1, mid1, mid2, ed2);
else
if (X<Y) return findMedian(mid1, ed1, st2, mid2);
}
The answer is:
res = findMedian (0, n, 0, n);
Can I re-formulate the question as follow?
Question:
Given two numbers a,b, where a > b >= 1. Find the quotient n = a/b
without using the division operator, in log(n) time, with a precision of
k digits after the decimal point.
This can be done by GALLOP SEARCH:
First, init the quotient q as 1 then do repeated doubling until it overshoots the target quotient.
q = 1;
while (q*b < a) q *=2;
After this, we know the quotient is in between the range [q/2,q]
Now do binary search on this range [q/2,q]:
binSearch(a,b, st, ed):
mid = (st+ed)/2;
while(st < ed-1){
mid = (st+ed)/2;
if (mid *a <b){
st = mid;
} else ed = mid;
}
return mid;
The integer part of the quotient is:
intPart = binSearch(a, b, q/2, q);
The remainder is:
remain = b - intPart*a;
To find the k digits after decimal point, we k-time iteratively multiply the remain by 10, and do binary search in range [0,9];
for i = 1..k
remain *=10;
D[i]= binSearch(remain, b, 0, 9);
remain = b - a*D[i];
The final quotient is composed of the intPart and k digits after decimal point stored in array D.
Complexity: O(log n) + O( k*log(10) )
A follow up question may be:
The binary matrix is very big and it's stored in a file, with N = 2*10^6 lines, and M = 5000 characters each line. You cannot use more than 64 KB of main memory to store data.
Find the longest sequence of 1's in column wise.
Any one?
An O(n) time, O(1) space solution:
Consider 3 consecutive numbers A(i), A(i+1), A(i+2)
Suppose A(i) and A(i+1) are in correct order.
If A(i+1) and A(i+2) are also in correct order, then continue doing for A(i+1), A(i+2), A(i+3);
If A(i+1) and A(i+2) are not in correct order, then swap A(i+1) and A(i+2). After swapping, A(i), A(i+2), A(i+1) must be all in correct order (can you check that ?). Then, continue doing for A(i+2), A(i+1), A(i+3)...
Initially, we can swap A(1) with the max of (A). Then A(1), A(2) will be in correct order.
This can work for NEGATIVE values:
#include <iostream>
using namespace std;
int main()
{
const int Nmax = 10;
int Arr[Nmax];
int n = 6; //size of input Arr;
Arr = {7, -3, 8, 4, 13,-5};
int S = 15;
int Sum = Arr[0];
int wR = 0, wL = 0;
int minSize = n+10;
while(true){// make sure that Arr[wL] and Arr[wR] are positive.
if (Sum<=0 and wR <n){
wR++;
wL = wR;
Sum = Arr[wR];
continue;
};
if (Sum <=S and wR<n){
wR++;
Sum += Arr[wR];
continue;
};
if (Sum>S){
minSize = min(minSize, wR-wL);
Sum -= Arr[wL];wL++;
while(Arr[wL] <=0 and wL < wR){
Sum -= Arr[wL];
wL++;
if (Sum>S){
minSize = min(minSize, wR-wL);
}
};
};
if (wR>=n) break;
};
if (minSize>n) cout <<"No solution"<<endl;
else cout <<"minimum sequence length is "<<minSize+1<<endl;
return 0;
}
How about this:
I try to expand the window to the right, but if at any position, say v, the sum become non-positive, I skip all the current window and start a NEW window at position v+1.
If the sum is > S:
I try to shrink the window by sliding the left side wL++ iteratively, to find the minimum size.
I have an idea, using SLIDING WINDOW: I use a "window" from index wL to wR to slide on the array, while keeping track of its sum and the minimum window size that satisfied sum > S.
While the sum of numbers inside the window is not greater than S, slide the right side (wR++). At any moment, while the sum is greater than S, record the minimum so far and then slide into the left side (wL++).
This takes O(n) since the window is always sliding into 1 direction (left to right), which stops at most O(n) steps.
This works for array with negative values as well.
O(n) time, O(1) space.
EDITED:
It doesn't work for negative values, AS WELL!
EDITED (2nd time): For negative values:
If the sum is <=0 at position v, then start new window at v+1;
If the sum is <=S: sliding the right side wR++;
If the sum is >S: try to shrink the left side to find the minimum size.
Please see my code below and tell if it doesn't work. Thanks!
great idea! +1
Here is an explanation for that:
(1). First look at an easier problem: Given a SORTED array, find 2 elements that sum up to some value, say S.
This can be done in O(n) using two pointer approach: using two pointers that point to the start (Pstart) and the end (Pend) of the sorted array.
Depends on whether the sum values of the two pointers is smaller of not smaller than S, we increase Pstart++ or decrease Pend--, respectively. This takes O(n) time, since the range is decreasing every step.
No extra space is needed.
(2). Now come back to the original problem with 3 elements:
First, sort the array. This takes O(n logn) with no extra space if using heap-sort.
For each element x in this array, do this sub-task: Find in the remaining SORTED array two elements that sum up to -x. This sub-task is done in O(n) as in (1).
Thus, the overall solution is O(n ^2) with no extra space.
Calculate the sums of any two numbers, and store them in an array of length O(n^2). This takes O(n*n).
Then for each element x in the original list, do a binary search for -x in the sum array. This takes O(n log(n^2)) = O(2nlogn) = O(nlogn).
Thus, the overall will take O(n^2).
EDITED: Above is wrong!
Should store the sums in a hash table, no binary search needed.
Rep
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
RepLoler, Employee at Google
RepNelson Perez, Software Engineer
Repaliciagreene771, Vashikaran mantra for get my love back at None
Hello! How are you,My name is Alicia Greene I am from London (UK). I am a Business English, Math ...
RepNoahTaylor, abc at A9
Accomplished software developer with many years of experience in development of applications. Excels in every stage of the life cycle ...
RepEarned praise for analyzing acne for the government. Earned praised for my work implementing mantra to get desired husband in ...
Replamisobbeya45, Student at None
Hello there, My name is Lamis Obbeya I am from Brooklyn, New York . I am 29 years of age. I ...
RepAugment is a mobile app that lets you and your customers visualize your 3D models in Augmented Reality. If you ...
RepNellieWheeler212, None at Service Now
Hey Everyone! My name is Nellie Wheeler and I live in the constantly radiant and wonderful San Francisco, CA, and ...
RepA real dynamo when it comes to buying and selling carnival rides in Fort Lauderdale, FL. Spend several years working ...
Repmorganweiler771, Employee at None
Hello Everyone, I am Morgan Weiler I am from Mumbai, (India).I enjoy Watching TV, playing guitar, Yoga and reading ...
RepAre you looking a solution for marry your love? Islamic dua to marry someone you love is the effective solution ...
RepPandit Ji is the best vashikaran expert for vashikaran mantra for girlfriend in Mumbai.It is the strongest method to ...
RepAre you looking for strong dua for husband love?Astrology is the perfect way to get your lost love back ...
RepAmber Van is registered and fully insured cheap removal company in Bristol.Our featured services includes domestic moves,commercial moves ...
Rep
RepAre you wasting time for to search a professional astrologer and specialist to get rid of black magic?Black Magic ...
Repaalvinbrowne, Android Engineer at ASAPInfosystemsPvtLtd
Working as an Agricultural laborer at Mars Music I maintain yields like natural products, vegetables, grains, and nuts, or take ...
RepLeonaDWilliams, Analyst at CCN
At the moment I'm building banjos in Deltona, FL. Once had a dream of analyzing easy-bake-ovens in Fort Walton ...
RepDo you want to marry with your desired person? The Islamic dua for marriage with a loved one has great ...
RepCeliaParker, teacher at Illinoisstate
Experienced teacher with a background in education who is looking to complement graduate studies with the opportunity to teach at ...
Nice answer!
- ninhnnsoc May 12, 2014You can do O(n) time sorting in this problem, using counting sort or bucket sort.
(The last sentence you wrote may be correct, but be careful with the notation: little-o vs. big-O ...)