Question

Every positive integer has a multiple that, when expressed in base ten, is comprised entirely of zeros and ones. Write a procedure to find the least multiple of n, the input parameter, which is of the required form.

Warnings: You should definitely use the long data type for this computation. The least multiple of the required form may be much larger than the input n. For example, what is the least such multiple of 9 that contains only zeros and ones? What is the least such multiple of 99?

Design your procedure to detect overflow and return -1 if it is unable to find the required multiple.

solve in c++

Answer 1

C++ code:

#include<iostream>
using namespace std;
//function to check whether all digits of n are zero or one
//if all are 0/1 then returns 1
//otherwise returns 0
int check_zero_one(long int n)
{
   int digit;
   while(n!=0)
   {
       digit=n%10;
       n=n/10;
       if(digit>1)
           return(0);
   }
   return(1);
}

//function to find least multiple d of n
//such that d*n contains only 0/1
long int find_multiple_zero_one(long int n)
{
   int i=1;
   while(i>0)
   {
       if(check_zero_one(i*n))
           return(i);
       i++;
   }
   return(-1);
}

//main driver function
int main()
{
   long int n;
   cout<<"Enter a number:";
   cin>>n;
   long int d=find_multiple_zero_one(n);
   cout<<"Least multiple contains 0 or 1 is:"<<d<<endl;
   cout<<"As "<<n<<"*"<<d<<"="<<n*d<<endl;
  
}

output: