Solve C++ Number Probs: Find the Smallest Number with 1-9 Digits

[ron_jay]

Hi

Lets see...I got this interesting program: To Find the smallest number which when put together with its square as a single number has the digits 1-9 exactly once i.e. it does not have a 0 in it.

Initial Observations:

1.The first thing to see is that the conglomerated no. should have only nine digits.

2.The method to put the two number together is:

number + (10*no. of digits in its square)+ the square

3.The sum of the digits will always be 45

4.the absolute(modulus) difference between adjacent digits in the cong.. no. has to be >0

5.There must be an infinite loop which will be made to break when the number is found

Ok this is my list of ways...now I can't figure out how to use these conditions at once.Perhaps we could use arrays, but I want the code to be as simple and intelligent as possible.Find the number.

 

[arunbg]

Well, a few comments on your observations... you don't really have to conglomerate the nos coz you really are going to split it later anyway(you probably knew that of course).
Taking sum of all the digits and checking if it equals 45 is a good idea, this quickly reduces computation involved with checking each digit.
Checking magnitude of modulus is almost useless, this holds true for any number with no same adjacent digits and the check requires digit pairwise checking.
You don't need to run an infinite loop, just find the smallest and largest numbers whose squares are 7 digit numbers, and run the code through this interval.

Lastly, you should use arrays to easily store individual digits for checking. You can have counters for each digit in a switch...case structure perhaps. If all counters are 1 for a no, then you have yourself a winner.

 

[ron_jay]

Well Thanks for the suggestions, I really appreciate it but looks like I already got a solution...See if this works>>

#include <iostream.h>
#include <conio.h>
#include <math.h>

int main(){

	long i=1,sq,flag,k,temp,copy,c,c1,cong,g;

	 while(1)//till infinity
	 {
		sq=i*i;flag=0;c=0;c1=0;  //initializing

		//--------------------------------------------------------
		while(sq!=0){c++;sq/=10;} //counting digits in square
		sq=i*i;

		cong=(i*pow(10,c))+sq; //putting no. and its square together
		copy=cong;

		while(copy!=0){c1++;copy/=10;}//coutning no. of digits in 'cong'

		//--------------------------------------------------------
		for(k=1;k<=9;k++){ //checking digits from 1-9

		 g=0;copy=cong;

		 while(copy!=0){

		  temp=copy%10;
		  if(temp==0){flag=-1;break;} //checking for zeroes
		  if(temp==k){g++;}
		  if(g>1){flag=-1;break;}//a digit can occur only once
		  copy/=10;
							}
		 if(flag==-1){break;}
		 else{flag++;}
		}
		//--------------------------------------------------------

		if(flag==9&&c1==9){cout<<i;break;}
		i++;
	 }
	return 0;
}

 

[ron_jay]

Ok that program is done.I have another tricky one:

Find the smallest number which can be expressed as the sum of squares of two different sets of numbers

eg. a^2+b^2=n
and also x^2+y^2=n

What i think is that we should consider all possible permutations of the two numbers in one set till the sum of their squares exceeds or equals to the number...that way the number which has two sets of these first should be the answer...

 

[arunbg]

Your first program seems to be all right at first glance. For the second one, I would say generate list of all squares in some suitably large range, and check for the smallest square that has repetitions in that list. This is much simpler than the one you suggested. Of course you can optimize the code as required.