×

# include<stdio.h>

int main() { char a[10000],b[10000];

int t;

scanf("%d",&t);
while(t>0)


{ int flag=0;

scanf("%s",&a);
scanf("%s",&b);
for(int i=0;i<strlen(a);i++)
{
for(int j=0;j<strlen(b);j++)
{
if(a[i]==b[j]){
flag++;
b[j]='1';
break;
}
}
}
printf("%d",flag);

t--;


}

}

1★k1k1313
1014
accept rate: 0%

19.8k350498541

### The question has been closed for the following reason "Duplicate Question" by admin 23 Jun '14, 22:10

 2 First of all, always remember that strlen() function is an O(n) function to calculate the length of a string. So, doing "for(i=0;i< strlen(a);i++)" makes the loop O(n^2) instead of O(n). Your two for loops were therefore performing O(n^4) to calculate the answer. Now t is 100 and n is 1000 so that makes your solution O(tn^4) which is not possible to run in 1 sec. Even making an O(tn^2) solution would give a TLE as it will be 10^10 which cannot be run in 1 sec. The correct approach to the question is hashing. Have a look at this. It is the accepted version of your code. answered 04 May '14, 00:02 4★roman28 1.6k●7●14●29 accept rate: 19% how cn u calculate the program for in 1 sec or not,is just ur experience in the codechef or there is any sort of calculation regarding this,,,i undrstnd ur complexity bt cn u explain how does u calculate it for running in 1 sec or not (05 May '14, 16:50) k1k13131★ Its definitely experience. :) Most of the time it will work if your algorithm is not naive. The most basic approach is rarely the solution. (I am sorry i commented for roman28) (05 May '14, 21:40)
 1 Use Hashing bro. Basically using array indexes for fast access. answered 04 May '14, 00:18 255●1●3 accept rate: 15%
 0 Request you to continue the discussion on the editorial page of the problem. Closing this question as of now. answered 23 Jun '14, 22:10 0★admin ♦♦ 19.8k●350●498●541 accept rate: 36%

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,716
×717
×20
×19

question asked: 03 May '14, 18:47

question was seen: 935 times

last updated: 23 Jun '14, 22:10