Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Lucky Number CodeChef Solution
Problem -Lucky Number CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Lucky Number CodeChef Solution in C++14
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod=1e9+7;
int dp[1001][1001][2],C[1001][1001],fact[1001];
vector<int>v={4,7,44,47,74,77,444,447,474,477,744,747,774,777};
int power(int a,int b){
int res=1;
while(b){
if(b&1){
res=(res*a)%mod;
}
a=(a*a)%mod;
b/=2;
}
return res;
}
int c(int len,int cnt){
int res=0;
for(auto x:v){
int target=x-cnt;
if(target<0 or target>len){
continue;
}
res=(res+((C[len][target]*power(2,target))%mod)*power(8,len-target))%mod;
}
return res;
}
int calc(string &s,int idx,int cnt,int tight){
if(idx==s.size()){
if(find(v.begin(),v.end(),cnt)!=v.end()){
return 1;
}
return 0;
}
if(dp[idx][cnt][tight]!=-1){
return dp[idx][cnt][tight];
}
if(tight==0){
return dp[idx][cnt][tight]=c(s.size()-idx,cnt);
}
int ub=(tight)?(s[idx]-'0'):9;
int ans=0;
for(int i=0;i<=ub;i++){
if(i==4 or i==7){
ans+=calc(s,idx+1,cnt+1,tight&(i==ub));
}
else{
ans+=calc(s,idx+1,cnt,tight&(i==ub));
}
ans%=mod;
}
return dp[idx][cnt][tight]=ans;
}
void solve(){
string l,r;
cin>>l>>r;
memset(dp,-1,sizeof(dp));
int ans_l=calc(l,0,0,1);
memset(dp,-1,sizeof(dp));
int ans_r=calc(r,0,0,1);
int cnt=0;
for(auto x:l){
if(x=='4' or x=='7'){
cnt++;
}
}
if(find(v.begin(),v.end(),cnt)!=v.end()){
ans_r++;
}
cout<<((ans_r-ans_l)%mod+mod)%mod<<"\n";
}
int32_t main(){
int t;
cin>>t;
memset(C,0,sizeof(C));
C[0][0]=1;
fact[0]=1;
for(int i=1;i<=1000;i++){
fact[i]=(fact[i-1]*i)%mod;
}
for(int i=1;i<=1000;i++){
for(int j=0;j<=i;j++){
C[i][j]=(C[i-1][j]+((j-1>=0)?C[i-1][j-1]:0))%mod;
}
}
while(t--){
solve();
}
}Lucky Number CodeChef Solution in PYTH 3
# cook your dish here
# cook your dish here
lucky = {4, 774, 7, 744, 777, 74, 747, 44, 77, 47, 474, 444, 477, 447}
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7
fact = [1]
for i in range(1, 1001):
fact.append(fact[-1] * i % mod)
inv = [pow(i, mod-2, mod) for i in fact]
C = lambda k, n: fact[n] * inv[n-k] * inv[k] % mod
def f(n):
n = [int(x) for x in n]
@lru_cache(None)
def dp(pos, cnt, free):
if cnt > 777:
return 0
diff = len(n) - pos
ans = 0
if free:
for i in lucky:
i -= cnt
if 0 <= i <= diff:
ans += C(i, diff) * pow(2, i, mod) * pow(8, diff - i, mod)
ans %= mod
return ans
if pos == len(n):
return int(cnt in lucky)
for i in range(10 if free else n[pos]+1):
ans += dp(pos+1, cnt + int(i == 4 or i == 7), free or i < n[pos])
ans %= mod
return ans
return dp(0, 0, 0)
t = int(input())
for _ in range(t):
l, r = input().split()
l = str(int(l) -1)
print ((f(r) - f(l)) % mod)Lucky Number CodeChef Solution in C
#include<stdio.h>
#include<string.h>
char s[10001];
int pow2[1001];
int pow8[1001];
int comb[1001][1001];
int ac[14]={4,7,44,47,74,77,444,447,474,477,744,747,774,777};
int b=1000000007;
int cf(int k,int w,int cnt)
{
int v,q=0,i,ret=0;;
if(k>4) q++;
if(k>7) q++;
if(q>0)
{
for(i=0;i<14;i++)
if((w+cnt)>=ac[i])
{
if(ac[i]>cnt)
{
v=comb[w-1][ac[i]-cnt-1];
v=((long long)v*q)%b;
v=(v*(long long)pow2[ac[i]-cnt-1])%b;
v=(v*(long long)pow8[w+cnt-ac[i]])%b;
ret=(ret+v)%b;
}
}
else break;
k=k-q;
}
for(i=0;i<14;i++)
if((w+cnt)>ac[i])
{
if(ac[i]>=cnt)
{
v=comb[w-1][ac[i]-cnt];
v=((long long)v*k)%b;
v=(v*(long long)pow2[ac[i]-cnt])%b;
v=(v*(long long)pow8[w+cnt-ac[i]-1])%b;
ret=(ret+v)%b;
}
}
else
break;
return ret;
}
int main()
{
int cnt,len,i,j,v,t,k,tc;
pow2[0]=1;pow8[0]=1;
for(i=1;i<1001;i++)
{
pow2[i]=((long long)pow2[i-1]*2)%b;
pow8[i]=((long long)pow8[i-1]*8)%b;
}
for ( i = 0; i <1001; i++) {
comb[i][0] = 1;
for (j = 1; j <= i; j++)
comb[i][j] = (comb[i-1][j] + comb[i-1][j-1]) %b;
}
scanf("%d",&t);
while(t--)
{
tc=2;
v=0;
while(tc--)
{
k=v;
scanf("%s",s);
len=strlen(s);
cnt=0;
v=0;
for(i=0;i<len;i++)
{
v=(v+cf(s[i]-'0',len-i,cnt))%b;
if(s[i]=='7'||s[i]=='4') cnt++;
}
}
for(i=0;i<14;i++)
if(cnt==ac[i]) v=(v+1)%b;
printf("%d\n",(b+v-k)%b);
}
return 0;
}Lucky Number CodeChef Solution in JAVA
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.StringTokenizer;
public class Main {
static int MOD = 1000000007;
static long pow2[];
static long pow8[];
static long fa[] = new long[2001];
static long fb[] = new long[2001];
static long[] powers(int base) {
long a[] = new long[2001];
for (int i = 0; i < 2001; i++) {
if (i == 0) {
a[i] = 1;
} else {
a[i] = a[i-1] * base;
a[i] %= MOD;
}
}
return a;
}
static int luckyNumbers[] = { 4, 7, 44, 47, 74, 77, 444, 447, 474, 477,
744, 747, 774, 777 };
public static void main(String[] args) throws NumberFormatException,
IOException {
FastScanner in = new FastScanner(System.in);
int cases = in.fastNextInt();
long ans;
StringBuilder output = new StringBuilder();
while (cases-- > 0) {
ans = 0;
String L = in.next();
String R = in.next();
StringBuilder sb = new StringBuilder(L);
if (sb.charAt(sb.length() - 1) > '0'
&& sb.charAt(sb.length() - 1) <= '9') {
sb.setCharAt(sb.length() - 1,
(char) (sb.charAt(sb.length() - 1) - 1));
} else {
int i = sb.length() - 1;
while (i >= 0 && sb.charAt(i) == '0') {
sb.setCharAt(i, '9');
i--;
}
if (sb.charAt(i) == '1' && i == 0) {
sb.deleteCharAt(i);
} else {
sb.setCharAt(i, (char) (sb.charAt(i) - 1));
}
}
L = sb.toString().trim();
ans = solve(R) - solve(L);
if (ans < 0) {
ans = (ans + MOD) % MOD;
}
output.append(ans + "\n");
}
System.out.println(output);
// long end = System.currentTimeMillis();
// System.out.println(end-start);
}
static class FastScanner {
BufferedReader br;
StringTokenizer st;
IOException happened;
public FastScanner(InputStream is) {
br = new BufferedReader(new InputStreamReader(is));
}
public String next() {
while (st == null || !st.hasMoreTokens()) {
try {
String line = br.readLine();
st = new StringTokenizer(line);
} catch (IOException e) {
happened = e;
return null;
}
}
return st.nextToken();
}
public int fastNextInt() {
try {
int c = br.read();
while (c <= 32 && c >= 0) {
c = br.read();
}
if (c == -1) {
return Integer.MIN_VALUE;
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = br.read();
}
if (c < '0' || c > '9') {
throw new NumberFormatException("digit expected "
+ (char) c + " found");
}
int ret = 0;
while (c >= '0' && c <= '9') {
ret = ret * 10 + c - '0';
c = br.read();
}
if (c > 32) {
throw new NumberFormatException("space character expected "
+ (char) c + " found");
}
return ret * sgn;
} catch (IOException e) {
return Integer.MIN_VALUE;
}
}
public int nextInt() {
return Integer.parseInt(next());
}
}
static class FastPrinter extends PrintWriter {
public FastPrinter(OutputStream out) {
super(out);
}
public FastPrinter(Writer out) {
super(out);
}
}
static long solve(String input) {
int len = input.length();
int num;
if (len < 4) {
return 0;
} else if (len == 4) {
num = Integer.parseInt(input);
if (num < 4444) {
return 0;
}
}
long ans = 0;
int cnt47 = 0;
for (int i = 0; i < luckyNumbers.length; i++) {
cnt47 = 0;
if (len < luckyNumbers[i]) {
break;
}
int m;
long p;
int ia, ib;
for (int j = 0; j < len; j++) {
m = input.charAt(j) - '0';
p = 0;
if (m > 0) {
ia = luckyNumbers[i] - cnt47;
ib = len - 1 - j - (luckyNumbers[i] - cnt47);
if (ia >= 0
&& ib >= 0) {
p = pow2[ia];
p *= C(ia+ib, ia);
p%=MOD;
p *= pow8[ib];
p%=MOD;
}
}
if (m == 4 || m == 7) {
if (m == 4) {
p *= 4;
p %= MOD;
ans += p;
ans %= MOD;
} else {
p *= 6;
p %= MOD;
ans += p;
ans %= MOD;
ia = luckyNumbers[i] - 1 - cnt47;
ib = len - 1 - j - (luckyNumbers[i] - 1 - cnt47);
if (ia >= 0
&& ib >= 0) {
p = pow2[ia];
p *= C(ia+ib, ia);
p%=MOD;
p *= pow8[ib];
p%=MOD;
ans += p;
ans %= MOD;
}
}
cnt47++;
} else if (m < 4) {
p *= m;
p %= MOD;
ans += p;
ans %= MOD;
} else if (m > 4 && m < 7) {
p *= (m - 1);
p %= MOD;
ans += p;
ans %= MOD;
ia = luckyNumbers[i] - 1 - cnt47;
ib = len - 1 - j - (luckyNumbers[i] - 1 - cnt47);if (ia >= 0
&& ib >= 0) {
p = pow2[ia];
p *= C(ia+ib, ia);
p%=MOD;
p *= pow8[ib];
p%=MOD;
ans += p;
ans %= MOD;
}
} else if (m > 7) {
p *= (m - 2);
p %= MOD;
ans += p;
ans %= MOD;
ia = luckyNumbers[i] - 1 - cnt47;
ib = len - 1 - j - (luckyNumbers[i] - 1 - cnt47);
p = 0;
if (ia >= 0
&& ib >= 0) {
p = pow2[ia];
p *= C(ia+ib, ia);
p%=MOD;
p *= pow8[ib];
p%=MOD;
}
p *= 2;
p %= MOD;
ans += p;
ans %= MOD;
}
}
if (cnt47 == luckyNumbers[i]) {
ans += 1;
ans %= MOD;
}
ans %= MOD;
}
return ans;
}
static long C(int a, int b) {
if (b > a)
return 0L;
if (b < 0)
return 0L;
long res = fa[a];
res *= fb[b];
res %= MOD;
res *= fb[a - b];
res %= MOD;
return res;
}
static long calc(long x, long y) {
long ans = 1;
long temp = x;
while (y > 0) {
if (y % 2 == 1) {
ans = (temp % MOD) * (ans % MOD);
ans %= MOD;
}
temp = (temp % MOD) * (temp % MOD);
temp %= MOD;
y = y / 2;
}
return ans % MOD;
}
static {
pow2 = powers(2);
pow8 = powers(8);
fa[0] = 1;
for (int i = 1; i < fa.length; i++) {
fa[i] = i * fa[i - 1];
fa[i] %= MOD;
}
fb[fb.length - 1] = calc(fa[fb.length - 1], MOD - 2);
for (int i = fb.length - 1; i > 0; i--) {
fb[i - 1] = i * fb[i] % MOD;
}
}
}Lucky Number CodeChef Solution in PYPY 3
lucky = {4, 774, 7, 744, 777, 74, 747, 44, 77, 47, 474, 444, 477, 447}
from functools import lru_cache
import sys
sys.setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7
fact = [1]
for i in range(1, 1001):
fact.append(fact[-1] * i % mod)
inv = [pow(i, mod-2, mod) for i in fact]
C = lambda k, n: fact[n] * inv[n-k] * inv[k] % mod
def f(n):
n = [int(x) for x in n]
@lru_cache(None)
def dp(pos, cnt, free):
if cnt > 777:
return 0
diff = len(n) - pos
ans = 0
if free:
for i in lucky:
i -= cnt
if 0 <= i <= diff:
ans += C(i, diff) * pow(2, i, mod) * pow(8, diff - i, mod)
ans %= mod
return ans
if pos == len(n):
return int(cnt in lucky)
for i in range(10 if free else n[pos]+1):
ans += dp(pos+1, cnt + int(i == 4 or i == 7), free or i < n[pos])
ans %= mod
return ans
return dp(0, 0, 0)
t = int(input())
for _ in range(t):
l, r = input().split()
l = str(int(l) -1)
print ((f(r) - f(l)) % mod)Lucky Number CodeChef Solution in PYTH
lucky = {4, 774, 7, 744, 777, 74, 747, 44, 77, 47, 474, 444, 477, 447}
import sys
sys.setrecursionlimit(10 ** 6)
mod = 10 ** 9 + 7
fact = [1]
for i in range(1, 1001):
fact.append(fact[-1] * i % mod)
inv = [pow(i, mod-2, mod) for i in fact]
C = lambda k, n: fact[n] * inv[n-k] * inv[k] % mod
def f(n):
n = [int(x) for x in n]
memo = {}
def dp(pos, cnt, free):
if cnt > 777:
return 0
diff = len(n) - pos
ans = 0
if (pos, cnt, free) in memo:
return memo[pos, cnt, free]
if free:
for i in lucky:
i -= cnt
if 0 <= i <= diff:
ans += C(i, diff) * pow(2, i, mod) * pow(8, diff - i, mod)
ans %= mod
memo[pos, cnt, free] = ans
return ans
if pos == len(n):
return int(cnt in lucky)
for i in range(10 if free else n[pos]+1):
ans += dp(pos+1, cnt + int(i == 4 or i == 7), free or i < n[pos])
ans %= mod
memo[pos, cnt, free] = ans
return ans
return dp(0, 0, 0)
t = int(input())
for _ in range(t):
l, r = raw_input().split()
l = str(int(l) -1)
print ((f(r) - f(l)) % mod)Lucky Number CodeChef Solution Review:
In our experience, we suggest you solve this Lucky Number CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Lucky Number CodeChef Solution.
Conclusion:
I hope this Lucky Number CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
