Antall elementer med oddefaktorer i gitt område
#practiceLinkDiv { display: ingen !viktig; } Gitt en rekkevidde [ n m ] finn antall elementer som har et oddetall faktorer i det gitte området ( n og m inklusive).
Eksempler:
Input : n = 5 m = 100 Output : 8 The numbers with odd factors are 9 16 25 36 49 64 81 and 100 Input : n = 8 m = 65 Output : 6 Input : n = 10 m = 23500 Output : 150
EN Enkel løsning er å gå gjennom alle tall fra n . For hvert tall sjekk om det har et partall av faktorer. Hvis den har et partall av faktorer, øker antallet slike tall og skriv til slutt ut antallet slike elementer. For å finne alle divisorer av et naturlig tall referer effektivt Alle delere av et naturlig tall
An Effektiv løsning er å observere mønsteret. Bare de tallene som er perfekte firkanter har et odde antall faktorer. La oss analysere dette mønsteret gjennom et eksempel.
For eksempel 9 har oddetall faktorer 1 3 og 9. 16 har også oddetall faktorer 1 2 4 8 16. Grunnen til dette er for andre tall enn perfekte kvadrater er alle faktorer i form av par, men for perfekte kvadrater er en faktor enkel og gjør totalen som oddetall.
Hvordan finne antall perfekte firkanter i et område?
Svaret er forskjellen mellom kvadratroten av m og n-1 ( ikke n )
Det er et lite forbehold. Som begge n og m er inkluderende hvis n er et perfekt kvadrat vil vi få et svar som er mindre enn ett av det faktiske svaret. For å forstå dette, vurder området [4 36]. Svaret er 5, dvs. tallene 4 9 16 25 og 36.
Men hvis vi gjør det (36**0.5) - (4**0.5) får vi 4. Så for å unngå denne semantiske feilen tar vi n-1 .
// C++ program to count number of odd squares // in given range [n m] #include using namespace std ; int countOddSquares ( int n int m ) { return ( int ) pow ( m 0.5 ) - ( int ) pow ( n -1 0.5 ); } // Driver code int main () { int n = 5 m = 100 ; cout < < 'Count is ' < < countOddSquares ( n m ); return 0 ; }
Java // Java program to count number of odd squares // in given range [n m] import java.io.* ; import java.util.* ; import java.lang.* ; class GFG { public static int countOddSquares ( int n int m ) { return ( int ) Math . pow (( double ) m 0.5 ) - ( int ) Math . pow (( double ) n - 1 0.5 ); } // Driver code for above functions public static void main ( String [] args ) { int n = 5 m = 100 ; System . out . print ( 'Count is ' + countOddSquares ( n m )); } } // Mohit Gupta_OMG <(o_0)>
Python3 # Python program to count number of odd squares # in given range [n m] def countOddSquares ( n m ): return int ( m ** 0.5 ) - int (( n - 1 ) ** 0.5 ) # Driver code n = 5 m = 100 print ( 'Count is' countOddSquares ( n m )) # Mohit Gupta_OMG <0_o>
C# // C# program to count number of odd // squares in given range [n m] using System ; class GFG { // Function to count odd squares public static int countOddSquares ( int n int m ) { return ( int ) Math . Pow (( double ) m 0.5 ) - ( int ) Math . Pow (( double ) n - 1 0.5 ); } // Driver code public static void Main () { int n = 5 m = 100 ; Console . Write ( 'Count is ' + countOddSquares ( n m )); } } // This code is contributed by Nitin Mittal.
PHP // PHP program to count // number of odd squares // in given range [n m] function countOddSquares ( $n $m ) { return pow ( $m 0.5 ) - pow ( $n - 1 0.5 ); } // Driver code $n = 5 ; $m = 100 ; echo 'Count is ' countOddSquares ( $n $m ); // This code is contributed // by nitin mittal. ?>
JavaScript < script > // JavaScript program to count number of odd squares // in given range [n m] function countOddSquares ( n m ) { return Math . pow ( m 0.5 ) - Math . pow ( n - 1 0.5 ); } // Driver Code let n = 5 m = 100 ; document . write ( 'Count is ' + countOddSquares ( n m )); < /script>
Utgang:
Count is 8
Tidskompleksitet: O(1)
Hjelpeplass: O(1)
