Header Ads Widget

Reduce to One | Codechef solution

Rajnish Tripathi 21:37

 Problem:-

You have become good friends with Chef. Right now, Chef is busy in the kitchen, so he asked you to solve a problem for him.

Consider a list of integers �. Initially, � contains the integers 1 through �, each of them exactly once (but it may contain multiple copies of some integers later). The order of elements in � is not important. You should perform the following operation �−1 times:

  • Choose two elements of the list, let's denote them by � and �. These two elements may be equal.
  • Erase the chosen elements from �.
  • Append the number �+�+�⋅� to �.

At the end, � contains exactly one integer. Find the maximum possible value of this integer. Since the answer may be large, compute it modulo 1,000,000,007 (109+7).

Input

  • The first line of the input contains a single integer � denoting the number of test cases. The description of � test cases follows.
  • The first and only line of each test case contains a single integer �.

Output

For each test case, print a single line containing one integer ― the maximum possible value of the final number in the list modulo 109+7.

Constraints

  • 1≤�≤100,000
  • 1≤�≤1,000,000

Subtasks

Subtask #1 (20 points): 1≤�,�≤25

Subtask #2 (80 points): original constraints

Sample 1:

Input
Output
3
1
2
4
1
5
119

Explanation:

Example case 1: �=[1]

Example case 2: �=[1,2]→[1+2+1⋅2]

Example case 3: �=[1,2,3,4]→[2,3,9]→[3,29]→[119]. The chosen elements in each step are in bold.

Code(C++):-

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007

int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
long t;
cin >> t;
ll a[1000001];
for(int i=1;i<1000001;i++){
a[i]=(a[i-1]+i+(i*a[i-1]))%mod;
}
while (t--){
ll n;
cin>>n;
cout<<a[n]<< "\n";
}
return 0;
}

Code(JAVA):-

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class rtr {
public static int gcf(int a, int b) {
if (b == 0)
return a;
return gcf(b, a % b);
}

public static int lcm(int a, int b) {
return (a * b) / gcf(a, b);
}

public static void main(String[] args) throws java.lang.Exception {
// your code goes here
Scanner input = new Scanner(System.in);
int test = input.nextInt();
long a[]=new long[1000_0001];
int i;
long m=1000_000_007;
for(i=1;i<a.length;i++)
{
a[i]=(a[i-1]+i+(i*a[i-1]))%m;
}
while (test > 0) {
int n = input.nextInt();
System.out.println(a[n]%m);
test--;
}
}
}

Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments