Directi Interview Question
Software Engineer / DevelopersCountry: India
add a condition when more than one number map to same value..
for ex->
123,132,213,231,312,321
@Abhishek yeah!I should add res += (cnt[j]*(cnt[j]-1))/2 before the second loop. thank you for your correcting.
Hey @notbad,really good implementation ..but one bug if a no. is repeated again like
123,132,213,231,312,321,321
It should give 15 but its giving 21,dat means its treating last 321 as a separate number. Provide corrected code asap .
@bond I'm not quite sure how to process duplicate numbers.If the duplicate numbers can only be counted once,we should sort the numbers first and uniq them. If we should count every number no matter whether they are the same or not, the code above is Okay.Off course, promising no duplicate numbers will be appreciated.
Represent each digit of a number with a bit.
Compare bit-representation of each number with the bit-representation every other number
struct bit
{
unsigned int num:10;
};
void find(int* a,int size)
{
struct bit b[size];
int i,num,j,count=0;
for(i=0;i<size;i++) b[i].num=0;
for(i=0;i<size;i++)
{
num=a[i];
while(num)
{
b[i].num|=1<<(num%10);
num/=10;
}
}
for(i=0;i<size;i++)
{
for(j=i+1;j<size;j++)
{
if(b[i].num&b[j].num)
count++;
}
}
printf("%d ",count);
}
Complete code here: ideone.com/nEeTG
I don't know if this would meet the requirements of this problem or not. An n^2 solution is likely to time out given the constraints. You have, however, really done some good preprocessing to make sure that the n^2 step has a really small constant factor. Maybe this solution would scrape by.
Create an array of size 10 to count the distinct appearance of digits in a given number ... While taking the input number increase the value by 1 in the array for the corresponding digit...
for e.g. if the input number is 9788 increase the count of 7,8,9th position in array by 1.
Final answer 'll be :
count=0;
for(i=0;i<10;i++)
count += arr[i]-1;
Number of comparisons = No of comparisons in insertion sort
while comparing two elements
1. create an array of size 10 and intialize to zero ..
2. take the first element and traverse its digits (using modulo) and set the array[digit] to 1
3. when you traverse the second element's digits and if you found array[digit] to 1 then these two elements are friends..
is my solution right?
Here's something complicated, but its O(N):
Construct 10 buckets (LinkedLists) where bucket i contains all numbers which contain digit i. This step is Space: O(N), time O(N).
Let us call the answer "count".
Now, for bucket i, i varies from 0 to 9:
Add bucket[i].size()*(bucket[i].size()-1)/2 to count. This is for the number of friendly pairs, which are friendly because they contain digit i. Now we need to remove pairs which have been counted earlier because they were friendly due to some digit j < i.
Create an array C[] of size i where C[j] denotes the count of numbers in this bucket (bucket[i]) whose MINIMUM digit is j.
Subtract C[j]*(C[j]-1)/2 from count, j varies from 0 to i-1.
Return count.
Its O(N) time and space.
Can you please explain this line- "Create an array C[] of size i where C[j] denotes the count of numbers in this bucket (bucket[i]) whose MINIMUM digit is j. "?
void findFriendlyNumsCount(int[] setOfNumbers){
int[] digitsCount = new int[10];
int friendlyNumCount = 0;
for(int i=0; i<setOfNumbers.length; i++){
int temp = setOfNumbers[i];
int[] countChecker = new int[10];
while(temp>0){
int oldCount = digitsCount[temp%10];
digitsCount[temp%10] = digitsCount[temp%10]+1;
int newCount = digitsCount[temp%10];
if(oldCount > 0 && newCount > oldCount && countChecker[temp%10] == 0){
friendlyNumCount = friendlyNumCount+1;
countChecker[temp%10] = 1;
//break;
}
temp = temp/10;
}
}
System.out.println(friendlyNumCount);
}
for each digit from 0 to 9, I compute the number of pairs as following : for digit i, I calculate 2 numbers : - nrused ( number of values that contains digit i, but also contain digits that are smaller than i, those are numbers that have allready been used )
- and nr_not_used ( number of values that contains digit i and doesn't contain digits smaller than i, number that haven't been used ).
now we add to the solution : nrused * nr_not_used + nr_not_used*(nr_not_used-1)/2 .
For this solution ,time complexity would be o(n * const ) , const = number of digits. Honestly I am not quite sure on the correctness of this solution, though it seems correct.
Because the time limit is 1sec.It may fail if the algorithm is O(N^2) where the max N is 10^4.the following alg is O(K^2) where K = (1<<11)=2048,it can insure the time limit 1sec.
1)represent each number with a integer from 0 to (1<<11)-1.where ith bit of the integer will be set 1 if the number contains the digit i.for instance 11330 will be represented by (1<<1)|(1<<3)|(1<<0)=11.
2)we have an array to accord the count of each integer
3)two for loops the array of the integer to count.
- notbad July 17, 2012