I think I have an O(1) solution to this problem.
I think we can use the idea of summing the pairs of all the values which
are divisible by k.
The answer will have r+1 terms ( I define r below )
Term 1 : floor((k-1)/2) will give us the value of pairs who have sum k.
Term 2 : floor((2*k-1)/2) will give us the value of pairs who have sum 2*k.
...
...
...
Term r : floor((r*k-1)/2) will give us the value of pairs who have sum r*k.
where r is the maximum of all the numbers i such that i*k<=n
hence r = floor((n+1)/k)
the last term will contain the number of pairs who have sum (r+1)*k
Hence,
Term r+1 : floor((2*n-(r+1)*k+1)/2). (why?)
Now the only thing which remains is summing the r terms defined above.
I used the idea that floor(X/2) = (X-(X%2))/2
Case 1 : k is even. Then all the numerators in r terms are odd, and the
summation can be easily proved to be equal to ((r*(r+1)/2)*k - 2*r)/2.
Case 2 : k is odd. Then half(actually floor of half) the numerators in r
terms are odd, and the summation will be (r*(r+1)/2*k-r-floor(r/2))/2.
The final answer can be stated as :-
Even k : answer = ((r*(r+1)/2)*k - 2*r)/2 + floor((2*n-(r+1)*k+1)/2)
Odd k : answer = (r*(r+1)/2*k-r-floor(r/2))/2 + floor((2*n-(r+1)*k+1)/2)
where r = floor((n+1)/k).
Let me know if there is a flaw, or if you don't understand anything.
On Fri, Oct 18, 2013 at 7:15 AM, pankaj joshi <joshi10...@gmail.com> wrote:
> HI All,
>
> Puzzle: (This puzzle is of hacker rank)
>
> Harvey gives two numbers N and K and defines a set A.
>
> *A = { x : x is a natural
> number<https://en.wikipedia.org/wiki/Natural_number> ≤
> N }*
> (i.e), A = {1,2,3,4,5,6,…., N}
>
> Mike has to find the total number of pairs of elements A[i] and A[j]
> belonging to the given set such that i < j and their sum is divisible by K
>
>
> Solution:- (I am facing a problem of time exceed. can you tell me an
> optimize solution)
>
> the complexity of below solution is O(M*N) {M is numbers and N is Div}
>
> static long Occurances(int Number, int Div)
> {
> long retVal = 0;
> for (int i = 1; i <= Number; i++)
> {
> int cout = 1;
> int result = Div * cout - i;
> cout = (result > 0) ? cout : i / Div;
> result = Div * cout - i;
> while (result <= Number)
> {
> if (result > i)
> {
> retVal++;
> }
> else
> {
> cout = 2 * i / Div;
> }
> cout++;
> result = Div * cout - i;
> }
> }
> return retVal;
> }
>
> Test conditions are, so take care of space also.
> K<=N<=109
> 1<=K<=10000
>
> Regards,
>
> Pankaj Kumar Joshi
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
- Saurabh Paliwal
B-Tech. Comp. Science and Engg.
IIT ROORKEE
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
