Length of smallest sequence having sum X and product Y | C ++ program for the above approach ; Function for checking valid or not ; Function for checking boundary of binary search ; Function to calculate the minimum sequence size using binary search ; Initialize high and low ; Base case ; Print - 1 if a sequence cannot be generated ; Otherwise ; Iterate until difference between high and low exceeds 1 ; Calculate mid ; Reset values of high and low accordingly ; Print the answer ; Driver Code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define ll  long long NEW_LINE #define pb  push_back NEW_LINE double temp ( int n , int x ) { return pow ( x * 1.0 / n , n ) ; } bool check ( int n , int y , int x ) { double v = temp ( n , x ) ; return ( v >= y ) ; } void find ( int x , int y ) { int high = ( int ) floor ( x / exp ( 1.0 ) ) ; int low = 1 ; if ( x == y ) cout << 1 << endl ; else if ( ! check ( high , y , x ) ) cout << -1 << endl ; else { while ( high - low > 1 ) { int mid = ( high + low ) / 2 ; if ( check ( mid , y , x ) ) high = mid ; else low = mid ; } cout << high << endl ; } } int main ( ) { int x = 9 , y = 8 ; find ( x , y ) ; return 0 ; }