Adobe Interview Question
Country: India
Interview Type: Written Test
This will work
int main(void)
{
int arr[100000];
for(int i=0;i<100000;i++)
arr[i]=1;
int i,n,num=0;
cin>>n;
for( i=0;i<1000000;i++)
{
num=(num*10+arr[i])%n;
if(num==0)
break;
}
for(;i>=0;i--)
cout<<arr[i];
getch();
}
Great, but why not just make a count here with a while condition on num ==0(ofcourse initialize it with 1), rather than looping on a large number. That will save space i think. You don't need an array. You just need to output 1 as long as variable count. That will also take care of a long number possibility which can't fit in int, long ranges.
Please comment on my solution, I think it works, Thanks!
int test1s(int n)
{
int num1s = 0;
while(n%10==1)
{
n = n/10;
num1s++;
}
if( n == 0 )
return num1s;
else
return 0;
}
string minmul3(int n)
{
string err = "err";
if (mod(n+10,10)!=3)
return err;
//we are solving the problem by iterative find the digit of b,which satisfies n*b=111....11.
//pre recomputed map[i] = s; st: mod(s*3+i,10) = 1;
int map[] = {7,0,3,6,9,2,5,8,1,4};
int res =0;
int count = 0;
while (test1s(res)==0)
{
count++;
int b = map[res%10];
res = res/10 + b*n;
}
count = count + test1s(res);
string result;
result.resize(count+1);
memset(result.c_str(),'1',count);
result.c_str()[count+1] = 0;
return result;
}
#include<iostream.h>
#include<conio.h>
#include<math.h>
int main()
{
clrscr();
int a,i,b,count=1;
cout<<"Enter a";
cin>>a;
for(i=1;;i+=b)
{
count++;
b=pow(10,count);
if(a%10!=3)
{cout<<"\n wrong output";
getch();
return 0;
}
else
{
if(i%10==1)
{
if(i%a==0)
{
cout<<"\n Ans is "<<i<<" is divided by "<<a ;
getch();
return 0;
}
}
}
}
getch();
}
#include"stdio.h"
#define SIZE 100000
int modulo(int num[],int n)
{
int pre_ten=1;
int pre_mod=0;
int i=0,count=0;
while(i<SIZE)
{
count++; i++;
pre_mod=(pre_mod + pre_ten)%n ;
if(pre_mod==0) break ;
pre_ten=(pre_ten*10)%n ;
}
if(i==SIZE) return -1;
return count ;
}
// I assume that answer will come within 100000 digits
int main()
{
int num[SIZE] ;
int i;
for(i=0;i<SIZE;i++)
num[i]=1;
int n;
scanf("%d",&n);
int c=modulo(num,n) ;
printf("%d\n",c);
// c is total 1's in answer
// so we have answer string.
return 0;
}
start with no. of 1's as 0 in answer. Then dynamically increase no. of 1's in answer until we get the answer. We will get the ans when answer modulo n becomes zero. use this : (a+b)%n= (a%n + b%n)%n.
let at some time ans is 1111 (it mean we have 1111%n), then
11111%n= (10000 + 1111)%n = (10000%n + 1111%n)%n.
also 10000%n= (10*(1000%n))%n ( use of (a*b)%n= (a*(b%n))%n )
#include"stdio.h"
#define SIZE 100000
int modulo(int num[],int n)
{
int pre_ten=1;
int pre_mod=0;
int i=0,count=0;
while(i<SIZE)
{
count++; i++;
pre_mod=(pre_mod + pre_ten)%n ;
if(pre_mod==0) break ;
pre_ten=(pre_ten*10)%n ;
}
if(i==SIZE) return -1;
return count ;
}
// I assume that answer will come within 100000 digits
int main()
{
int num[SIZE] ;
int i;
for(i=0;i<SIZE;i++)
num[i]=1;
int n;
scanf("%d",&n);
int c=modulo(num,n) ;
printf("%d\n",c);
// c is total 1's in answer
// so we have answer string.
return 0;
}
I think this may work
}
- vishal August 10, 2013