k-Ary Tree Geeks For Geeks

-

Problem Link:


https://practice.geeksforgeeks.org/problems/k-ary-tree1235/1


(It is also the problem of the day for 18-04-2022)


Solution:


class Solution {

    static Long karyTree(int k, int m) {

        long a=01;//return (long)(Math.pow(k,m)%1000000007);

        

        for(int i=0;i<m;i++){

            a=(a*k)%1000000007;

        }

        return a;

    }

};



TIME COMPLEXITY: O(M)[GFG Time:10.34/18.44]

SPACE COMPLEXITY: O(1)

AUXILIARY SPACE: O(1)

TOTAL TEST CASES:111


APPROACH USED:


Here if we observe clearly then a number of leaf nodes are equal to k^m.

eg if k=3 m=2

at the 0th level only one node ie the head node

at the 1st level three nodes 

at the 2nd level, each of the three nodes will be further divided into 3 nodes. Hence 1*3=3 so for 3 nodes 3*3=9

and all are leaf nodes and equal to 3^2 ie 9


So we will find out the value of k raise to the power m.


Question arises:

Can't we directly use Math. pow(k,m) and change the return value from double to long?

Answer:

Yes, it is an inbuilt method that we can use but in the question, one condition is also there that the answer may be very large and for that, you need modulo of 1000000007.

But in some cases, calculations will be very long so every time you need to do modulo 1000000007. Hence for that reason only returning the value after taking modulo in last will not be suitable.

So instead of using the direct Math. pow() function we will use for loop and do modulo every time.


"Thanks For Reading.😇"

"Share Further To Increase Knowledge Treasure.😊"


 

Comments

  1. UnknownApril 18, 2022 at 5:32 AM

    Hi! I didn't get the following statement.


    "But in some cases, calculations will be very long so every time you need to do modulo 1000000007. Hence for that reason only returning the value after taking modulo in last will not be suitable."

    ReplyDelete
    Replies
    1. BossCoderApril 19, 2022 at 9:56 PM

      Sorry for being late into conversation.

      By this statement I mean to say that

      for example you have one testcase as k=93075 and m=307930 then

      in first iteration a=93075*1=93075;
      in second iteration a=93075*93075=8662955625
      in third iteration a=8662955625*93075=806304594796875
      in fourth iteration a=806304594796875*93075=75046800160719140625
      …
      …
      …
      …


      ..

      at one stage we will get value which will overcome the range of long i.e. more than 64 bit value and hence after that all values will be more than that as we are doing multiplication only.

      The only method by which we can prevent is by taking a modulo 1000000007 every time.

      It is so because it will always keep the answer in range of long and hence return the correct output.
      It also means that you can not return answer by doing modulo once in last as you don't know how large the value will be and even after doing modulo will it come in range or not. So you need to do modulo every time at every stage or every iteration.

      Hence signifying my earlier statement

      "But in some cases, calculations will be very long so every time you need to do modulo 1000000007. Hence for that reason only returning the value after taking modulo in last will not be suitable."

      Hope it helps and if you feel anything to ask don't hesitate, ask freely.😊,we are here to help you and clear your queries.😇


      Delete

Post a Comment

Popular posts from this blog

Solutions Of Practice Questions Dated 01-06-2022

-
Question 1: Transmit the Message: Solution: import java.util.*; class Solution{     public static void main(String arg[]){         Scanner sc=new Scanner(System.in);         String s=sc.next();                          ArrayList<Integer>aa=new ArrayList<Integer>();         ArrayList<Character>ab=new ArrayList<Character>();                  char flag=s.charAt(0);        int index=0;        int count=1;         for(int i=1;i<s.length();i++){             if(flag==s.charAt(i)){                 count++;             }             else{                 aa.add(index,count);                 ab.add(index,flag);                 count=1;                 flag=s.charAt(i);                 index++;             }         }         aa.add(index,count);         ab.add(index,flag);                  int max=Collections.max(aa);                  for(int i=aa.size()-1;i>0;i--){             if(aa.get(i)==max){                 flag=ab.get(i);                 break;             }
Read more

CODEFORCES SPY DETECTED ROUND 713

-
 import java.util.*; public class CodeForcesSpyDetected{ public static void main(String arg[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); ArrayList <Integer> aa=new ArrayList<Integer>();  while(t -->0){ int n=sc.nextInt(); int arr2[]=new int[n]; for(int i=0;i<n;i++){ arr2[i]=sc.nextInt(); } for(int i=0;i<n;i++){ aa.add(arr2[i]); } for(int i=0;i<aa.size();i++){ //System.out.println(Collections.frequency(aa,aa.get(i))); if(Collections.frequency(aa,aa.get(i))==1){ System.out.println((i+1)); aa.clear(); break; } } } } }
Read more

Maximum Winning Score Geeks For Geeks

-
Problem Link: https://practice.geeksforgeeks.org/problems/4ead9c3991a3822f578309e2232bc5415ac35cb9/1# It is also the problem of the day for 5 march. Solution: class Solution {     public static Long findMaxScore(Node root)     {         Node temp=root;         long sum=0;         while(temp!=null){             if(temp.right==null && temp.left==null){                 return (long) temp.data;             }             else{                 return (long) temp.data*Long.max(findMaxScore(temp.left),findMaxScore(temp.right));             }         }         return sum;     } } Time Complexity:[GFG Time:0.7/2.9] Space Complexity: O(N)[Number of nodes given in tree] Auxiliary Space: O(1) Approach Used: Here we used an approach that we will traverse recursively. And when we travel recursive we follow the bottom to the top approach of the tree.  It means we will see the leaf node and then move up to the tree.  For recursion, we should have a base condition and that is when node. right or
Read more