CareerCup

boolean check(long N, long K) {
   for (long i=0; i<N-1; i++) {
         K = K/N;
   }
   return (K==N);
}

the best way can be ...

if ( (logK)/(logN) == N )
return true;

Here we can consider logarithm of any base as ... log(a) / log(b) = log of 'a' to the base b.
hence log(K)/log(N) == N ==> "logarithm of K to the base N" == N
==> K == N^N

We can find the last k digits in binary using modular exponential method.

Algorithm :-
Match the digits of N^N mod 10^(number of digits of (K) - number of digits of (K/N)) with the same number of digits of K.
Make K = K/N.
Match the digits of N^(N-1) mod 10^(number of digits of (K) - number of digits of (K/N)) with the same number of digits of K.
Do this recursively till the exponential reduces to 0.

In the worst case when the numbers are equal all the numbers are required to be matched.

The finding of number of digits in K/N still needs to be figured out without doing the actual division.

Why can't you simply use a if condition like the following :

if( (N*(Log (N))) == log(K) )

Since we know bounds on n.
We can pre-process and store the digits of n^n as array of long's.

Now for any call to the funtion we represent k as array of long's, pick the appropriate pre-processed array corresponding to n and then compare the arrays.

you can calculate sum = k / n; if sum == 0 then return false, else you can calculate next, if you can divide n times;

if K<=1000 then how can N be greater than 4. Wha's the worry??

no pls ignore that K<=1000, it s typo.. k can be ie N^N can be of 1000 digits !!!

this problem can be solved even linear algorithm , but I think O(logn) double squaring algorithm can be used to make it faster , but with only 1000 digits , Java's BigClass implementation is the way to go , or u can write ur own Big Class .

/* Bug may exists beware */

public static boolean check(int n,String k) {
		
		BigInteger N = new BigInteger(n+"");
		BigInteger K = new BigInteger(k);
		BigInteger res = new BigInteger("1");
		
		if (N.compareTo(K) ==0 )
			return true ; 
		
		
		for (int i = 1 ; i  <= n ; i++) {
			
			res = N.multiply(res) ; 
			//System.out.println(res);
			if (res.compareTo(K)>0)
				return false ; 
			 if (res.compareTo(K) ==0 )
				return true ; 
			
			
			
		}
		   return false ; 
		
		

	}


System.out.println(check(30,"101010101010010101010101010101010100110010101010101001010101010101010011"));

Set of (K, N) such that (N^N = K) and (0 <= K <= 1000) = [(1, 1), (2, 4), (3, 81), (4, 256)]
Now we can simply check whether (N,K) are part of this pair.

I do not know how efficient it is but I have a O(n) solution.
if we just try to see that for each element in (0 to n-1)[ Zn as in the abstract algebra] appear in K. if all of them appear n times it is n^n then it is other wise not

Initially we can check whether n is a factor of k or not
if(k%n==0)
then only we need to check further, otherwise return false directly.

and if it returns true then we can check whether n is even or odd in that way we need to loop only for logarithmic time that is greater improvement .

if n is even then proceed in multiples of n
eg:
if(n%2==0){
int flag=n;
for(i=0;i<n;i++)
{
k=k/flag;
if(k==1) return true;
flag=flag*flag;
}
return false;
}
similar could be handled for n being odd only 1 more iteration required in that case.

so in this case we didn't need to check again and again for same value of n and value of n increases in each iteration.. that is n, n^2, n^4, n^16..... so the algorithm runs in logarithmic time, that is greater improvement than naive approach.

Can you clarify what you mean here? Are you given only k? n? or both

Cool. So you are given both n and k. Am I right?

I think the question is, given a number find whether it is perfect square or not...
ex.

input answer
15 false
16 true
30 false
100 true

if(Math.pow(n,n)==k)

how about nlog(n) == log(k)? however i am using predefined log function.

private static bool EqualPower(int n, int k) {
      if (n >= k) {
        return false;
      }

      int pow = n;
      for (int i = 1; i < n; i++) {
        pow *= n;
      }
      if (pow == k) {
        return true;
      }
      return false;
    }

given n and k such that n^n=k
divide k/n untill 1 and count the loop ,if count==n is satisfied return true

Modular Exponential problem
N <= 1000, that means N can be expressed in 10 bits

function modular_pow(base, exponent, modulus)
    result := 1
    while exponent > 0
        if (exponent mod 2 == 1):
           result := (result * base) mod modulus
        exponent := exponent >> 1
        base = (base * base) mod modulus
    return result

modular_Pow(N, N, K)

since exponent N is 10 bit, while loop will iterate 10 times.
If the return result is 0 then N^N is divible by K

running time of this alogithm is (log N)

@banerjee36, did you try below approach

Here is the logn approach

int power(int n,int k)
{
        int p;
        if(k==0)
                return 1;
        else
        {
                p=power(n,k/2);
                p*=p;
                if(k&1)
                        p*=n;
                return p;
        }
}
 
int main()
{
        int n=3,k=27;
        power(n,n)==k?printf("Yes"):printf("No");
        return 0;
}

***ideone.*com/oEpgE***

boolean isKnpown(int n, int k) {
int temp=k;
for ( int i = 1; i <=n ; i++ ) {
if ( temp%n != 0 ) {
return (false);
}
temp= temp/n;

}
return true;
}

Sum of first n odd numbers will be square
This gives a solution to without multiplication.

basically N^2 = K or N = Sqrt(K)
its easier to check this even for K = 1000, N = Sqrt (K)... is easier to check....