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\$
  • \$\begingroup\$ An explanation of the combinatorics behind the scenes would be most helpful. \$\endgroup\$ – vnp Aug 4 '17 at 6:27
-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\$
  • \$\begingroup\$ It has to deal with only natural number then why to count 0 ? \$\endgroup\$ – Himanshu Ray Aug 4 '17 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 '17 at 6:51
  • \$\begingroup\$ @HimanshuRay Apparently you didn't really understand the problem so I removed my explanation. \$\endgroup\$ – JS1 Aug 4 '17 at 8:25
  • \$\begingroup\$ @vnp I think you were right, judging from the above comment by OP. \$\endgroup\$ – JS1 Aug 4 '17 at 8:26
  • \$\begingroup\$ my mistake @JS1 sorry. You can put back your Explanation. I will go through it once more. \$\endgroup\$ – Himanshu Ray Aug 4 '17 at 9:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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