1
\$\begingroup\$

Given an integer N(Natural Number), A program/Algorithm to find the remainder of arrangements that can be obtained by rearranging the numbers 1, 2, ...., N.

Input Format: One line containing the integer N

Output Format: An integer m, giving the remainder of the number of arrangements that could be obtained from 1, 2, ...., N is divide by Mod

Constraints:
Mod = 10^9+7
N ≤ 10^9

Example 1

Input
3
Output
2
Explanation:
Consider the first three natural numbers 1, 2, 3. These can be arranged in the following ways: 2, 3, 1 and 1, 3, 2. In both of these arrangements, the numbers increase to a certain point and then decrease. There are two such arrangements: 2, 3, 1 and 1, 3, 2.

Example 2

Input
4
Output
6
Explanation:
The six arrangements are (1, 2, 4, 3), (1,3,4,2), (1,4,3,2), (2,3,4,1), (2,4,3,1), (3,4,2,1).

#include<stdio.h>
#include<stdlib.h>
#define m 1000000007

unsigned long long int power(unsigned long long int x, unsigned long long int n){

    unsigned long long int res = 1;
    while(n > 0){
        if(n & 1){
            res = res * x;
            res = res%m;
        }
        x = x * x;
        x= x%m;
        n >>= 1;
    }
    return res;

}


int main(){

    unsigned long long int n,res=0,temp=1,i;
    scanf("%llu", &n);
    if(n==1 || n==0){
        printf("0\n");
        return 0;
    }
    temp = power(2, n-1);
    temp--;
    temp--;
    printf("%llu\n", temp);

    return 0;
}

Can Anyone Solve This with Better Time Complexity?

\$\endgroup\$
1
  • \$\begingroup\$ An explanation of the combinatorics behind the scenes would be most helpful. \$\endgroup\$
    – vnp
    Aug 4, 2017 at 6:27

1 Answer 1

-1
\$\begingroup\$

Bug

Input : 500000003
Output: 18446744073709551615

The problem is that the result of your power() call could be 0 or 1. Then when you subtract 2, you get a negative number. Given the input constaint of \$n ≤ 10^9\$, 500000003 is the only bad input, but in general this happens when n is any multiple of 500000003. To correct this, you could change this:

temp--;
temp--;

to:

temp = (temp + m - 2) % m;

This ensures that temp will remain positive. Time complexity wise, your program is great at \$O(\log n)\$.

\$\endgroup\$
5
  • \$\begingroup\$ It has to deal with only natural number then why to count 0 ? \$\endgroup\$ Aug 4, 2017 at 6:47
  • \$\begingroup\$ Why the answer is \$2^{n-1} - 2\$ is quite clear. I wanted OP to confirm that he knows that. You shouldn't interfere. I know that you know. Sorry. \$\endgroup\$
    – vnp
    Aug 4, 2017 at 6:51
  • \$\begingroup\$ @HimanshuRay Apparently you didn't really understand the problem so I removed my explanation. \$\endgroup\$
    – JS1
    Aug 4, 2017 at 8:25
  • \$\begingroup\$ @vnp I think you were right, judging from the above comment by OP. \$\endgroup\$
    – JS1
    Aug 4, 2017 at 8:26
  • \$\begingroup\$ my mistake @JS1 sorry. You can put back your Explanation. I will go through it once more. \$\endgroup\$ Aug 4, 2017 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.