Antal element med udda faktorer inom ett givet intervall
#practiceLinkDiv { display: ingen !viktigt; } Givet ett intervall [ n m ] hitta antalet element som har udda antal faktorer i det givna intervallet ( n och m inklusive).
Exempel:
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
A Enkel lösning är att gå igenom alla nummer med början från n . Kontrollera för varje nummer om det har ett jämnt antal faktorer. Om det har ett jämnt antal faktorer, öka antalet sådana antal och slutligen skriva ut antalet sådana element. För att hitta alla divisorer för ett naturligt tal hänvisa effektivt Alla delare av ett naturligt tal
En Effektiv lösning är att observera mönstret. Endast de siffror som är perfekta kvadrater har ett udda antal faktorer. Låt oss analysera detta mönster genom ett exempel.
Till exempel 9 har udda antal faktorer 1 3 och 9. 16 har också udda antal faktorer 1 2 4 8 16. Anledningen till detta är för andra tal än perfekta kvadrater alla faktorer är i form av par men för perfekta kvadrater är en faktor enkel och gör summan som udda.
Hur hittar man antalet perfekta rutor i ett intervall?
Svaret är skillnaden mellan kvadratroten av m och n-1 ( inte n )
Det finns en liten varning. Som båda n och m är inklusive om n är en perfekt kvadrat kommer vi att få ett svar som är mindre än det faktiska svaret. För att förstå detta, överväg intervallet [4 36]. Svaret är 5, dvs siffrorna 4 9 16 25 och 36.
Men om vi gör det (36**0.5) - (4**0.5) får vi 4. Så för att undvika detta semantiska fel 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>
Utgång:
Count is 8
Tidskomplexitet: O(1)
Hjälputrymme: O(1)
